Зайчик

[ros.pro]

Доброго времени суток, уважаемые форумчане!

Есть задача:

В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек 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 нужно вывести количество возможных вариантов различных маршрутов зайца на верхнюю ступеньку лестницы без ведущих нулей.
Примеры
INPUT.TXT OUTPUT.TXT
1 3 1
2 7 21
3 10 274

Юзал поиск. Нашел формулу:
x(n) = x(n - 1) + x(n - 2) + ... + x(n - k)

Так же нашел решение. Все работает, но не понимаю как это работает =)

Приведу пример, где k=3, n=4. Значит формула должна выглядеть так:

x(n) = x(n-1)+x(n-2)+x(n-3)+x(n-k)

Но вот вопрос: Как вычислить x(n-1), x(n-2) и т.д. ?

Заранее спасибо. Целый день сегодня бьюсь ((

[Крот]

Интересная задача. Я сначала думал что вот так надо считать
(4-1) + (4-2) + (4-3)
Только здесь получается 6 а не 7.

[Vago]

#!/usr/bin/python
# -*- coding: cp1251 -*-

K = 3
N = 4

nRoutes = 0

steps = []

def RabbitJump( N ):

    global K, nRoutes

    i = 1
    while i <= K:
        if i < N:
            steps.append( i )
            RabbitJump( N-i )
        else:
            steps.append( i )
            print steps
            steps.pop()
            if len( steps ) > 1:
                steps.pop()
            nRoutes += 1
            return
        i += 1


RabbitJump( N )
print nRoutes

#

120323.jpg

Что делают питоновские append() и pop() - думаю, понятно. На своём языке реализуешь, надеюсь.

[ros.pro]

2 Vago, большое спасибо, но программу я напишу сам, как только разберусь с принципом вычисления на бумаге.Вычисление x(n-1), x(n-2) и т.д. Я именно этот момент не понимаю. Объясните плиз...

[evg_m]

x(n) = x(n-1)+x(n-2)+x(n-3)+x(n-k)

x(n) число способов для лесенки длины n
= есть
сначала на 1 ступенькиу и далее x(n-1) вариантов
2 ступеньки и x(т-2)
............................
k ступенек и x(n-k)
других способов нет.

x(1)=1 на лесенку в одну ступеньку можно забраться одним способом

[ros.pro]

2 evg_m, спасибо за ответ.
Сама суть формулы мне ясна. Мне не ясно как вычислить x(n-1), x(n-2), x(n-3) и т.д, чтобы в дальнейшем их подставить в формулу...

[evg_m]

Последовательность Фиббоначи вам говорит что нибудь.

начинаем сначала
x(0) =1
x(1) =x(0) =1
x(2) =x(1)+x(0) =2
.......
x(k) =x(k-1)+...+x(0)=
внимание теперь только К слагаемых
x(k+1)=чx(k+1-1)+...+x(k+1-k) = x(k)+...+x(1) =
...........
x(n-1) =
x(n)=

P.S. в классической последовательности Фиббоначи k=2

[ros.pro]

2 evg_m,
прошу простить мою глупость, но видимо я что-то не так понимаю. Не могли бы вы расписать полностью решение для k=3, n=4 ?

Я попытался, у меня получилось вот так:
k = 3, n = 4

x(0) = 1
x(1) = x(0) = 1
x(2) = x(0) + x(1) = 2
x(3) = x(1) + x(2) = 3

x(n) = x(n-1) + x(n-2) + x(n-3) + x(n-k) = x(3) + x(2) + x(1) + x(1) = 3 + 2 + 1 + 1 = 7

[evg_m]

Не могли бы вы расписать полностью решение для k=3, n=4 ?

попытался, у меня получилось вот так:
k = 3, n = 4

x(0) = 1 OK
x(1) = x(0) = 1 OK
x(2) = x(0) + x(1) = 2 OK
x(3) = x(0) +x(1) + x(2) = 3 слагаемых должно быть K =3 (забыли x(0) )

x(4) =x(1) +x(2) +x(3)
вообще классическая запись (от старших к младшим) не зря стала классикой в ней труднее запутаться
x(4)=x(3)+x(2)+x(1) пишем все подряд и останавливаемся как только есть нужное число слагаемых или больше нечего проибавлять.

[ros.pro]

2 evg_m, огромное вам спасибо!!! Без вас я бы не разобрался =)
Еще раз благодарю вас. Вы реально очень мне помогли.