0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 5
|
||||||
1 | ||||||
Задача про Лестницу28.02.2013, 13:02. Показов 11389. Ответов 8
Метки нет (Все метки)
Условия формулируются так:
Есть лестница высотой в n ступенек (плюс «нулевая» - площадка, где мы стоим вначале). На каждой ступеньке написано число (положительное или отрицательное). На стартовой площадке и на последней ступеньке - нули. Можно ступать либо на следующую ступеньку либо перескакивать через одну. Напишите алгоритм, определяющий, как надо шагать, чтобы сумма чисел на пройденных ступеньках (тех, на которые мы ступали) была максимальна. Мой код:
Формат такой: 4 0 -58 -39 93 -92 0 я указываю, что на нулевой ступеньке число =0 и на последней=0 выход - максимальная сумма ступенек. Мне задачу забраковали. Сказали, что в ней ошибка. Может быть её и нет. (Я склоняюсь к этому варианту) Программу проверяли видимо руками, тест на котором не верно - не сказали. Я вводила несколько тестов, и моя программа выдавала верный результат. Верную сумму. Не подскажете в чем может быть проблема? И существует ли эта ошибка впринципе?
0
|
28.02.2013, 13:02 | |
Ответы с готовыми решениями:
8
Задача про взлом кода из книги Эрика Фримена про основы javascript в конце 5 главы. Задача на перебор вариантов. Задача Л.Эйлера. Про чиновника Нарисовать лестницу Комбинаторика подъёма на лестницу |
28.02.2013, 13:15 | 2 |
для "меньше или равно" есть оператор <=
Добавлено через 1 минуту Это неверное решение задачи. Точнее, я пока не уверен, что всё так просто. Лучше используй динамическое программирование.
0
|
0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 5
|
|
28.02.2013, 13:16 [ТС] | 3 |
Понятно. Я быстро писала, возможно где-то ошиблась.
Можно динамику. Можно через такие условия. Никто не ограничивает.
0
|
28.02.2013, 13:26 | 4 | |||||
1
|
0 / 0 / 0
Регистрация: 18.02.2013
Сообщений: 5
|
|
28.02.2013, 13:31 [ТС] | 5 |
Я поняла. Спасибо. Больше не нужно.
0
|
45 / 21 / 6
Регистрация: 28.02.2013
Сообщений: 194
|
||||||
28.02.2013, 13:38 | 6 | |||||
Я вижу 2 решения
1. Перебор всех возможных ходов 2. Перескок максимальной суммы отрицательных чисел Перенёс код себе. (к сожалению у меня нету std и всяких vektor) Но немного изменил по логике. Вот первый пример - и ответ неверен.
0
|
0 / 0 / 0
Регистрация: 10.12.2019
Сообщений: 1
|
||||||
10.12.2019, 19:17 | 7 | |||||
0
|
45 / 21 / 6
Регистрация: 28.02.2013
Сообщений: 194
|
||||||
10.12.2019, 22:54 | 8 | |||||
Мда, много времени прошло с 2013. Но раз уж мне на почту пришел ответ - то и я отвечу.
Подумав минут 7 понял что задача реально классная и имеет элегантнейшее решение. Для всех ступенек начиная с конца определяем максимально возможную сумму очей если мы на ней окажемся
0
|
11.12.2019, 00:13 | 9 |
Stelob, Kuzia domovenok, nefton, собственно это всё вариации одного и того же решения.
1
|
11.12.2019, 00:13 | |
11.12.2019, 00:13 | |
Помогаю со студенческими работами здесь
9
Массив описывает лестницу Комбинаторика подъёма на лестницу Нарисовать лестницу из восьми перекладин Написать процедуру, которая рисовала бы лестницу Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |