2020-08-05
163
Повышенный уровень, время –7 мин)
Тема: динамическое программирование.
Что нужно знать:
· динамическое программирование – это способ решения сложных задач путем сведения их к более простым задачам того же типа
· с помощью динамического программирования решаются задачи, которые требуют полного перебор вариантов:
o «подсчитайте количество вариантов…»
o «как оптимально распределить…»
o «найдите оптимальный маршрут…»
· динамическое программирование позволяет ускорить выполнение программы за счет использования дополнительной памяти; полный перебор не требуется, поскольку запоминаются решения всех задач с меньшими значениями параметров
Пример задания:
Р-08 (демо-вариант 2018 г.). Исполнитель М17 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
Прибавить 1
Прибавить 2
Умножить на 3
Первая команда увеличивает число на экране на 1, вторая – увеличивает его на 2, а третья – умножает его на 3. Программа для исполнителя М17 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 12 и при этом траектория вычислений содержит числа 8 и 10?
|
|
|
Решение:
1) запишем рекуррентную формулу для вычисления 
– количества возможных программ для получения числа N из некоторого начального числа:
, если N не делится на 3
, если N делится на 3
2) все допустимые программы можно разбить на 3 части:
– переход от 2 до 8
– переход от 8 до 10
– переход от 10 до 12
3) обозначим через 
количеств возможных программ получения числа b из числа a
4) очевидно, что 
для любого c, такого что a < c < b
5) поэтому 
6) вычисляем эти значения отдельно стандартным способом по рекуррентным формулам п. 1:
| N | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| KN | 1 | 1 | 2 | 3 | 6 | 9 | 15 |
| N | 8 | 9 | 10 | 10 | 11 | 12 | |
| KN | 1 | 1 | 2 | 1 | 1 | 2 |
7) и перемножаем: 15 × 2 × 2 = 60
8) Ответ: 60.
Ещё пример задания:
Р-07. Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
Прибавить 1
Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25?
Решение:
1) у нас в задании две особые точки – числа 14 (через которое должна проходить траектория) и 25 (а сюда она попасть НЕ должна)
2) сначала, так же, как и в задачах, рассмотренных ниже, составляем рекуррентную формулу, по которой будем вычислять количество обозначить количество разных программ для получения числа N из начального числа:
|
|
|
3) число N могло быть получено одной из двух операций:
- увеличением на 1 числа N-1;
- умножением на 2 числа N/2 (только для N, которые делятся на 2);
для нечётных чисел
для чётных чисел
4) для начального числа 2 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; 
.
5) составляем таблицу до первой особой точки – числа 14:
| N | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|
| 1 | 1 | 2 | 2 | 3 | 3 | 5 | 5 | 7 | 7 | 10 | 10 | 13 |
6) поскольку число 14 должно обязательно войти в траекторию, начинаем составлять вторую часть таблицы (до второй контрольной точки, 25) с этого числа заново, считая, что все ячейки для меньших чисел – нулевые
| N | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 |
|
| 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 0 |
7) поскольку траектория не может проходить через 25, для N = 25 принимаем KN = 0 (в таблице эта ячейка выделена красным цветом)
8) дальше заполняем оставшиеся ячейки второй части таблицы обычным способом (см. задачи ниже):
| N | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 |
|
| 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 0 | 0 | 0 | 13 | 13 |
9) Ответ: 13.
Ещё пример задания:
Р-06. У исполнителя Удвоитель две команды, которым присвоены номера:
Прибавить 1
Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Удвоитель – это последовательность команд. Сколько существует программ, преобразующих число 4 в число 24, предпоследней командой которых является команда «1»?
Решение:
1) итак, мы знаем предпоследнюю команду – 1, при этом последняя команда может быть любая – 1 или 2
2) выходит, что нужно получить количество всех программ вида «*11» и «*12», где звёздочка обозначает любые команды
3) если программа заканчивается на «11», то до выполнения цепочки «11» у нас было число
24 – 1 – 1 = 22; поэтому нужно найти число программ для преобразования 4 в 22
4) для начального числа 1 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через обозначить количество разных программ для получения числа N из начального числа 1, то .
5) теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую с предыдущими элементами последовательности 
, то есть с решениями таких же задач для меньших N
6) число N могло быть получено одной из двух операций:
- увеличением на 1 числа N-1;
- умножением на 2 числа N/2 (только для N, которые делятся на 2, и таких, что N/2 ³ 4);
для нечётных чисел
для чётных чисел, таких, что N/2 ³ 4
7) составляем таблицу:
| N | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
|
| 1 | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 | 7 | 7 | 9 | 9 | 12 | 12 | 15 |
8) теперь рассматриваем случай, когда программа заканчивается на «12», это значит, что до выполнения цепочки «12» у нас было число (24/ 2) – 1 = 11; поэтому нужно найти число программ для преобразования 4 в 11, берём его из таблицы: 3
9) ответ к задаче – сумма двух значений, выделенных жёлтым маркером: 15 + 3 = 18, поскольку мы рассмотрели все варианты программ, в которых предпоследняя команда – 1
10) Ответ: 18.
Ещё пример задания:
Р-05. Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
Прибавить 1
Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 21 и при этом траектория вычислений содержит число 10? Траектория вычислений программы – это последовательность результатов
выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
|
|
|
Решение (вариант 1):
1) заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться)
2) для начального числа 1 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через обозначить количество разных программ для получения числа N из начального числа 1, то .
3) теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую с предыдущими элементами последовательности , то есть с решениями таких же задач для меньших N
4) число N могло быть получено одной из двух операций:
- увеличением на 1 числа N-1;
- умножением на 2 числа N/2 (только для N, которые делятся на 2);
для нечётных чисел
для чётных чисел
5) поскольку траектория должна проходить через число 10, сначала выясняем, сколькими способами можно получить 10 из 1, а затем будем считать, сколько есть способов получить 21 из 10
6) заполняем таблицу от 1 до 10 по полученным формулам:
| N | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|
| 1 | 2 | 2 | 4 | 4 | 6 | 6 | 10 | 10 | 14 |
7) второй этап – определяем таким же образом (и по таким же формулам!), сколько есть способов получить конечное число 21 из 10, только левую часть таблицы (от 1 до 10) мы уже не рассматриваем:
| N | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
|
| 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 28 | 28 |
8) Ответ: 28.
Решение (вариант 2, А.Н. Носкин):
1) первый этап (п. 1-6) такой же, как и в первом варианте (см. выше);
2) на втором этапе используем такую идею: если мы знаем количество команд, с помощью которых из начального числа 1 можно получить 10 и определим количество команд, с помощью которых из 10 можно получить конечное значение 21, останется только перемножить эти два числа – это и будет ответ
3) составляем таблицу для получения 21 из 10, используя те же рекуррентные формулы:
| N | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 |
4) результат – 14 ´ 2 = 28
5) Ответ: 28.
Ещё пример задания:
Р-04. Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя
три команды, которым присвоены номера:
|
|
|
Прибавь 1
Прибавь 2
Прибавь следующее
Первая из них увеличивает число на экране на 1, вторая увеличивает это число на 2, а третья прибавляет к числу на экране число, большее на 1 (к числу 3 прибавляется 4, к числу 9 прибавляется 10 и т. д.). Программа для исполнителя Калькулятор– это последовательность команд. Сколько есть программ, которые число 2 преобразуют в число 10?
Решение (1 способ, составление таблицы):
1) заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться)
2) для начального числа 2 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через обозначить количество разных программ для получения числа N из начального числа 2, то 
.
3) теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую 
с предыдущими элементами последовательности , то есть с решениями таких же задач для меньших N
4) число N могло быть получено одной из трёх операций сложения:
- увеличением на 1 числа N-1;
- увеличением на 2 числа N-2;
- из некоторого числа X увеличением на X+1 (следующее число), так что N = X + X + 1, откуда X = (N – 1) / 2; так могут быть получены только нечетные числа;
поэтому
для чётных чисел
для нечётных чисел
5) остается по этой формуле заполнить таблицу для всех значений от 2 до 10:
| N | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|
| 1 | 1 | 2 | 4 | 6 | 11 | 17 | 30 | 47 |
6) ответ – 47.
Ещё пример задания:
Р-03. Исполнитель Май4 преобразует число, записанное на экране. У исполнителя
три команды, которым присвоены номера:
Прибавь 1
Прибавь 2
Прибавь 4
Первая из них увеличивает число на экране на 1, вторая увеличивает это число на 2, а третья – на 4. Программа для исполнителя Май4 – это последовательность команд. Сколько есть программ, которые число 21 преобразуют в число 30?
Решение (1 способ, составление таблицы):
7) заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться)
8) все числа, меньшие начального числа 21, с помощью этого исполнителя получить нельзя, для них количество программ будет равно 0
9) для начального числа 21 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через 
обозначить количество разных программ для получения числа N из начального числа 21, то 
.
10) теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую 
с предыдущими элементами последовательности , то есть с решениями таких же задач для меньших N
11) любое число N > 21 могло быть получено одной из трёх операций сложения соответственно из чисел N-1, N-2 и N-4, поэтому
12) остается по этой формуле заполнить таблицу для всех значений от 21 до 30:
| N | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
|
| 1 | 1 | 2 | 3 | 6 | 10 | 18 | 31 | 55 | 96 |
13) ответ – 96.
Ещё пример задания:
Р-02. У исполнителя Утроитель две команды, которым присвоены номера:
Прибавь 1
Умножь на 3
Первая из них увеличивает число на экране на 1, вторая – утраивает его.
Программа для Утроителя – это последовательность команд.
Сколько есть программ, которые число 1 преобразуют в число 20?
Решение (1 способ, составление таблицы):
1) заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться)
2) начнем с простых случаев, с которых будем начинать вычисления: для чисел 1 и 2, меньших, чем 3, существует только одна программа, состоящая только из команд сложения; если через обозначить количество разных программ для получения числа N из 1, то 
.
3) теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую с предыдущими элементами последовательности 
, то есть с решениями таких же задач для меньших N
4) если число N не делится на 3, то оно могло быть получено только последней операцией сложения, поэтому 
5) если N делится на 3, то последней командой может быть как сложение, так и умножение
6) поэтому для получения нужно сложить 
(количество программ с последней командой сложения) и 
(количество программ с последней командой умножения). В итоге получаем:
если N не делится на 3:
если N делится на 3: 
7) остается заполнить таблицу для всех значений от 1 до N:
| N | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
|
| 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 5 | 5 | 5 | 7 | 7 | 7 | 9 | 9 | 9 | 12 | 12 | 12 |
8) Заметим, что количество вариантов меняется только в тех столбцах, где N делится на 3, поэтому из всей таблицы можно оставить только эти столбцы:
| N | 1 | 3 | 6 | 9 | 12 | 15 | 18 | 21 |
|
| 1 | 2 | 3 | 5 | 7 | 9 | 12 | 15 |
9) заданное число 20 попадает в последний интервал (от 18 до 21), поэтому …
10) ответ – 12.
Решение (2 способ, подстановка – вычисления по формулам «с конца»):
1) п. 1-6 выполняются так же, как и при первом способе; главная задача – получить рекуррентную формулу:
если N не делится на 3: 
если N делится на 3:
с начальными условиями 
2) начинаем с заданного конечного числа 20; применяем первую формулу (
), пока не дойдем до числа, делящегося на 3 (это 18):
3) далее применяем вторую формулу ():
4) применяем первую формулу для 17:
5) применяем вторую формулу для обоих слагаемых:
где учтено, что 
6) с помощью первой формулы переходим в правой части к числам, делящимся на 3:
а затем применяем вторую формулу для каждого слагаемого
7) снова используем первую формулу
а затем – вторую:
8) и еще раз
9) ответ – 12.
Решение (3 способ, О.В. Шецова, лицей № 6, г. Дубна):
1) будем составлять таблицу из трех столбцов: в первом записывается получаемое число от 1 до 20, во втором – какой последней командой может быть получено это число, а в третьем вычисляем количество различных программ для получения этого числа из 1
2) очевидно, что число 1 может быть получено с помощью одной единственной (пустой) программы:
| Число | Как можно получить? | Количество программ |
| 1 | 1 |
3) число 2 не делится на 3, поэтому его можно получить только командой сложения (+1), значит, количество программ для 2 совпадает с количеством программ для 1:
| Число | Как можно получить? | Количество программ |
| 1 | 1 | |
| 2 | +1 | = 1 |
4) число 3 делится на 3, поэтому его можно получить с помощью двух команд: +1 (из 2) и *3 (из 1):
| Число | Как можно получить? | Количество программ |
| 1 | 
|  1
|
| 2 | +1 |  1
|
| 3 | +1 *3 | 1 + 1 = 2 |
5) числа 4 и 5 не делятся на 3, поэтому их можно получить только с помощью команды +1, а число 6 может быть получено двумя командами:
| Число | Как можно получить? | Количество программ |
| 1 | 1 | |
| 2 |  +1
|  1
|
| 3 | +1 *3 |  1 + 1 = 2
|
| 4 | +1 |  2
|
| 5 | +1 |  2
|
| 6 | +1 *3 | 2 + 1 = 3 |
6) следующая группа – 7, 8 (не делятся на 3) и 9 (делится на 3):
| Число | Как можно получить? | Количество программ |
| 1 | 1 | |
| 2 | +1 | 1 |
| 3 |  +1 *3
|  1 + 1 = 2
|
| 4 | +1 | 2 |
| 5 | +1 | 2 |
| 6 | +1 *3 |    2 + 1 = 3
|
| 7 | +1 | 3 |
| 8 | +1 | 3 |
| 9 | +1 *3 | 3 + 2 = 5 |
7) далее – 10, 11 и 12:
| Число | Как можно получить? | Количество программ |
| 1 | 1 | |
| 2 | +1 | 1 |
| 3 | +1 *3 | 1 + 1 = 2 |
| 4 |  +1
|  2
|
| 5 | +1 | 2 |
| 6 | +1 *3 | 2 + 1 = 3 |
| 7 | +1 | 3 |
| 8 | +1 | 3 |
| 9 | +1 *3 |  3 + 2 = 5
|
| 10 | +1 |  5
|
| 11 | +1 |  5
|
| 12 | +1 *3 | 5 + 2 = 7 |
8) и так далее, вот полностью заполненная таблица (до конечного числа 20):
| Число | Как можно получить? | Количество программ |
| 1 | 1 | |
| 2 | +1 | 1 |
| 3 | +1 *3 | 1 + 1 = 2 |
| 4 | +1 | 2 |
| 5 |  +1
|  2
|
| 6 |  +1 *3
|  2 + 1 = 3
|
| 7 | +1 | 3 |
| 8 | +1 | 3 |
| 9 | +1 *3 | 3 + 2 = 5 |
| 10 | +1 | 5 |
| 11 | +1 | 5 |
| 12 | +1 *3 | 5 + 2 = 7 |
| 13 | +1 | 7 |
| 14 | +1 | 7 |
| 15 | +1 *3 | 7 + 2 = 9 |
| 16 | +1 | 9 |
| 17 | +1 | 9 |
| 18 | +1 *3 | 9 + 3 = 12 |
| 19 | +1 | 12 |
| 20 | +1 | 12 |
9) ответ – количество программ, с помощью которых можно получить число 20 из 1, – считываем из последней ячейки третьего столбца
10) ответ – 12.
Решение (4 способ, М.В. Кузнецова и её ученики, г. Новокузнецк):
1) пусть 
– искомое конечное число, 
количества программ получения числа
2) тогда для построения рекуррентной формулы определения , нужно знать 2 факта:
а) какой может быть последняя команда и сколько есть видов этого последнего действия?
б) для каждого «последнего» действия нужно знать число программ получения предыдущего числа, сумма этих количеств и есть искомое значение – число программ получения числа .
Например, общее количество программ получения числа 6 с помощью Утроителя равно 
, т.к. есть ДВА способа завершения программ получения этого значения: 6=5+1 и 6=2∙3.
3) число программ получения числа зависит от числа программ получения предыдущего значения, и что программы получения чисел, кратных 3-м могут завершаться 2-мя способами: 
или 
, а все остальные числа получают только первым способом: .
4) составим рекуррентную формулу для определения числа программ получения числа :
при 
имеем 
если не кратно 3: 
если делится на 3: 
5) с помощью это формулы заполняем таблицу следующим образом:
– в первом столбце записываем все натуральные числа от 1 до заданного ;
– во втором столбце – числа, на единицу меньшие (из которых может быть получено последней операцией сложения с 1);
– в третьем столбце для чисел, кратных 3-м, записываем частное от деления числа, записанного в первом столбце, на 3 (из этого числа может быть получено последней операцией умножения на 3);
– в последнем столбце вычисляем , складывая соответствующие значения для тех строк, номера которых записаны во втором и третьем столбцах:
| N | N-1 | N/3 | K(N) |
  1
