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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
fetchhell
0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 5
28.02.2013, 13:02     Задача про Лестницу #1
Условия формулируются так:

Есть лестница высотой в 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
выход - максимальная сумма ступенек.

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

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

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

C++ [C++] задача про вектор
Задача про 2 рюкзака C++
Задача про монеты C++
C++ Массив описывает лестницу
C++ Задача про яйца
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 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;
* * * * }
Это неверное решение задачи. Точнее, я пока не уверен, что всё так просто. Лучше используй динамическое программирование.
fetchhell
0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 5
28.02.2013, 13:16  [ТС]     Задача про Лестницу #3
Понятно. Я быстро писала, возможно где-то ошиблась.
Можно динамику. Можно через такие условия. Никто не ограничивает.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 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;
}
fetchhell
0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 5
28.02.2013, 13:31  [ТС]     Задача про Лестницу #5
Я поняла. Спасибо. Больше не нужно.
nefton
44 / 20 / 5
Регистрация: 28.02.2013
Сообщений: 184
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
Yandex
Объявления
28.02.2013, 13:38     Задача про Лестницу
Ответ Создать тему
Опции темы

Текущее время: 11:02. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru