Динамическое программирование Введение А.Г.Баханский © Программирование – вторая грамотность. А.П.Ершов

Оглавление Введение Задача о количестве маршрутов Задача о маршруте максимальной стоимости перехода Задача о письмах Задача об отрезках Задача о телефонных номерах Задача о кенгуру Задача о станках (самостоятельно)

Введение Динамическое программирование - один из наиболее интересных приемов для решения задач. Однако он применим только при определенных условиях. Суть метода динамического программирования разберем на примерах.

Задача о количестве маршрутов Задача о количестве маршрутов Дана прямоугольная таблица n k (n строк, k столбцов). Путник находится в верхней левой клетке. Разрешается делать шаги только вниз или вправо. Сколькими разными маршрутами он может перейти в правую нижнюю клетку? Пример 1. Пример

Пример

Математическая модель Аргументы n – число строк, целое k – число столбцов, целое Результаты m – число маршрутов, целое (или длинное целое) Промежуточные величины i, j – счетчик циклов, целые a[1..n,1..k] – массив целых (или длинных целых) чисел, где a[i,j] – число разных маршрутов из клетки 1,1 в клетку i, j

Зависимость a[i,j]:= 1, если i=1 или j=1 a[i-1,j]+a[i,j-1], если i 1 и j 1 m:=a[n,k]

Фишка движется по клеткам квадратной таблицы от северо-западного угла к юго- восточному. каждый шаг делает на восток (обозначение – В) или на юг (обозначение – Ю). В клетках таблицы вписаны натуральные числа, каждое от 1 до 9. Требуется найти (построить) маршрут фишки, обеспечивающий максимальную сумму числе в пройденных клетках. Программа должна: запросить размер таблицы (в подсказке указать ограничения); запросить содержание таблицы; найти требуемый маршрут. По завершению работы программы на экране должны быть: таблица; максимальная сумма; маршрут в виде последовательности букв В и Ю. Задача о маршруте максимальной стоимости перехода Пример 1Пример Максимальная сумма сумма Маршрут: ВВЮЮВЮ4551ЮЮЮВВВ

Пример Массив a[1..n,1..k] Массив s[1..n,1..k]

Математическая модель Аргументы n – число строк, целое k – число столбцов, целое a[1..n,1..k] – массив стоимостей, целые Результаты m – максимальная стоимость пути, целое (или длинное целое) t – маршрут, строковая Промежуточные величины i, j – счетчик циклов, целые s[1..n,1..k] – массив целых (или длинных целых) чисел, где s[i,j] – максимальная стоимость перехода из клетки 1,1 в клетку i, j

Зависимость s[i,j]:= a[i,j], если i=1 и j=1 s[i,j-1]+a[i,j], если i=1 и j1 m:=s[n,k] s[i-1,j]+a[i,j], если j=1 и i1 max{s[i-1,j],s[i,j-1]}+a[i,j], если j1 и i1

Выяснение маршрута (ретроанализ) Если s[i-1,j]>s[i,j-1], то последний шаг был на юг, иначе на восток ю в юювювю

Задача о письмах Задача о письмах Для отправки по адресам подготовлены n писем и n конвертов с адресами. Письма случайным образом раскладываются по конвертам. При этом может получиться так, что ни одно письмо не попадет в нужные руки. Например: Адрес на Какое письмо вложено в конверт конверте 1 вариант 2 вариант Иванову Петрову Сидорову Петрову Сидорову Иванову Сидорову Иванову Петрову Программа должна по заданному n находить и печатать максимально возможное число таких неправильных раскладок. Например для n=3 таких возможностей 2

Математическая модель Аргументы n – число писем, целое Результаты k – число неправильных раскладок, целое (или длинное целое) Промежуточные величины i – счетчик циклов, целое s[1..n] – массив целых (или длинных целых) чисел, где s[i] – количество неправильных раскладок i писем по i конвертам

Зависимость Если n=1, то s[i]:=0 Если n=2, то s[i]:=1 Если n=3, то s[i]:=2 Рассмотрим случай n писем, считая, что для 1, 2, …, n – 1 письма мы уже знаем число неправильных раскладок (устанавливаем рекурсивную формулу и это напоминает прием, характерный для математической индукции)

Итак, n – писем и n – конвертов. Пусть в n-ый конверт попало i-тое письмо. Это можно сделать (n – 1) способом. Тогда возможны два случая.... … 12jin-1n jin-1n 1 случай. n-ое письмо попало в i-ый конверт. Остается неправильно разложить n – 2 письма по конвертам, а это делается s[n-2] способами.... … 12jin-1n jin-1n 2 случай. n-ое письмо не попало в i-ый конверт. Остается неправильно разложить n – 1 письмо по конвертам, а это делается s[n-1] способами Получили s[n]:=(n – 1)×s[n – 2]+(n-1)×s[n – 1]

Зависимость s[i]:= 0, если i=1 1, если i=2 m:=s[n] (i – 1)(s[i – 2]+s[i – 1]), если i>2

Задача об отрезках Задача об отрезках На числовой оси заданы n точек в порядке возрастания их координат. Точки соединяются отрезками прямых так, чтобы ни одна из точек не оказалась изолированной, т.е. не принадлежащей никакому отрезку. При этом сумма отрезков должна быть минимальной. Пример : Число точек : 6 Координаты точек : 1, 3, 5, 12, 15, 16 Соединяем точки : Всего отрезков 4 Длина отрезков

Математическая модель Аргументы n – число точек, целое x[1..n] – массив координат точек, целые Результаты k – минимальное количество подходящих отрезков, целое d – их общая длина, целое Промежуточные величины i – счетчик циклов, целое s[1..n] – массив целых чисел, где s[i] – общая минимальная длина для i первых точек t[1..n] – массив строковых величин, где t[i] – код соединений для i первых точек, причем t[i][j]=`1`, если j- ый отрезок берем, `0` – не берем

Если точек две, то s[2]:=x[2]-x[1], t[2]:=`1` x[1]x[2] x[1]x[2] Если точек три, то s[3]:=x[3]-x[1], t[3]:=`11` x[3] Если точек четыре, то s[4]:=x[2]-x[1]+x[4]-x[3], t[3]:=`101` x[1]x[2]x[3]x[4] Рассмотрим случай n точек, считая, что для 1, 2, …, n – 1 мы уже знаем как считать (устанавливаем рекурсивную формулу)

x[1]x[2]x[3]x[4] Отрезок x[n-1]x[n] придется взять обязательно x[n]x[n-2]x[n-1]x[n-3] … Возможны случаи: 1. Отрезок x[n-2]x[n-1] не берем. Тогда точки x[1], x[2],..., x[n-2] придется соединять по всем правилам и общая длина составит s[n]:=s[n-2]+x[n]-x[n-1], а t[n]:=t[n-2]+`01` 2. Отрезок x[n-2]x[n-1] берем. Тогда точки x[1], x[2],..., x[n-1] придется соединять по всем правилам и общая длина составит s[n]:=s[n-1]+x[n]-x[n-1], а t[n]:=t[n-1]+`1`

Зависимость s[i]:= x[2]-x[1], если i=2 d:=s[n] x[3]-x[1], если i=3 s[i-2]+x[i]-x[i-1], если i>3 и s[i-2]s[i-1] t[i]:= `1`, если i=2 `11`, если i=3 t[i-2] +`01`, если i>3 и s[i-2]s[i-1] t[i-1] +`1`, если i>3 и s[i-2]>s[i-1] s[i-1]+x[i]-x[i-1], если i>3 и s[i-2]>s[i-1]

Число проведенных отрезков – число символов 1 в строке t[n] Если i-ый символ строки t[n] равен 1, то точки i и i+1 соединяем отрезком, если 0, то нет

Задача о телефонных номерах Задача о телефонных номерах Телефонный номер называется шахматным, если при его наборе переход на следующую цифру осуществляется ходом шахматного коня (на две кнопки в одном направлении и на одну в перпендикулярном, например, номер – шахматный, смотри рисунок). Для жителей города N используются n-значные (3 n 10) номера телефонов. Определите, сколько в городе N шахматных номеров, начинающихся на цифру k. Ваша программа должна: запросить числа n и k; найти и сообщить общее количество шахматных номеров. Например, если n=3, k=4, то число шахматных номеров

Математическая модель Аргументы n – количество цифр в номере, целое k – первая цифра в номере, целое Результаты m – искомое количество номеров, целое (или длинное целое) Промежуточные величины i, j – счетчики циклов, целое a[0..9,1..n] – массив целых (или длинных целых) чисел, где a[i,j] – число номеров, начинающихся на цифру i, длинной в j цифр

Зависимость Если j=1, то a[i,j]:=1 Если i=0 и j>1, то a[i,j]:=a[5,j-1]+a[9,j-1] Если i=1 и j>1, то a[i,j]:=a[6,j-1]+a[8,j-1] Если i=2 и j>1, то a[i,j]:=a[7,j-1]+a[9,j-1] Если i=3 и j>1, то a[i,j]:=a[4,j-1]+a[8,j-1] Если i=4 и j>1, то a[i,j]:=a[3,j-1]+a[9,j-1] Если i=5 и j>1, то a[i,j]:=a[0,j-1] Если i=6 и j>1, то a[i,j]:=a[1,j-1]+a[7,j-1] Если i=7 и j>1, то a[i,j]:=a[2,j-1]+a[6,j-1] Если i=8 и j>1, то a[i,j]:=a[1,j-1]+a[3,j-1] Если i=9 и j>1, то a[i,j]:=a[0,j-1]+a[2,j-1]+a[4,j-1]