| – | 1 | |
   2
| 1 | 1 | |
| 3 | 2 | 1 | 1+1=2 |
| 4 | 3 | 2 | |
 5
| 4 | 2 | |
| 6 | 5 | 2 | 2+1=3 |
| 7 | 6 | 3 | |
| 8 | 7 | 3 | |
| 9 | 8 | 3 | 3 + 2=5 |
| 10 | 9 | 5 | |
| 11 | 10 | 5 | |
| 12 | 11 | 4 | 5 + 2 = 7 |
| 13 | 12 | 7 | |
| 14 | 13 | 7 | |
| 15 | 14 | 5 | 7 + 2 = 9 |
| 16 | 15 | 9 | |
| 17 | 16 | 9 | |
| 18 | 17 | 6 | 9+3 = 12 |
| 19 | 18 | 12 | |
| 20 | 19 | 12 |
6) ответ – 12.
Решение (5 способ, А. Сидоров):
1) основная идея – число программ, преобразующих начальное число 1 в конечное 20 с помощью заданных в условии команд, равно числу программ, преобразующих конечное число 20 в начальное 1 с помощью обратных команд: «вычти 1» и «раздели на 3»
2) будем строить «обратное дерево» – дерево всех способов преобразования конечного числа в начальное; это лучше (в сравнении с построением «прямого» дерева, от начального числа к конечному), потому что операция умножения необратима – каждое число можно умножить на 3, но не каждое можно разделить на 3; из-за этого сразу отбрасываются тупиковые ветви, не дающие новых решений
3) рисуем сокращенное дерево, в котором черные стрелки показывают действие первой команды («прибавь 1»), а красные – действие второй команды («умножь на 3»); красные стрелки подходят только к тем числам, которые делятся на 3:
4) чтобы получить количество программ для каждого числа из верхней строки, нужно сложить соответствующие количества программ для всех чисел из нижнего ряда, которые не больше данного (программы с умножением), и добавить 1 (программа, состоящая из одних сложений)
5) очевидно, что для получения 1 существует одна (пустая) программа; тогда для числа 2 тоже получается одна программа, а для числа 3 – две программы:
6) далее, для чисел 4 и 5 получаем 2 программы (после числа 3 нет «разветвлений» – подходящих красных стрелок), а для числа 6 – 3 программы, так как «подошло» еще одно разветвление (6 можно получить умножением 2 на 3), а для числа 2 мы уже подсчитали количество программ – оно равно 1:
7) находить число программ для следующих чисел нам уже не понадобится, потому что при умножении на 3 они дают числа, большие, чем заданное конечное число 20
8) запишем полученные результаты в самой нижней строке для всех множителей от 1 до 6:
9) теперь остается сложить все числа в скобках в нижнем ряду (количество программ с командами умножения) и добавить 1 (одна программа, состоящая только из команд сложения):
3 + 2 + 2 + 2 + 1 + 1 + 1 = 12
10) ответ – 12.
Возможные проблемы:
· неверно определенные начальные условия
· неверно выведенная рекуррентная формула
· ошибки при заполнении таблицы (невнимательность)
· второй способ (подстановка), как правило, приводит к бОльшему количеству вычислений; конечно, можно отдельно выписывать все полученные ранее значения  , но тогда мы фактически придем к табличному методу
|
Еще пример задания:
Р-01. У исполнителя Калькулятор две команды, которым присвоены номера:
Прибавь 1
увеличь вторую с конца цифру на 1
Первая из них увеличивает число на экране на 1, вторая – увеличивает на 1 число десятков. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется. Программа для Калькулятора – это последовательность команд.
Сколько есть программ, которые число 15 преобразуют в число 28?
Решение (1 способ, составление таблицы):
1) заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться)
2) при заданных командах очередное число N может быть получено двумя способами:
3) увеличением на 1 (для всех чисел, больших начального числа)
4) увеличением числа десятков на 1 (то есть, фактически командой «+10») – для всех чисел, больших или равных 25; например, число 24 не может быть получено этой командой (14 + 10 = 24), потому что число 14 меньше, чем начальное значение 15
5) таким образом, рекуррентные формулы принимают вид
для всех чисел, меньших, чем 25
для чисел, больших или равных 25
6) других способов получения числа с помощью исполнителя с заданными командами нет, то есть мы таким образом рассматриваем все возможные программы
7) начальное значение: 
(число 15 можно получить единственной пустой программой)
8) далее заполняем таблицу:
| 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 3 | 4 | 5 |
9) Ответ: 5
Еще пример задания:
Р-00. У исполнителя Калькулятор две команды, которым присвоены номера:
Прибавь 1
