|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
11.10.2011, 12:43 | #1 |
Регистрация: 11.10.2011
Сообщений: 3
|
Задача на динамическое программирование)
В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек N. Заяц может одним прыжком преодолеть не более К ступенек. Для разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы. Директору любопытно, сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях K и N. Помогите директору написать программу, которая поможет вычислить это количество. Например, если K=3 и N=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т.е. при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы. Входные данные В единственной строке входного файла INPUT.TXT записаны два натуральных числа K и N (1 ≤ K ≤ N ≤ 300). К - максимальное количество ступенек, которое может преодолеть заяц одним прыжком, N – общее число ступенек лестницы. Выходные данные В единственную строку выходного файла OUTPUT.TXT нужно вывести количество возможных вариантов различных маршрутов зайца на верхнюю ступеньку лестницы без ведущих нулей. Код:
Сдать задачу
Последний раз редактировалось Serge_Bliznykov; 11.10.2011 в 15:01. |
11.10.2011, 12:52 | #2 |
Участник клуба
Регистрация: 08.10.2007
Сообщений: 1,185
|
Википедия -> Динамическое программирование.
Что именно непонятно? |
11.10.2011, 13:00 | #3 |
Регистрация: 11.10.2011
Сообщений: 3
|
Как решить эту задачу)
|
11.10.2011, 13:21 | #4 | |
Участник клуба
Регистрация: 08.10.2007
Сообщений: 1,185
|
Цитата:
f(1) = 1 // прыгнул на ступеньку f(2) = 1 + f(1) = 2 // прыгнул или сразу, или с первой f(3) = 1 + f(1) + f(2) = 4 // прыгнул или сразу, или с первой, или со второй f(4) = f(1) + f(2) + f(3) = 7 // сразу нельзя, прыгнул или с первой, или со второй, или с третьей ....... f(n) = f(n - k) + ... + f(n - 1) |
|
11.10.2011, 13:56 | #5 |
Регистрация: 11.10.2011
Сообщений: 3
|
Огромнейшее спасибо!!!
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Динамическое программирование!!! | Fuckkiller | Microsoft Office Excel | 13 | 04.05.2011 19:03 |
динамическое программирование | stefan0202 | Паскаль, Turbo Pascal, PascalABC.NET | 3 | 07.02.2011 22:05 |
Динамическое программирование | joey_ramone | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 23.04.2010 13:51 |
Динамическое программирование. | MAKEDON | Помощь студентам | 6 | 26.08.2009 14:10 |
Задача на динамическое программирование | Римма1990 | Помощь студентам | 2 | 02.04.2009 23:11 |