У исполнителя Удвоитель две команды, которым присвоены номера:
1. прибавь 1,
2. умножь на 2.
Первая из них увеличивает число на экране на 1, вторая удваивает его.
Программа для Удвоителя — это последовательность команд.
Сколько есть программ, которые число 7 преобразуют в число 21?
Числа 8, 9, 10, 11, 12, 13 получаются из числа 7 единственным образом: постепенным прибавлением единиц. Число 14 из числа 7 можно получить двумя способами: либо прибавлением единиц, либо удвоением числа 7. Число 15 из числа 14 получается единственным образом, а из числа 7 двумя: последовательным прибавлением единиц или удвоением числа 7 и прибавлением единицы. Число 16 можно получить тремя способами: либо удвоением числа 8 (которое получается из 7 единственным способом), либо прибавлением единицы к числу 15 (получаемому двумя способами). Аналогично продолжая рассуждения, мы видим, что до числа 27 при каждом чётном числе количество программ увеличивается на единицу, а при нечётном числе увеличения не происходит.
Построим таблицу, в которой запишем число программ (S) , которыми можно получить с помощью Удвоителя число n из числа 7: