Презентация на тему: Дистанционная подготовка к Всероссийской олимпиаде по информатике

Дистанционная подготовка к Всероссийской олимпиаде по информатике
Динамическое программирование
Идея метода
Одномерное ДП
Одномерное ДП
Одномерное ДП
Двумерное ДП
Двумерное ДП
Двумерное ДП
Двумерное ДП
Задача о рюкзаке
Задача о рюкзаке
Задача о самой длинной возрастающей подпоследовательности
Задача о самой длинной возрастающей подпоследовательности
Задача о палиндроме
Задача о палиндроме
Задача о палиндроме
1/17
Средняя оценка: 4.9/5 (всего оценок: 99)
Код скопирован в буфер обмена
Скачать (278 Кб)
1

Первый слайд презентации: Дистанционная подготовка к Всероссийской олимпиаде по информатике

Преподаватель: к.ф.-м.н., заведующий кафедрой ВТиКГ ДВГУПС, преподаватель программы IT -школа Samsung, Пономарчук Юлия Викторовна E-mail: yulia.ponomarchuk@gmail.com

Изображение слайда
2

Слайд 2: Динамическое программирование

Изображение слайда
3

Слайд 3: Идея метода

Метод динамического программирования используется для задач, обладающих следующим свойством: имея решения некоторых подзадач (для меньшего числа N ), можно найти решение исходной задачи, т.е. оптимальное решение подзадачи большего размера можно построить из оптимальных решений подзадач.

Изображение слайда
4

Слайд 4: Одномерное ДП

Последовательность Фибоначчи задается формулами: F 1 = 1, F 2 = 1, F n = F n-1 +F n-2 при n>1. Необходимо найти F n по номеру n. Неэффективное рекурсивное решение: function F(n: integer): integer; begin if n<2 then F := 1 else F := F(n-1) + F(n-2); end ; Эффективное решение по методу ДП: F[1] = 1; F[2] = 1; for i :=3 to n do F[ i ] := F[i-1] + F[i-2];

Изображение слайда
5

Слайд 5: Одномерное ДП

Посчитать число последовательностей нулей и единиц длины n, в которых не встречаются две идущие подряд единицы. Обозначим K[ i ] – число таких последовательностей длины i Тривиальные случаи: K[1] = 2, K[2] = 3; Ответом является значение K[n]

Изображение слайда
6

Слайд 6: Одномерное ДП

Проанализируем последовательность длины i. Если последний ее символ равен 0, то первые i-1 – любая правильная последовательность длины i-1 ( не важно, заканчивается она нулем или единицей). Таких последовательностей K[i-1]. Если последний ее символ равен 1, то предпоследний символ обязательно должен быть равен 0 (иначе будет две единицы подряд), а первые i-2 символа – любая правильная последовательность длины i-2. Таких последовательностей K[i-2]. Таким образом, K[ i ] = K[i-1] + K[i-2], т.е. данная задача сводится к нахождению чисел Фибоначчи

Изображение слайда
7

Слайд 7: Двумерное ДП

Дано прямоугольное поле размером n на m клеток. Можно совершать шаги длиной в одну клетку вправо и вниз. Посчитать, сколькими способами можно попасть из левой верхней клетки (с координатами ( 1, 1 )) в правую нижнюю (с координатами ( n, m)).

Изображение слайда
8

Слайд 8: Двумерное ДП

В некоторую клетку с координатами ( i,j ) можно прийти только сверху или слева, т.е. из клеток с координатами ( i-1, j) и ( i, j-1). Таким образом, для клетки ( i, j) число маршрутов A[ i,j ] = A[i-1,j] + A[i,j-1], т.е. задача сводится к двум подзадачам. Необходимо последовательно пройти по строкам (или столбцам), находя число маршрутов для текущей клетки по формуле. Тривиальный случай: A[1,1] = 1 Ответ находится в элементе A[ n,m ]

Изображение слайда
9

Слайд 9: Двумерное ДП

