Вопрос B13

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

1. прибавь 1,

2. умножь на 2.

Первая из них увеличивает на 1 число на экране, вторая удваивает его. Программа для Удвоителя – это последовательность команд.

Сколько есть программ, которые число 2 преобразуют в число 25?

Для решения задачи будем считать число программ, позволяющих получить число 25 из чисел от 24 до 2  последовательно.

Над каждым числом в последовательности чисел, представленной выше, будем записывать цифру, означающую,  сколько существует программ получения числа 25 из данного числа.

Ясно что для чисел от 24 до 13 существует только единственная программа получения числа 25 с помощью команды "прибавь  1", так как команда  "умножь на 2"  приведет к получению числа >25.

Из числа 12 число 25 можно получить не только последовательным выполнением команды "прибавь 1", но также командой "умножь на 2" числа 12.

Следовательно существует 2 способа (или 2 программы) получения числа 25 из числа 12

Для всех остальных чисел количество программ получения числа 25 складывается из числа программ последователя + число программ получения числа 25 для числа, являющегося

результатом применения к исходному числу команды

«умножь на 2».

Ответ:  существует 47 программ, содержащих команды «прибавь 1» и «умножь на 2», преобразующих число 2 в число 25.