Задача о кенгуру Задача о кенгуру Перед кенгуру дорожка длиной k у.е., по которой он может двигаться прыжками только вперед. Длина прыжка кенгуру 1, 2, 3, 4, 5 или 6 у.е. Найти число различных вариантов преодоления дорожки, если k 32. Пример 1:Пример 2: Исходные данные k = 4 Ответ 8 Примечание. Имеются в виду следующие варианты (1, 1, 1, 1); (1, 1, 2); (1, 2, 1); (2, 1, 1); (2, 2); (1, 3); (3, 1); (4) Исходные данные k = 8 Ответ 125

Математическая модель Аргументы k – длина дорожки, целое Результаты n – число вариантов перемещения, длинное целое Промежуточные величины i– счетчик циклов, целое m[0..k] – массив длинных целых чисел, где m[i] – число вариантов преодоления дорожки, длинной в i у.е.

Зависимость m[i]:=1, если i=0 m[i]:=1, если i=1 m[i]:=m[0]+m[1], если i=2 m[i]:=m[0]+m[1] +m[2], если i=3 m[i]:=m[0]+m[1] ]+m[2] +m[3], если i=4 m[i]:=m[0]+m[1] +m[2] +m[3]]+m[4], если i=5 m[i]:=m[i-6]+m[i-5] +m[i-4]+m[i-3] +m[i-2]+m[i-1], если i>5

Задача о станках Задача о станках Имеется n деталей, каждая из которых должна пройти обработку на трех станках: сначала на первом, затем на втором, а в заключение на третьем. Для каждой i–той детали известно время обработки на каждом станке, t[i,1], t[i,2] и t[i,3], соответственно. Написать программу, вычисляющую продолжительность обработки всех деталей в последовательности их ввода. Пример Число деталей – 4 Продолжительность обработки на первом, втором и третьем станках 1–ая деталь – 4, 2, 3 2–ая деталь – 2, 1, 5 3–ая деталь – 1, 5, 3 4–ая деталь – 5, 3, 6 Общее время обработки – 23

Задача (районная олимпиада года, задание 3) Задача (районная олимпиада года, задание 3) Написать программу определения количества 2*N -значных билетов, у которых сумма первых N десятичных цифр равна сумме N последних десятичных цифр; при этом N10 -натуральное число. Например, если N=2, то счастливых билетов K=669.

program oo32009; uses crt; var n,i,j,m:integer; k:int64; s:array [1..40, ] of int64; begin clrscr; writeln('n'); readln(n); for i:=1 to n do for j:=-9 to 9*n do s[i,j]:=0; for i:=0 to 9 do s[1,i]:=1; for i:=2 to n do for j:=0 to 9*i do for m:=0 to 9 do s[i,j]:=s[i,j]+s[i-1,j-m]; k:=0; for i:=1 to 9*n do k:=k+s[n,i]*s[n,i]; writeln('Число счастливых билетов ',k); readkey end.

Задача (районная олимпиада года, задание 3) Задача (районная олимпиада года, задание 3) Скучающий Вася Пупкин решил посчитать количество двузначных простых чисел. Их оказалось 21: 11, 13,17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. Он так увлекся этим занятием, что начал изучать «двупростые» числа. Так Вася назвал числа, у которых любые 2 подряд идущие цифры образуют двузначное простое число. Вам предстоит продолжить дело Васи и выяснить, насколько часты (или редки) «двупростые» числа. Составите программу, которая * Запрашивает число N цифр в числе (2 N 20); * Находит и сообщает число N-значных «двупростых» чисел (возможно, длинное целое). Например: Число разрядов N4 Число N-разрядных «двупростых» чисел 142 Примечание. Решение этой задачи для N 8 оценивается из 60 баллов.

program dvyprostii; uses crt; var k:longint=2; {Количество разрядов в числе} c1:longint=5; {Счетчик пар, оканчивающихся на 1} c3:longint=6; {Счетчик пар, оканчивающихся на 3} c7:longint=5; {Счетчик пар, оканчивающихся на 7} c9:longint=5; {Счетчик пар, оканчивающихся на 9} cc1,cc3,cc7,cc9:longint; s:longint=21; {Общее количество чисел, первоначально двузначных} m:longint; {Общее количество цифр} j:longint; begin clrscr; write('Число разрядов в числе >=2 и <=20) ') ; readln(k); for j:=3 to k do begin cc1:=c1+c3+c7; cc3:=c1+c7; cc7:=c1+c3+c9; c9:=c1+c7; c1:=cc1; c3:=cc3; c7:=cc7; s:=c1+c3+c7+c9; end; writeln('Количество чисел ',s); readkey; end.

И это еще не все, но... КОНЕЦКОНЕЦ