Повышенный уровень, время –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 принимаем K_N = 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