Повышенный уровень, время –7 мин)
Повышенный уровень, время –7 мин)
Тема: динамическое программирование.
Что нужно знать:
· динамическое программирование – это способ решения сложных задач путем сведения их к более простым задачам того же типа
· с помощью динамического программирования решаются задачи, которые требуют полного перебор вариантов:
o «подсчитайте количество вариантов…»
o «как оптимально распределить…»
o «найдите оптимальный маршрут…»
· динамическое программирование позволяет ускорить выполнение программы за счет использования дополнительной памяти; полный перебор не требуется, поскольку запоминаются решения всех задач с меньшими значениями параметров
Пример задания:
Р-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 | |||||||||||||
| |
6) поскольку число 14 должно обязательно войти в траекторию, начинаем составлять вторую часть таблицы (до второй контрольной точки, 25) с этого числа заново, считая, что все ячейки для меньших чисел – нулевые
| N | ||||||||||||||||
| |
7) поскольку траектория не может проходить через 25, для N = 25 принимаем KN = 0 (в таблице эта ячейка выделена красным цветом)
8) дальше заполняем оставшиеся ячейки второй части таблицы обычным способом (см. задачи ниже):
| N | ||||||||||||||||
| |
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 | |||||||||||||||||||
| |
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 | ||||||||||
| |
7) второй этап – определяем таким же образом (и по таким же формулам!), сколько есть способов получить конечное число 21 из 10, только левую часть таблицы (от 1 до 10) мы уже не рассматриваем:
| N | ||||||||||||
| |
8) Ответ: 28.
Решение (вариант 2, А.Н. Носкин):
1) первый этап (п. 1-6) такой же, как и в первом варианте (см. выше);
2) на втором этапе используем такую идею: если мы знаем количество команд, с помощью которых из начального числа 1 можно получить 10 и определим количество команд, с помощью которых из 10 можно получить конечное значение 21, останется только перемножить эти два числа – это и будет ответ
3) составляем таблицу для получения 21 из 10, используя те же рекуррентные формулы:
| N | ||||||||||||
| |
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 | |||||||||
| |
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 | ||||||||||
| |
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 | ||||||||||||||||||||
| |
8) Заметим, что количество вариантов меняется только в тех столбцах, где N делится на 3, поэтому из всей таблицы можно оставить только эти столбцы:
| N | ||||||||
| |
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 может быть получено с помощью одной единственной (пустой) программы:
| Число | Как можно получить? | Количество программ |
3) число 2 не делится на 3, поэтому его можно получить только командой сложения (+1), значит, количество программ для 2 совпадает с количеством программ для 1:
| Число | Как можно получить? | Количество программ |
| +1 | = 1 |
4) число 3 делится на 3, поэтому его можно получить с помощью двух команд: +1 (из 2) и *3 (из 1):
| Число | Как можно получить? | Количество программ |
 |  1 | |
| +1 |  1 | |
| +1 *3 | 1 + 1 = 2 |
5) числа 4 и 5 не делятся на 3, поэтому их можно получить только с помощью команды +1, а число 6 может быть получено двумя командами:
| Число | Как можно получить? | Количество программ |
 +1 |  1 | |
| +1 *3 |  1 + 1 = 2 | |
| +1 |  2 | |
| +1 |  2 | |
| +1 *3 | 2 + 1 = 3 |
6) следующая группа – 7, 8 (не делятся на 3) и 9 (делится на 3):
| Число | Как можно получить? | Количество программ |
| +1 | ||
 +1 *3 |  1 + 1 = 2 | |
| +1 | ||
| +1 | ||
| +1 *3 |    2 + 1 = 3 | |
| +1 | ||
| +1 | ||
| +1 *3 | 3 + 2 = 5 |
7) далее – 10, 11 и 12:
| Число | Как можно получить? | Количество программ |
| +1 | ||
| +1 *3 | 1 + 1 = 2 | |
 +1 |  2 | |
| +1 | ||
| +1 *3 | 2 + 1 = 3 | |
| +1 | ||
| +1 | ||
| +1 *3 |  3 + 2 = 5 | |
| +1 |  5 | |
| +1 |  5 | |
| +1 *3 | 5 + 2 = 7 |
8) и так далее, вот полностью заполненная таблица (до конечного числа 20):
| Число | Как можно получить? | Количество программ |
| +1 | ||
| +1 *3 | 1 + 1 = 2 | |
| +1 | ||
 +1 |  2 | |
 +1 *3 |  2 + 1 = 3 | |
| +1 | ||
| +1 | ||
| +1 *3 | 3 + 2 = 5 | |
| +1 | ||
| +1 | ||
| +1 *3 | 5 + 2 = 7 | |
| +1 | ||
| +1 | ||
| +1 *3 | 7 + 2 = 9 | |
| +1 | ||
| +1 | ||
| +1 *3 | 9 + 3 = 12 | |
| +1 | ||
| +1 |
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 | – | ||
   2 | |||
| 1+1=2 | |||
 5 | |||
