Сколько существует таких программ, которые исходное число 3 преобразуют в число 12 и при этом траектория вычислений программы содержит число 10?
Демонстрационный вариант ЕГЭ 2017 по информатике – задание №22.
Исполнитель А16 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 2
Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2,третья умножает его на 2.
Программа для исполнителя А16 – это последовательность команд.
Сколько существует таких программ, которые исходное число 3 преобразуют в число 12 и при этом траектория вычислений программы содержит число 10?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.
Решение:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 2
Разобъём задачу на 2 этапа: получить из 3 — 10 и получить из 10 — 12
1) Из 3 — 10
4 из 3 можем получить только 1 способом: 3+1=4 (1 способ)
5 из 3 можем получить 2 способами: 4+1 (1) и 3+2 (1) (2 способа)
6 из 3 можем получить 4 способами: 5+1 (2); 4+2 (1) и 3*2 (1) (4 способа)
7 из 3 можем получить 6 способами: 6+1 (4); 5+2 (2) (6 способов)
8 из 3 можем получить 11 способами: 7+1 (6); 6+2 (4) и 4*2 (1) (11 способов)
9 из 3 можем получить 17 способами: 8+1 (11); 7+2 (6) (17 способов)
10 из 3 можем получить 30 способами: 9+1 (17); 8+2 (11) и 5*2 (2) (30 способов)
2) Из 10 — 12
12 из 10 можно получить 2 способами:
- Сразу 12 из 10: 10+2
- Сначала получаем 11: 10+1, потом 12 из 11: 11+1
10 из 3 можем получить 30 способами, 12 из 10 можно получить 2 способами:
2*30=60
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 1 | 1 | ||||||||
| 1 | 1 | 2 | |||||||
| 1 | 1 | 2 | 4 | ||||||
| 2 | 4 | 6 | |||||||
| 1 | 4 | 6 | 11 | ||||||
| 6 | 11 | 17 | |||||||
| 2 | 11 | 17 | 30 | ||||||
| 30 | 30 | ||||||||
| 30 | 30 | 60 |
Ответ: 60