Исполнитель Май15 преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Май15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Решение:
Разобъём задачу на 2 этапа: получить из 2 — 14 и получить из 14 — 29
1) Из 2 — 14
3 из 2 можем получить только 1 способом: 2+1=3 (1 способ)
4 из 2 можем получить 2 способами: 3+1 (1) и 2*2 (1) (2 способа)
5 из 2 можем получить 2 способами: 4+1 (2) (2 способа)
6 из 2 можем получить 3 способами: 5+1 (2) и 3*2 (1) (3 способа)
7 из 2 можем получить 3 способами: 6+1 (3) (3 способа)
8 из 2 можем получить 5 способами: 7+1 (3) и 4*2 (2) (5 способов)
9 из 2 можем получить 5 способами: 8+1 (5) (5 способов)
10 из 2 можем получить 7 способами: 9+1 (5) и 5*2 (2) (7 способов)
11 из 2 можем получить 5 способами: 10+1 (7) (7 способов)
12 из 2 можем получить 10 способами: 11+1 (7) и 6*2 (3) (10 способов)
13 из 2 можем получить 10 способами: 12+1 (10) (10 способов)
14 из 2 можем получить 13 способами: 12+1 (10) и 7*2 (3) (13 способов)
2) Из 14 — 29
Траектория вычислений не содержит числа 25, значит, 29 из 14 мы не можем получить, используя только команду №1 ( Прибавить 1).
Поэтому для получения 29 из 14, мы 14 умножаем на 2 и прибавляем 1:
14*2=28 (1 способ)
28+1=19(1 способ)
14 из 2 можем получить 13 способами, 29 из 14 можно получить 1 способом:
13*1=13
Ответ:13