| 2+1=3 | |||
| 3 + 2=5 | |||
| 5 + 2 = 7 | |||
| 7 + 2 = 9 | |||
| 9+3 = 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
Умножь на 2
Сколько есть программ, которые число 1 преобразуют в число 16?
2) У исполнителя Калькулятор две команды, которым присвоены номера:
Прибавь 1
Умножь на 4
Сколько есть программ, которые число 1 преобразуют в число 55?
3) У исполнителя Калькулятор три команды, которым присвоены номера:
Прибавь 1
Умножь на 2
Умножь на 3
Сколько есть программ, которые число 1 преобразуют в число 18?
4) У исполнителя Калькулятор три команды, которым присвоены номера:
Прибавь 1
Умножь на 2
Умножь на 4
Сколько есть программ, которые число 1 преобразуют в число 17?
5) У исполнителя Калькулятор три команды, которым присвоены номера:
Прибавь 1
Умножь на 3
Умножь на 4
Сколько есть программ, которые число 1 преобразуют в число 25?
6) У исполнителя Калькулятор три команды, которым присвоены номера:
Прибавь 1
Прибавь 2
Умножь на 3
Сколько есть программ, которые число 1 преобразуют в число 12?
7) У исполнителя Калькулятор три команды, которым присвоены номера:
Прибавь 1
Прибавь 3
Умножь на 2
Сколько есть программ, которые число 1 преобразуют в число 15?
8) У исполнителя Калькулятор три команды, которым присвоены номера:
Прибавь 1
Прибавь 3
Умножь на 3
Сколько есть программ, которые число 1 преобразуют в число 15?
9) У исполнителя Калькулятор три команды, которым присвоены номера:
Прибавь 1
Прибавь 3
Умножь на 4
Сколько есть программ, которые число 1 преобразуют в число 18?
10) У исполнителя Калькулятор три команды, которым присвоены номера:
Прибавь 1
Прибавь 2
Умножь на 4
Сколько есть программ, которые число 1 преобразуют в число 13?
11) У исполнителя Калькулятор две команды, которым присвоены номера:
Прибавь 1
Умножь на 4
Сколько есть программ, которые число 1 преобразуют в число 32?
12) (С.Э. Назаренко) У исполнителя Калькулятор две команды, которым присвоены номера:
Прибавь 2
Умножь на 2
Сколько есть программ, которые число 1 преобразуют в число 24?
13) (С.Э. Назаренко) У исполнителя Калькулятор две команды, которым присвоены номера:
Прибавь 1
Умножь на 3
Сколько есть программ, которые число 5 преобразуют в число 49?
14) (С.Э. Назаренко) У исполнителя Калькулятор две команды, которым присвоены номера:
Прибавь 3
Умножь на 3
Сколько есть программ, которые число 5 преобразуют в число 27?
15) (С.Э. Назаренко) У исполнителя Калькулятор три команды, которым присвоены номера:
Прибавь 1
Прибавь 3
Умножь на 2
Сколько есть программ, которые число 3 преобразуют в число 15?
16) (Т.В. Белова) У исполнителя Калькулятор три команды, которым присвоены номера:
Прибавь 1
Умножь на 2
Возведи в квадрат
Сколько есть программ, которые число 2 преобразуют в число 38?
17) (Т.В. Белова) У исполнителя Калькулятор три команды, которым присвоены номера:
Прибавь 1
Прибавь 3
Возведи в квадрат
Сколько есть программ, которые число 2 преобразуют в число 19?
18) (Т.В. Белова) У исполнителя Калькулятор три команды, которым присвоены номера:
Прибавь 1
Умножь на 2
Возведи в квадрат
Сколько есть программ, которые число 2 преобразуют в число 27?
19) У исполнителя Калькулятор две команды, которым присвоены номера:
Прибавь 1
Увеличь число десятков на 1
Например: при помощи команды 2 число 23 преобразуется в 33. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется.
Сколько есть программ, которые число 11 преобразуют в число 27?
20) У исполнителя Калькулятор две команды, которым присвоены номера:
Прибавь 1
Увеличь число десятков на 1
Например: при помощи команды 2 число 23 преобразуется в 33. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется.
Сколько есть программ, которые число 12 преобразуют в число 36?
21) У исполнителя Калькулятор две команды, которым присвоены номера:
Прибавь 1
Прибавь 1
Прибавь 1
Прибавь 1
Увеличь число десятков на 1
Например: при помощи команды 2 число 23 преобразуется в 33. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется.
Сколько есть программ, которые число 10 преобразуют в число 33?
25) У исполнителя Калькулятор две команды, которым присвоены номера:
Прибавь 2
Умножь на 2
Сколько есть программ, которые число 2 преобразуют в число 40?
26) У исполнителя Калькулятор две команды, которым присвоены номера:
Прибавь 3
Умножь на 2
Сколько есть программ, которые число 3 преобразуют в число 42?
27) У исполнителя Калькулятор две команды, которым присвоены номера:
Прибавь 1
Прибавь 3
Сколько есть программ, которые число 1 преобразуют в число 15?
28) У исполнителя Калькулятор две команды, которым присвоены номера:
Прибавь 1
Прибавь 3
Сколько есть программ, которые число 7 преобразуют в число 20?
29) У исполнителя Калькулятор три команды, которым присвоены номера:
Прибавь 1
Умножь на 2
Умножь на 3
Сколько есть программ, которые число 1 преобразуют в число 14?
30) У исполнителя Калькулятор две команды, которым присвоены номера:
Прибавь 2
Умножь на 3
Сколько есть программ, которые