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

Question

У ис­пол­ни­те­ля Три­тон две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:
1. при­бавь 1,
2. при­бавь 3.
Пер­вая из них уве­ли­чи­ва­ет на 1 число на экра­не, вто­рая уве­ли­чи­ва­ет это число на 3. Про­грам­ма для Три­то­на — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко су­ще­ству­ет про­грамм, ко­то­рые число 22 пре­об­ра­зу­ют в число 35?

Answer 1

Пусть #(N) - число программ, которыми можно получить число N из числа 22. Первые значения этой последовательности такие:
#(22) = 1 - только пустая программа
#(23) = 1 - только программа 1
#(24) = 1 - только программа 11
Дальше так: любое число N можно получить либо из числа N - 3 добавлением тройки, либо из числа N - 1 добавлением единицы. Поэтому #(N) = #(N - 1) + #(N - 3).
#(25) = #(24) + #(22) = 1 + 1 = 2
#(26) = 2 + 1 = 3
#(27) = 3 + 1 = 4
#(28) = 4 + 2 = 6
#(29) = 9
Дальше будут числа 13, 19, 28, 41, 60, 88.

Ответ: 88.