Конспект и презентация к уроку информатики "Динамическое программирование"; 11 класс

Разработка рекурсивных алгоритмов на языке программирования Python

для 11 класса

углублённого изучения предмета информатика

ТЕМА «ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ»

Предметные результаты:

• Получить представление о динамическом программировании, рекуррентной формуле

• Уметь составлять программы для практических задач с применением рекуррентной формулы на языке Python

Мета предметные результаты:

Регулятивные УУД:

Планирование – определение последовательности промежуточных целей с учётом конечного результата, составлдение плана и последовательности действий при создании динамической модели

Контроль за этапами выполнения задачи

Коммуникативные УУД:

Умение лаконично выражаться

Владение навыками письменной коммуникации

Познавательные УУД:

Умение определять понятия, делать выводы, обобщение, строить логические умозаключения

Устанавливать причинно-следственные связи

Личностные результаты:

Формирование устойчивого познавательного интереса

Повышение ответственности к обучению

Тип урока: Комбинированный

План:

1. Неформальное определение динамического программирования

2. Примеры задач применения ДП

3. Описание идеи ДП

4. Точное определение ДП

5. Пример 1 (задача о числовом ряде)

6. Пример 2 (задача и сдаче)

7. Задача 3 (оптимальная сдача)

8. Применение динамического программирования к решению КИМ 23 ЕГЭ.

1. Организационный этап.

2. Постановка цели и задач урока. Мотивация учебной деятельности учащихся (пункты 1-4)

3. Первичная проверка понимания (пункт 5)

4. Первичное закрепление (пункт 6-7)

1. ДП – техника, позволяющая решать некоторые задачи комбинаторики, оптимизации, …, обладающие определённым свойством (со оптимальности).

2. ПРИМЕРЫ ЗАДАЧ

№	задача	Целевая функция	Переменные выбора
А. оптимизация
	Маршрут оптимальной длины	Цель: найти кратчайший путь Целевая функция: минимизация расстояния	Куда повернуть
	Замена машины (оборудования)	Задача: продать старую или купить новую Целевая функция: минимизация расходов	Продать или оставить
	Биржевой портфель	Целевая функция: максимизация среднего дохода	Сколько купить акций и какой фирмы
	Составление плана производства (например, производство мебели)	Целевая функция: максимизация прибыли	Составляющий план: Сколько столов Сколько шкафов
Б. Комбинаторика
	Графы, деревья
	Количество способов вернуть сдачу

3. Н еформальное объяснение

Отвлечься орт решения сразу всей задачи, а рассмотреть решение задачи только для Х1. Найти для неё оптимальное решение и с помощью этого решения найти решение для задачи Х1, Х2. Аналогично поступить для Х1, Х2, Х3 и т.д., пока не получим решение всей задачи.

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

• Пример 1.

Применим к решению идеи ДП

F(1) =1

F(2) = F(1)+2 = 1+2= 3

F(3) = F(2)+3 = 3+3=6

…

F(n)= F(n-1)+a_n – рекуррентная формула

Рекуррентная формула (от лат. recurrens, родительный падеж recurrentis - возвращающийся), формула приведения, формула, сводящая вычисление n-го члена какой-либо последовательности (чаще всего числовой) к вычислению нескольких предыдущих её членов.

def f(n):

if n== 0:

return 0

else:

return n + f(n-1)

n=int(input('введите значение n'))

print('сумма равна',f(n))

• Задача 2 (задача о сдаче)

Задача: имеются копейки номиналом 1, 3, 5, 10

Вопрос: сколько существует способов вернуть сдачу номиналом n копеек? (порядок монет в сдаче важен)

4 копейки

1 способ: 1 1 1 1

2 способ: 1 3

3 способ: 3 1

1 копейка 1

0 копеек 1

Обозначим через F(i) – количество способов вернуть сдачу размерностью i

F(n) - ?

F(0) F(1) F(2) F(3) … F(n-1) F(n)

F(0)=1

F(1)=1

F(2)= F(1)=1

F(3)= F(2) + F(0)=2

F(4)= F(3)+ F(1)=3

