У исполнителя Удвоитель2 две команды, которым присвоены номера: прибавь 2, умножь на 2. Первая из них увеличивает на 2 число на экране, вторая удваивает его. Программа для Удвоителя2 – это последовательность... | Яндекс.Репетитор

Задание#T13819

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

прибавь 2,
умножь на 2.

Первая из них увеличивает на число на экране, вторая удваивает его.

Программа для Удвоителя2 – это последовательность команд.

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

Показать разбор и ответ

Очевидно, что из числа можно получить только четные числа, поэтому нечетные числа можно не рассматривать. Будем решать поставленную задачу последовательно для чисел

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

Количество программ, которые преобразуют число в число будем обозначать через

Число у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше Значит,

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

Число

Из чего получается

Количество программ

Число
Из чего получается
Количество программ

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