Задача 4.
Фишка может двигаться по полю длины N только вперед. Длина хода фишки не более K. Найти число различных путей, по которым фишка может пройти поле от начала до конца.
Пример. N=3, K=2
Возможные пути:
1,1,1
1,2
2,1
Ответ: 3.
|
Решение задачи 4.
Очевидное решение задачи предполагает разложение числа N на всевозможные суммы таким образом, чтобы каждое слагаемое в сумме не превосходило k. Очевидно, что таких разложений очень много, особенно если учитывать, порядок слагаемых в разложении существенен, так как он соответствует различной последовательности ходов фишки.
Обозначим через S(i) количество различных путей, по которым фишка может пройти поле от начала до позиции с номером i. Предположим теперь, что для любого j от 1 до i известны значения величин S(j). Задача состоит в определении правила вычисления значения S(i+1), используя значения известных величин. Легко заметить, что в позицию с номером i+1 фишка может попасть из позиций i, i-1,...,i-k. Следовательно,
S(i+1)=S(i)+S(i-1)+...+S(i-k).
Таким образом, вычисляя последовательно значения величин S(1), S(2),..., S(N) по описанному выше правилу, получаем значение S(N), которое и указывает общее количество различных путей, по которым фишка может пройти поле от начала до позиции с номером N.
|
