|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
07.11.2017, 11:02 | #1 |
Пользователь
Регистрация: 07.11.2017
Сообщений: 42
|
Сломанные ступеньки
Всем привет. Помогите доработать задачу.
Заяц может ходить на следующую ступеньку, переступать через одну и через две, однако некоторые ступеньки сломаны. Сколькими способами можно попасть на N-ю ступеньку. входные данные В первой строке записано число N - номер ступеньки на которую нужно попасть и K - количество сломанных ступеней. (1 ≤ k ≤ n ≤ 60). В следующей строке записаны номера ступеней которые сломаны. Исходные данные Вывести одно число, количество способов которыми можно попасть на строчку с номером N, или -1, если попасть невозможно. Вот мой код вроде на Паскале работает, а на сайте проходит на 20%. Суть идеии: если количество сломанных ступенек больше 2 и j+1 элемент находится между j и j+2 элементами (3 сломанные ступеньки идут подряд) то -1 иначе результат. Код:
Код программы нужно выделять (форматировать) тегами [CODE] (читать FAQ) Модератор Последний раз редактировалось Serge_Bliznykov; 07.11.2017 в 11:31. |
08.11.2017, 07:56 | #2 |
Участник клуба
Регистрация: 03.06.2009
Сообщений: 1,834
|
комбинаторика, что ли?
С из N по K надо считать? а есть проверка, что сломанных ступенек K Больше или равно, чем N? - тогда попасть на последнюю ступеньку нельзя и должно выводить -1. а если последняя ступенька цела (есть хоть одна целая), то уже есть один способ туда добраться - перепрыгнуть через все сломанные ступеньки сразу на последнюю. и для чего в этом коде цифры? Код:
Программирование - это единственный способ заставить компьютер делать то, что тебе хочется, а не то, что приходится.
Последний раз редактировалось NetSpace; 08.11.2017 в 08:01. |
08.11.2017, 10:17 | #3 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Для начала нужно найти решение как попасть с 1-ой на последнюю ступеньку участка без поломанных ступенек. И найти для этого количество решений линейного диофантового уравнения x+2y+3z=n-1, где n количество ступенек. А дальше слева направо участок за участком с учетом того, что начало и конец этого участка зависит от количества поломанных ступенек в начале и в конце участка. И само собой, если где-то подряд больше 2-ух поломанных то нет решения
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
08.11.2017, 10:54 | #4 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
задача известная, на динамическое программирование.
на форуме была http://www.programmersforum.ru/showthread.php?t=168384 (без сломанных ступенек, но зато заяц мог прыгать на K ступенек). как эту со сломанными решать я не знаю, но думаю, что нужно в том же направлении двигаться - заполнять массив [1..N] значениями функции F(X), которое означает, сколькими способами можно попасть на ячейку со значением X, но с учётом сломанных ступенек. |
09.11.2017, 12:58 | #5 | |
Пользователь
Регистрация: 07.11.2017
Сообщений: 42
|
Цитата:
Задача работает для целых ступенек. Я добавил код для сломанных, но где-то он не работает верно. Прошу помочь |
|
09.11.2017, 14:20 | #6 |
Программист
Участник клуба
Регистрация: 23.06.2009
Сообщений: 1,772
|
Короче, Вы сами в своём коде не можете разобраться, а хотите чего-то от нас..
Лично мне проще с нуля написать.. Код:
|
09.11.2017, 14:43 | #7 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
|
10.11.2017, 09:31 | #8 |
Программист
Участник клуба
Регистрация: 23.06.2009
Сообщений: 1,772
|
Ещё можно остановить цикл, если все три уйдут в ноль
|
10.11.2017, 09:45 | #9 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
|
10.11.2017, 11:03 | #10 | |
Пользователь
Регистрация: 07.11.2017
Сообщений: 42
|
Цитата:
Код:
Сюда я добавил код, который вводит число сломанных ступенек и их номер: Код:
Код:
Код:
Код:
А как записать для моего случая (моего кода программы) Код:
Очень всем благодарен. |
|