F(5)= F(4)+ F(2) +F(0)=5

F(6)= F(5)+ F(3) + F(1)=8

{рассчитайте самостоятельно F(7) и F(10) }

F(7)= F(6)+ F(4) + F(2)=12

F(8)= F(7)+ F(5) + F(3)=12+5+2=19

F(9)= F(8)+ F(6) + F(4)=19+8+3=30

F(10)= F(9)+ F(7) + F(5)+ F(0)=30+12+5+1=48

i	0	1	2	3	4	5	6	7	8	9	10
F(i)	1	1	1	2	3	5	8	12	19	30	48

Рекуррентные формулы:

при 1<к<3: F(k)= F(k-1)

при 3≤к<5: F(k)= F(k-1)+ F(k-3)

при 5≤к<10: F(k)= F(k-1)+ F(k-3)+ F(k-5)

при к≥10: F(k)= F(k-1)+ F(k-3)+ F(k-5)+ F(k-10)

Основные этапы решения:

• Определили целевую функцию, ввели обозначения

• Составили рекуррентную формулу

• Вычислили F(0), F(1), F(2), …, F(n)

• Нашли общее решение F(n)

Программа:

def f(n):

if n==0:

return 1

if n==1:

return 1

if n>1 and n<3:

return f(n-1)

if n>=3 and n<5:

return f(n-1)+f(n-3)

if n>=5 and n<10:

return f(n-1)+f(n-3)+f(n-5)

if n>=10:

return f(n-1)+f(n-3)+f(n-5)+f(n-10)

k=int(input('введите '))

print('для номиналом',' ',k,' ','копеек существует', ' ', f(k),' ','способ(а/ов)')

VII. Задача 3 (оптимальная сдача)

Определить минимальное количество монет (номиналом 1,3,5,10) необходимых для возврата сдачи

Обозначим F(n)= минимальное количество монет (номиналом 1,3,5,10) необходимых для возврата сдачи

сдача	0	1	2	3	4	5	6	7	8	9	10
F	0	1	2	1 (3)	2 (1,3)	1 (5)	2 (3,3) или (5,1)	3 (1,1,3)	2 (3,5)	3 (1,3,5)	1 (10)

1. Наивно решение (правильное, но не эффективное)

Рассмотреть всевозможные способы вернуть сдачу n и выбрать тот, который использует минимальное количество монет.

В чем проблема?

Для больших значений n переборов будет огромное множество, что трудно реализуемо.

2. «Жадное» решение (простое, эффективное, но не всегда верное)

{Жадный алгоритм — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным.}

1. N-10, -10,-10 … пока N не станет N<10 (или n div 10)

2. N-5,-5 …. N<5

…

Но существует набор монет, для которого этот алгоритм даёт неверное решение

Например, имеются монеты 10, 9, 1 и сдача n=18

3. Применим идею динамического программирования

F(0)=0

F(1)=1

Найдём рекуррентную формулу

F(n)=1+ F(n-1);1+ F(n-3);1+ F(n-5); 1+F(n-10)

1 3 5 10

F(n)=1+min[F(n-1), F(n-3), F(n-5), F(n-10)]

I_n≥1 I_n≥3 I_n≥5 I_n≥10

П

11-10=1

ринятие решения какую монету выбрать

Р ассмотрим пример:

Цель F(12)

N	0	1	2	3	4	5	6	7	8	9	10	11	12
F(n)	0	1	2	1	2	1	2	3	2	3	1	2	3
какой монетой достигается минимум			1	3	1	5	1	2	1	3	10	10	1

F(2) = 1+min[F(1)]=1+1=1

F(3) = 1+min[F(2), F(0)]=1+0=1

F(4) = 1+min[F(3), F(1)]=1+1=2

F(5) = 1+min[F(4), F(2), F(0)]=1

…

Какие монеты нужны, чтобы вернуть F(12) с помощью трёх монет?

По таблице набрать все минимумы, начиная с конца: 1, 10, 1

Рассмотрение алгоритма решения задачи 23. (презентация прилагается)

З адача 4