Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
fetchhell
0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 5
#1

Задача про Лестницу - C++

28.02.2013, 13:02. Просмотров 1657. Ответов 5
Метки нет (Все метки)

Условия формулируются так:

Есть лестница высотой в n ступенек (плюс «нулевая» - площадка, где мы стоим вначале). На каждой ступеньке написано число (положительное или отрицательное). На стартовой площадке и на последней ступеньке - нули. Можно ступать либо на следующую ступеньку либо перескакивать через одну. Напишите алгоритм, определяющий, как надо шагать, чтобы сумма чисел на пройденных ступеньках (тех, на которые мы ступали) была максимальна.

Мой код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<vector>
#include<cstdio>
 
using namespace std;
 
vector<int> stairs;
 
int main()
{
    int n = 0;
    cin >> n;
 
    stairs.resize(n + 2);
 
    for(int i = 0; i < n + 2; i++)
    {
        int num;
        scanf("%d", &num);
        stairs[i] = num;
    }
 
    int cur=0, sum=0;
 
    while(cur < n)
    {
        if(stairs[cur + 1] == stairs[cur + 2] || stairs[cur + 1] < stairs[cur + 2])
        {
            sum += stairs[cur + 2];
            cur += 2;
        }
        else 
        {
            sum += stairs[cur + 1];
            cur += 1;
        }
    }
 
    printf("%d\n", sum);
 
    //system("pause");
    return 0;
}
На вход подается кол-во ступенек и числа на них.
Формат такой:

4
0 -58 -39 93 -92 0

я указываю, что на нулевой ступеньке число =0 и на последней=0
выход - максимальная сумма ступенек.

Мне задачу забраковали. Сказали, что в ней ошибка.

Может быть её и нет. (Я склоняюсь к этому варианту) Программу проверяли видимо руками, тест на котором не верно - не сказали.

Я вводила несколько тестов, и моя программа выдавала верный результат. Верную сумму.
Не подскажете в чем может быть проблема? И существует ли эта ошибка впринципе?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.02.2013, 13:02
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача про Лестницу (C++):

Массив описывает лестницу - C++
Дан упорядоченный массив целых чисел. Он описывает лестницу, разность соседних элементов - высота ступеней. Имеется некое существо,...

Задача про числа - C++
Думаю, думаю, но всё равно не могу понять как решить. Задача: Дан массив из положительных чисел и два числа a и b. Мы можем отнять...

Задача про кубики - C++
Есть столбики указанных размеров. Задание такое: Какое наименьшое количество перекладываний необходимо сделать, что бы высота 2х любых...

Задача про синусоиду - C++
Велосипедист Павлуша выехал на широкую дорогу. Но ехать иначе, чем по закону синусоиды, ему никак не удавалось. Юный спортсмен стартовал в...

Задача про буквы - C++
Условие задачи таково: изменить в строке все маленькие буквы на большие, всё это делается в файле!Мой вопрос:существуют ли какие лиюо...

Задача про метеостанции - C++
На южном полюсе расположены N пронумерованных метеорологических станций. Каждая станция соединена с другими станциями линиями связи. В...

5
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 1
28.02.2013, 13:15 #2
Цитата Сообщение от fetchhell Посмотреть сообщение
if(stairs[cur + 1] == stairs[cur + 2] || stairs[cur + 1] < stairs[cur + 2])
для "меньше или равно" есть оператор <=

Добавлено через 1 минуту
Цитата Сообщение от fetchhell Посмотреть сообщение
if(stairs[cur + 1] == stairs[cur + 2] || stairs[cur + 1] < stairs[cur + 2])
* * * * {
* * * * * * sum += stairs[cur + 2];
* * * * * * cur += 2;
* * * * }
* * * * else
* * * * {
* * * * * * sum += stairs[cur + 1];
* * * * * * cur += 1;
* * * * }
Это неверное решение задачи. Точнее, я пока не уверен, что всё так просто. Лучше используй динамическое программирование.
0
fetchhell
0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 5
28.02.2013, 13:16  [ТС] #3
Понятно. Я быстро писала, возможно где-то ошиблась.
Можно динамику. Можно через такие условия. Никто не ограничивает.
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 1
28.02.2013, 13:26 #4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<vector>
#include<cstdio>
 
using namespace std;
 
vector<int> stairs;
vector <int> records;
int main()
{
    int n = 0;
    cin >> n;
 
    stairs.resize(n + 2);
    records.resize(n + 2);
    for(int i = 0; i < n + 2; i++)
    {
        int num;
        scanf("%d", &num);
        stairs[i] = num;
    }
 
 
    records[0]=stairs[0]; records[1]=stairs[1];
    int cur=0, sum=0;
    for(int i = 2; i < n + 2; i++){
        if(records[i-1]>records[i-2]) records[i]=stairs[i]+records[i-1];
        else                                  records[i]=stairs[i]+records[i-2];
    }
 
    printf("%d\n", records[n+1]);
 
    //system("pause");
    return 0;
}
1
fetchhell
0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 5
28.02.2013, 13:31  [ТС] #5
Я поняла. Спасибо. Больше не нужно.
0
nefton
44 / 20 / 5
Регистрация: 28.02.2013
Сообщений: 189
28.02.2013, 13:38 #6
Я вижу 2 решения
1. Перебор всех возможных ходов
2. Перескок максимальной суммы отрицательных чисел

Перенёс код себе. (к сожалению у меня нету std и всяких vektor)
Но немного изменил по логике.
Вот первый пример - и ответ неверен.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include "stdafx.h"
 
#include<iostream>
#include<vector>
#include<cstdio>
 
 
int main()
{
    int n = 0;
    int stairs[100];
 
    stairs[0]=0;
    stairs[2]=2;
    stairs[3]=2;
    stairs[4]=2;
    stairs[5]=2;
    stairs[6]=2;
    stairs[7]=2;
    stairs[8]=2;
    stairs[9]=0;
   
   
 
    n=7;
    int cur=0, sum=0;
 
    while(cur < n)
    {
        if(stairs[cur + 1] == stairs[cur + 2] || stairs[cur + 1] < stairs[cur + 2])
        {
            sum += stairs[cur + 2];
            cur += 2;
        }
        else 
        {
            sum += stairs[cur + 1];
            cur += 1;
        }
    }
 
    printf("%d\n", sum);
    scanf("%d",cur);
 
    //system("pause");
    return 0;
}
Пишет сумма = 8
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.02.2013, 13:38
Привет! Вот еще темы с ответами:

Задача про рюкзак - C++
Из заданных N предметов выбрать такие, чтобы суммарный вес был менее 30 кг, а стоимость - наибольшей. Напечатать суммарную стоимость. ...

Задача про рюкзак - C++
Всем привет! Есть программа, которая решает задачу про рюкзак. Когда у меня количество &quot;предметов&quot; 5 или 10, то все работает хорошо....

Задача про птичек - C++
4. Птицы летят клином: в 1-м ряду —1 птица, во 2-м ряду — 3 птицы, в 3-м ряду — 5 птиц и т.д. Сколько птиц летит в 11 ряду? Сколько...

Задача про самолет - C++
Здравствуйте.вопрос,вернее просьба разрбраться в своем же коде.писал честно говоря &quot;по памяти&quot;,когда начал разбирать свои ошибки,честно...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Yandex
Объявления
28.02.2013, 13:38
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru