Динамическое программирование. Задание №22

Основные понятия
динамическое программирование – это способ решения сложных задач путем сведения их к более простым задачам того же типа
с помощью динамического программирования решаются задачи, которые требуют полного перебор вариантов:
«подсчитайте количество вариантов…»
«как оптимально распределить…»
«найдите оптимальный маршрут…»

Задание №22
Проверяемые элементы:
умение анализировать результат исполнения алгоритма
Уровень сложности:
профильный
Примерное время выполнения:
7 мин.
Средний процент выполнения задания
в 2016 г. – 38,2%

У исполнителя Увеличитель две команды, которым присвоены номера: 1. прибавь 1, 2. умножь на 2.
Первая из них увеличивает число на экране на 1, вторая – умножает его на 2. Программа для Увеличителя – это последовательность команд. Сколько есть программ, которые число 3 преобразуют в число 23?
Краткая запись условия
Команды
1) N= x+1
2) N= x*2
Начальное число
3
Конечное число
23
траектория
Пример №1

1 способ – выписать все нужные программы, построить дерево программ.
2 способ – подсчитать число программ, не выписывая их явно, а написав формулу, которая позволяет найти количество программ получения данного числа, если уже известно количество программ для получения меньших чисел (при таком решении удобно заполнять таблицу).
Способы решения задания

Дерево возможных путей вычислений
1 способ

У исполнителя Увеличитель две команды, которым присвоены номера: 1. прибавь 1, 2. умножь на 2.
Первая из них увеличивает число на экране на 1, вторая – умножает его на 2. Программа для Увеличителя – это последовательность команд. Сколько есть программ, которые число 3 преобразуют в число 23?
2 способ
Краткая запись условия:
3 → 23
N= x + 1
N= x*2
Обратные команды:
1) x = N – 1
2) x = N/2

1
1
1+1= 2
2
2 +1= 3
3
3 +1 =4
4
4+ 2 =6
6
6+ 2 =8
8
8+3 = 11
14+4=18
18
18+4=22
22
Ответ: 22
2 способ
14
11+3=14
11

Исполнитель А12S преобразует целое число, записанное на экране. У исполнителя три команды, каждой команде присвоен номер:
1. Прибавь 1 2. Прибавь 2 3. Прибавь предыдущее
Первая команда увеличивает число на экране на 1, вторая увеличивает это число на 3, третья прибавляет к числу на экране число, меньшее на 1 (к числу 3 прибавляется 2, к числу 11 прибавляется 10 и т. д.). Программа для исполнителя А12S – это последовательность команд.
Сколько существует программ, которые число 3 преобразуют в число 10?
3 → 10
N= x + 1
N=x + 2
N=x + (x-1)
Обратные команды:
x= N – 1
X=N – 2
X=(N+1)/2
Пример 2
Проверить таблицу

Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25?
2 → 29
Траектория: Содержит 14
Не содержит 29
N= x + 1
N=x *2
Обратные команды:
x= N – 1
X=N/2
Пример 3