( Задача о черепашке ). Дано прямоугольное поле размером n на m клеток. Можно совершать шаги длиной в одну клетку вправо, вниз или по диагонали вправо-вниз. В каждой клетке записано некоторое натуральное число. Необходимо попасть из левой верхней клетки (с координатами ( 1, 1 )) в правую нижнюю (с координатами ( n,m )). Вес маршрута вычисляется как сумма чисел со всех посещенных клеток. Необходимо найти маршрут с минимальным весом.

Изображение слайда
10

Слайд 10: Двумерное ДП

В некоторую клетку с координатами ( i,j ) можно прийти из клеток с координатами ( i-1, j), ( i, j-1) и ( i-1, j-1). Допустим, что для каждой из этих трех клеток уже найден маршрут минимального веса, а сами эти веса находятся в W[i-1,j], W[i,j-1] и W[i-1,j-1]. Чтобы найти минимальный вес для ( i,j ), необходимо выбрать минимальный из весов W[i-1,j], W[i,j-1], W[i-1,j-1] и прибавить к нему число, записанное в текущей клетке: W[ i,j ] = W[i-1,j] + W[i,j-1] + W[i-1,j-1].

Изображение слайда
11

Слайд 11: Задача о рюкзаке

Имеется судно грузоподъемностью W и N предметов. Известно, что i -й предмет имеет вес w i и ценность c i. Необходимо загрузить судно предметами так, чтобы получить максимальную прибыль.

Изображение слайда
12

Слайд 12: Задача о рюкзаке

Обозначим через f( i,w ) максимальную стоимость, которую можно получить имея лишь первые i грузов и грузоподъемность w. Если i - й груз не использовался при подсчете f( i,w ), то f( i,w ) = f(i-1,w). Иначе f( i,w ) = f(i-1,w-w i ) + c i Из двух вариантов выбираем максимальный: f( i,w ) = max( f(i-1,w), f(i-1,w-w i ) + c i ), i >1 Начальные условия: f(1,w i ) = c i

Изображение слайда
13

Слайд 13: Задача о самой длинной возрастающей подпоследовательности

Дана последовательность целых чисел. Необходимо найти длину ее самой длинной возрастающей подпоследовательности. Пример Последовательность 4, 1, 7, 5, 2, 5, 8, 3 Ответ : длина 4 (1, 2, 5, 8)

Изображение слайда
14

Слайд 14: Задача о самой длинной возрастающей подпоследовательности

Пусть f[ i ] – длина наибольшей возрастающей подпоследовательности среди элементов a[1], a[2], …, a[ i ], где a[ i ] – последний элемент возрастающей подпоследовательности. Определим возрастающие подпоследовательности, к которым допустимо прибавление a[ i ]. Они обязаны заканчиваться на элемент a[j] (j< i ), меньший чем a[ i ]. f[ i ] = 1 + max(f[j]) для всех j, таких что j=1… i и a[j]<a[ i ]

Изображение слайда
15

Слайд 15: Задача о палиндроме

Палиндром – это симметричная строка, т.е. строка, которая одинаково читается как слева направо, так и справа налево. Требуется по заданной строке определить минимальное количество символов, которые необходимо вставить в строку для преобразования ее в палиндром. Прописные и строчные буквы считаются различными. Пример. После вставки двух символов строка Ab3bd может быть преобразована в палиндром dAb3bAd или Adb3bdA. Вставкой менее двух символов палиндром получить нельзя.

Изображение слайда
16

Слайд 16: Задача о палиндроме

f[ i,j ] – минимальное количество символов, которые необходимо вставить в подстроку S[ i..j] ( где i – номер крайнего левого символа исходной строки, j – крайнего правого) для того, чтобы получить искомый палиндром. Искомый результат – f[1,n]

Изображение слайда
17

Последний слайд презентации: Дистанционная подготовка к Всероссийской олимпиаде по информатике: Задача о палиндроме

Рассмотрим строку S[ i..j] Если символы S[ i ] и S[j] совпадают, то для преобразования строки в палиндром требуется столько же символов, сколько для преобразования строки S[i+1..j-1]. При несовпадении символов требуется добавить один символ или к подстроке S[i+1..j] или к подстроке S[i+1..j] – к той из них, для которой преобразование в палиндром осуществляется за минимальное количество символов.

Изображение слайда