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

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

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

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

28.02.2013, 13:02. Просмотров 1517. Ответов 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
выход - максимальная сумма ступенек.

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

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

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

задача про массивы C++
Задача про 2 рюкзака C++
C++ Задача про буквы
C++ Задача про кузнечиков
задача про матрицы C++
C++ Задача про самолет
C++ Массив описывает лестницу
C++ Задача про небоскребы
C++ Задача про фермера
C++ Задача про банку
задача про МКАД C++
C++ Задача про монеты

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 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
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 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
Сообщений: 188
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     Задача про Лестницу
Ответ Создать тему
Опции темы

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