Question

У Исполнителя две команды, которым присвоены номера:
1. прибавь 2,
2. прибавь 5.

Первая из них увеличивает число на экране на 2, вторая увеличивает его на 5. Программа для Увеличителя — это последовательность команд.
Сколько есть программ, которые число 1 преобразуют в число 21?

Answer 1

Ответ:

23

Объяснение:

Пусть

n - число

f(n) - сколькими способами его можно получить из 1

f(n) = f(n - 2) + f(n - 5)

т.к число n можно получить из n - 2 и это f(n - 2) способа или из n - 5 и это f(n -5) способов

f(1) = 1 (пустая программа)

f(2) = 0

f(3) = 1

f(4) = 0

f(5) = 1

f(6) = 1

f(7) = 1

f(8) = 2

f(9) = 1

f(10) = 3

f(11) = 2

f(12) = 4

f(13) = 4

f(14) = 5

f(15) = 7

f(16) = 7

f(17) = 11

f(18) = 11

f(19) = 16

f(20) = 18

f(21) = 23