Архив решенных задач

Метод динамического программирования.

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

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

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

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

Динамическое программирование - это программирование с использованием таблиц, когда при заполнении очередной клетки таблицы используются уже заполненные.

Разберем несколько задач.

Домино

Определить количество вариантов укладывания костей домино в прямоугольнике 2х12.

Решение

Обобщим задачу: определим количество вариантов укладывания костей домино в прямоугольнике 2хn.

Рассмотрим решение задачи для n=1, 2, 3, и т.д. Пусть а[n]- количество вариантов укладывания костей домино в прямоугольнике 2хn. Тогда a[1]=1,a[2]=2,a[3]=3,a[4]=5.

Предположим, что мы знаем значение a[n-1], a[n-2] и т.д. Заметим, что любую кость домино можно положить либо вертикально, либо горизонтально. Значит, последняя кость может располагаться вертикально, тогда остальные кости можно расположить a[n-1] способами, или горизонтально, тогда остальные кости можно расположить a[n-2] способами.

Таким образом, a[n]=a[n-1]+a[n-2].

Тогда a[5]=3+5=8; a[6]=5+8=13; a[7]=8+13=21; a[8]=13+21=34; a[9]=21+34=55; a[10]=34+55=89; a[11]=55+89=144; a[12]=144+89=233.

Итак, количество вариантов укладывания костей домино в прямоугольник 2х12 равно 233.

Игра "Даты" .(№13 [3])

Играют двое. Первый игрок сообщает какую-нибудь дату января 1991 года. Каждый игрок на своем ходе называет более позднюю дату, увеличивая либо календарную дату в месяце, либо месяц, но не то и другое сразу. Описать выигрышную стратегию, при которой:

a) игрок, назвавший 31 декабря, выигрывает (3 балла);

b) игрок, назвавший 31 декабря, проигрывает (5 баллов).

решение

Построим таблицу 12x31, соответствующую дням года.

В варианте а) пометим правую верхнюю клеточку (31 декабря) знаком "+", как выигрышную. Тогда все клетки правого столбца (декабря) и верхней строки (31-е числа) будут проигрышными "-". Из оставшихся клеток ближайшую свободную клетку (30 ноября) снова пометим "+" (как легко видеть, она выигрышная), а оставшиеся клетки этого столбца и строки пометим "-". Продолжение такого построения приведет к тому, что выигрышные клетки заполнят диагональ с 20.01 по 31.12. Соответственно, выигрышная стратегия будет заключаться в том, чтобы на каждом шаге называть одну из дат 20.01, 21.02, 22.03, 23.04, 24.05, 25.06, 26.07, 27.08, 28.09, 29.10, 30.11, 31.12. Выигрывает первый игрок. В варианте б) пометим правую верхнюю клеточку (31 декабря) знаком "-" (по условию она проигрышная), а две ближайшие к ней клетки по горизонтали и вертикали (30.12 и 31.10 ! не 31.11) пометим знаком "+". Снова, поскольку ход можно делать на любое количество клеток в одном направлении, надо пометить все оставшиеся клетки 10 и 12 столбца и 31 и 30 строк знаком "-".Из оставшихся клеток ближайшую свободную клетку (29 ноября) снова пометим "+" (как легко видеть, она выигрышная), а оставшиеся клетки этого столбца и строки пометим "-". Продолжение такого построения приведет к тому, что выигрышные клетки заполнят диагональ с 20.01 по 28.09. Соответственно, выигрышная стратегия будет заключаться в том, чтобы на каждом шаге называть одну из дат 20.01, 21.02, 22.03, 23.04, 24.05, 25.06, 26.07, 27.08, 28.09, 31.10, 29.11, 30.12. Выигрывает снова первый игрок.