Текстовые решения некоторых заданий

Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2
Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 35, при этом траектория вычислений содержит число 10 и не содержит 17?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ABA при исходном числе 7 траектория будет состоять из чисел 8, 16, 17

Решение задачи сводится к тому, что мы подсчитываем сколькими способами можно попасть в текущее число из 1. В 2 можно попасть двумя способами, 1+1 и 1*2. В тройку можно попасть тоже двумя способами 1+1+1 и 1*2+1, т.е. в тройку можно попасть одним способом из двойки, а в двойку можно было попасть двумя способами. В четверку можно попасть из 3, и из 2, 3+1 и 2*2. В двойку можно было попасть двумя способами, в тройку также можно было попасть двумя способами, следовательно в четверку можно попасть четырьмя способами. Т.о. количество способов которыми можно попасть в некоторое число, равно сумме способов которыми можно попасть в те числа, из которых можно попасть в текущее.

В этот момент необходимо остановиться, т.к. по условию задачи необходимо проходить через число 10, т.е. вариантов как добраться до числа 11 у нас 14, только из 10, а в число 12 мы могли бы попасть как из 6, так и из 11, но из 6 нельзя, потому что тогда мы не пройдем через число 10. По сути нам нужно построить новую табличку, которая начинается с числа 10, и попасть в него у нас есть 14 способов, и начать заполнять уже эту табличку.

Т.о. в число 35 можно попасть 98 способами.

Ответ: 98