Занятие № 2 динамическое программирование

Е.В. Брызгалов

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

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

Для решения таких задач существует специальная теория, большая заслуга в ее создании принадлежит Р. Беллману. В общем виде она достаточна сложна, поэтому здесь не рассматривается. В то же время конкретные задачи, рассмотренные ниже, вполне могут сформировать (хотя бы на интуитивном уровне) идеи, лежащие в основе решения задач данного класса.

Первые две задачи, строго говоря, нельзя отнести к указанному классу, но приемы, использованные при их решении, очень сходны с таковыми у задач, рассматриваемых на этом занятии. Остальные задачи в свое время встречались на различных олимпиадах (а некоторые с тех пор стали фольклорными) и расположены (по мнению автора публикации) в порядке возрастания сложности. Для простоты будем считать, что в большинстве задачах исходные данные таковы, что результат поместится в тип LongInt. Справедливости ради отметим, что такое ограничение существует не всегда, и в последних двух задачах приходится либо использовать тип Double, либо дополнительно реализовывать длинную арифметику.

Числа Фибоначчи
Вычислить N-ое число в последовательности Фибоначчи, — 1, 1, 2, 3, 5, 8, … — в которой первые два члена равны единице, а все остальные представляют собой сумму двух предыдущих.
Формат входных данных
Одно число 0N47.
Формат выходных данных
Одно число — N-ый член последовательности.

[посмотреть подсказку]

Числа Фибоначчи

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

Самый очевидный способ “решения” задачи состоит в написании рекурсивной функции примерно следующего вида:

Function F(X:integer):longint; Begin if (X = 1) or (X = 2) then F := 1 else F := F(X — 1) + F(X — 2) end;

При этом где-то в середине четвертого десятка программа “подвешивает” самый быстрый компьютер (напомним, что по правилам олимпиад время на прохождение теста ограничивается, чаще всего это 10–15 секунд). Попробуем разобраться, почему так происходит? Для вычисления F(40) мы сперва вычисляем F(39) и F(38). Причем F(38) мы считаем “по новой”, “забывая”, что уже вычислили его, когда считали F(39). То есть наша основная ошибка в том, что значение функции при одном и том же значении аргумента считается много (слишком много!) раз. Если исключить повторный счет, то функция станет заметно эффективней. Для этого приходится завести массив, в котором хранятся значения нашей функции:

Var D : Array [1..50] of LongInt;

Срабатывает золотой закон программирования — выигрывая в скорости, проигрываем в памяти. Сперва массив заполняется значениями, которые заведомо не могут быть значениями нашей функции (чаще всего, это “минус единица”, но в нашей задачке вполне годится для этих целей “ноль”). При попытке вычислить какое-то значение, программа смотрит, не вычислялось ли оно ранее, и если да, то берет готовый результат. Функция принимает следующий вид (не верьте, пожалуйста, книгам, утверждающим, что искать числа Фибоначчи рекурсивно нельзя в принципе — можно, если отсечение делать с умом):

Function F(X : integer) : LongInt; Begin if D[X] = 0 then if (X = 1) or (X = 2) then D[X] := 1 else D[X] := F(x — 1) + F(x — 2); F := D[X] End;

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

D[1] := 1; D[2] := 1; For i := 3 to X do D[i] := D[i-1] + D[i-2];

Чаще всего такой способ раза в три быстрее. Но очень часто для его написания приходится использовать как промежуточный результат нисходящую форму, а иногда безрекурсивная (итеративная) форма оказывается чрезвычайно сложной и малопонятной. Не стоит забывать и о том, что время на олимпиаде ограничено. Еще об одном недостатке второй формы будет сказано через несколько задач. Суммируя, можно дать совет участнику (отнеситесь к нему критически): “Пишите и тестируйте рекурсивную форму, а переделыванием занимайтесь, если ваша программа превышает отведенное ей время на “больших” тестах”.

к занятию № 2

Мячик на лесенке
На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных маршрутов мячика с вершины на землю.
Формат входных данных
Одно число 0N31.
Формат выходных данных
Одно число — количество маршрутов.

[посмотреть подсказку]

Мячик на лесенке

Пусть мячик находится на некоторой ступеньке с номером X. Тогда он может спрыгнуть на ступеньки с номерами X — 1, X — 2 и X — 3. Если мы введем функцию F(X), которая определяет число маршрутов со ступеньки X до земли, то F(X) = F(X – 1) + F(X – 2) + F(X – 3). Остается просчитать вручную граничные значения: F(1) = 1, F(2) = 2 (очевидно), F(3) = 4 (3–2–1–0, 3–2–0, 3-1–0, 3–0). Все остальное уже сделано в предыдущей задаче. Чтобы не загромождать функцию, можно присваивания граничных значений сделать заранее, тогда отсечение произойдет автоматически:

Function F(X : integer) : longint; begin if D[X] = 0 then D[X] := F(x-1) + F(x-2) + F(x-3); {для X = 1..3, D[X]0 изначально} F := D[X] end;

Написание итеративной формы также труда не представляет.

Робот
В исследовательской лаборатории фирмы RobotsCo разработали новую модель робота. Главной особенностью данной модели робота является то, что он работает по заранее заданной программе, в которой могут присутствовать команды: сделать шаг на Юг, на Север, на Восток или на Запад. Робот исполняет программу строго последовательно и, дойдя до конца программы, останавливается. Специалисты из RobotsCo заинтересовались вопросом, сколько существует различных программ, состоящих из K инструкций, таких, что робот, выйдя из начала координат, придет в точку с координатами (X, Y). Оси координат располагаются параллельно сторонам света, и единица измерения, соответствует одному шагу робота. Напишите программу, которая дает ответ на этот вопрос.
Формат входных данных
Во входном файле находятся три числа K, X и Y (0Формат выходных данных
В выходной файл ваша программа должна поместить одно число — количество программ для робота.

Робот

В этой задаче мы впервые сталкиваемся с функцией трех переменных: F(X, Y, Z) — показывает количество маршрутов длины Z, приводящих в клетку (X, Y). К сожалению, такая структура данных как

Array [-16..16, -16..16, 0..16] of LongInt;

в память не помещается. Забудем пока об этой трудности и напишем рекурсивную часть. Для ответа на поставленный в задаче вопрос можно посчитать число маршрутов длины Z — 1 в четыре клетки, смежных с заданной, а результаты сложить, не забывая случаи клеток на границе. Граничными условиями будут F(X, Y, 0) = 0, если хотя бы одна из координат X или Y отлична от нуля, и F(0, 0, 0) = 1. Действительно, если робота не двигать, то он может оказаться только в начале координат. Теперь вспомним о проблеме хранения данных. Выхода существует два. Первый, чисто программистский, заключается в разбиении большой структуры на несколько меньших и размещении их в динамической памяти. Сделать это можно, например, так

Type T1 = array[-16..16, -16..16] of LongInt; T2 = array [0..16] of ^T1; Var D : T2;

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

Function F(X, Y, Z : integer) : longint; var s : longint; begin if D[Z]^[X, Y] = -1 then begin s := 0; if X-16 then s := s + F(X — 1, Y, Z — 1); if X16 then s := s + F(X + 1, Y, Z — 1); if Y-16 then s := s + F(X, Y — 1, Z — 1); if Y16 then s := s + F(X, Y + 1, Z — 1); D[Z]^[X, Y] := s end; F := D[Z]^[X, Y] end;

Это, конечно, решение, но оно далеко не оптимальное (с точки зрения расходования памяти). Действительно, для вычислений в некий момент времени необходимы данные только за предыдущий, что же происходило ранее, нас не интересует — с этим мы уже справились. Значит, достаточно хранить только 2 квадратные матрицы размером 31, — одна несет данные в предыдущий момент времени, а вторая вычисляется для текущего с использованием первой матрицы. После окончания расчета данные первой уже не нужны, ей присваиваем значение второй матрицы, увеличиваем счетчик времени и т.д. Ясно, что такую идею можно реализовать только итеративно.

for z := 1 to k do begin Way2 := Way1; for i := -16 to 16 do for j := -16 to 16 do begin s := 0; if i-16 then s := s + Way2[i — 1, j]; if i16 then s := s + Way2[i + 1, j]; if j-16 then s := s + Way2[i, j — 1]; if j16 then s := s + Way2[i, j + 1]; Way1[i, j] := s end end;

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

Черепашка
На квадратной доске расставлены целые неотрицательные числа. Черепашка, находящаяся в левом верхнем углу, мечтает попасть в правый нижний. При этом она может переползать только в клетку справа или снизу и хочет, чтобы сумма всех чисел, оказавшихся у нее на пути, была бы максимальной. Определить эту сумму.
Формат входных данных
Первая строка — N — размер доски.
Далее следует N строк, каждая из которых содержит N целых чисел, представляющие доску.
Формат выходных данных
Одно число — максимальная сумма.

[посмотреть подсказку]

Черепашка

Эта задача является классикой динамического программирования. Ни одно печатное или электронное пособие по решению задач не обходится без разбора “Черепашки”. Рассмотреть все возможные маршруты и просчитать их невозможно. Но можно свести задачу к аналогичной. Пусть нам известен “максимальный” путь для всех клеток, кроме правой нижней (функция F(X, Y)). Все нужные маршруты проходят через одну из клеток, смежных с этим углом (их всего две). Максимальный же маршрут проходит через ту клетку из двух, для которой значение функции F больше. Остается только правильно выполнить отсечение:

Function F(x,y:integer):longint;begin if B[x, y] = –1 then if F(x-1, y)F(x, y — 1) then B[x, y] := F(x — 1, y) + A[x, y] else B[x, y] := F(x, y — 1) + A[x, y]; F := B[x, y]end;

Теперь необходимо подумать о граничных условиях. Логически правильнее было бы просчитать нашу функцию для левой и верхней границы. Это делается легко, так как для этих клеток существует только один маршрут (непосредственно вдоль границы). Но еще проще ввести в рассмотрение фиктивные нулевые строку и столбец и присвоить им нулевые значения. Действительно, эти клетки, в принципе, недостижимы, поэтому максимальная сумма равна нулю.

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

for i:=1 to N do for j:=1 to N do if B[i — 1, j]B[i, j — 1] then B[i, j] := B[i — 1, j] + A[i, j] else B[i, j] := B[i, j — 1] + A[i, j];

к занятию № 2

Взрывоопасность
При переработке радиоактивных материалов образуются отходы двух видов — особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры, последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более двух контейнеров типа A. Для заданного количества контейнеров N определить число безопасных стопок.
Формат входных данных
Одно число 0N31.
Формат выходных данных
Одно число — количество безопасных вариантов формирования стопки.

[посмотреть подсказку]

Взрывоопасность

Если в предыдущей задаче нам удалось использовать рекурсивное решение, то здесь придется обходиться итеративным. Как обычно, будем искать число опасных стопок для произвольного N. Сложность в том, что стопки сами по себе разные. Разобьем их на 4 класса:

Тип 1 — опасные, содержат три или более контейнера A подряд.
Тип 2 — не опасны, но наверху лежат два контейнера А.
Тип 3 — не опасны, но наверху лежат один контейнер А (а под ним, если есть, B).
Тип 4 — не опасны, с контейнером B наверху.

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

из стопки 1-го класса получится 2 стопки 1-го класса;
из стопки 2-го класса получится по стопке 1-го и 4-го класса;
из стопки 3-го класса получится по стопке 2-го и 4-го класса;
из стопки 4-го класса получится по стопке 3-го и 4-го класса;

Теперь о граничных (вообще-то, для итеративных схем лучше говорить о начальных) условиях. Их можно написать как для N = 1 (по одной стопке типа 3 и 4), так и для N = 0 (одна стопка типа 4 — собственно, стопок нет вообще). Заметим, что как и в предыдущей задаче, нам достаточно знать количества стопок высоты на единицу меньшей текущей. После этого решение становится совсем простым.

к занятию № 2

[посмотреть подсказку] K-ичные числа

Эта задача почти не отличается от предыдущей, если число представить как стопку, а нули — как контейнеры типа A. Очевидно, что все числа разбиваются на три класса. Остается только прописать переходы при добавлении одной цифры. Лучше (привычнее) сделать это в десятичной системе счисления, а затем заменить девятки (количество ненулевых цифр) на K – 1, а десятки — на K. В результате основной цикл будет выглядеть так:

for i := 2 to N do begin OTZ := TZ; OZ := Z; ONZ := NZ; TZ := OTZ * K + Z; {TZ — два нуля} Z := ONZ; {Z — один ноль} NZ := OZ * (K — 1) + ONZ * (K — 1) {NZ — в конце не ноль} end;

к занятию № 2

К-ичные числа
Требуется вычислить количество N-значных чисел в системе счисления с основанием K, таких что их запись не содержит двух подряд идущих нулей.
Ограничения: 2Формат входных данных
Числа N и K в десятичной записи, разделенные пробелом или переводом строки.
Формат выходных данных
Искомое число в десятичной записи.

[посмотреть подсказку]

Подпалиндром

Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. Например, HELOLEH является подпалиндромом строки HTEOLFEOLEH. Напишите программу, находящую в данной строке подпалиндром максимальной длины.
Формат входных данных
Строка длиной не более 100 символов, состоящая из заглавных букв латинского алфавита.
Формат выходных данных
В первой строке вывести длину максимального подпалиндрома, а во второй строке сам максимальный подпалиндром. Если таких подпалиндромов несколько, то вывести любой из них.

[посмотреть подсказку] Подпалиндром

Эта задача является своеобразным водоразделом. Задачи, рассмотренные ранее, были достаточно простыми. Теперь начинается если не “высший пилотаж”, то уж никак не “обязательная программа”. Если Вам не удаётся их решить, то не стоит отчаиваться — с помощью таких задач определяются победители областных олимпиад.

Итак, мы имеем строку длины N. Будем искать палиндромы для подстроки с i-го символа по j-ый включительно, то есть писать функцию F(I, J). Хотелось бы, что она возвращала сам палиндром, но это невозможно из-за нехватки памяти. Ограничимся одной длиной. Массив целых 100 * 100 в памяти помещается свободно. Размещаем граничные случаи: F(I, I) = 1 и F(I, J) = 0, если IJ. Теперь в рассматриваемой подстроке отделяем первый символ. Есть две возможности (какая из них реализуется, пока не знаем). Отделенный символ не участвует в образовании максимального подпалиндрома — тогда F(I, J) = F(I + 1, J). Если же участвует, то ищем в подстроке с конца символ, совпадающий с отделенным (пусть его позиция K), тогда F(I, J) = 2 + F(I + 1, K – 1). Надо предусмотреть еще случай I = K, а затем отсекать рекурсию известным способом. Получается примерно следующее:

Function F(i, j : Integer) : Integer; var Ch : Char; R1, R2 : Integer; k : byte; begin if Mat[i, j] = -1 then BEGIN k := j; while Inp[i]Inp[k] do dec(k); R1 := F(i + 1, j); if ik then R2 := F(i + 1, k — 1) + 2 else R2 := 1; if R1R2 then Mat[i, j] := R1 else Mat[i, j] := R2 END; F := Mat[i, j] end;

Итеративно заполнять массив тоже можно, но при этом “стандартный” двойной цикл от 1 до N не годится. Попробуйте, такое решение тоже существует…

Первая, наиболее сложная, часть задачи решена (достаточно вызвать F(1, N)). Решение второй части тоже интересная задача, но здесь не рассмотрено (в архиве предложено полное решение задачи).

Примечание только для профессионалов: можно решать задачу и “в лоб” — переворачиваем введенную строку и используем на двух строках (исходной и полученной) алгоритм Нудельмана-Фишнера.

к занятию № 2

Мячик на лесенке

Function F(X : integer) : longint; begin if D[X] = 0 then D[X] := F(x-1) + F(x-2) + F(x-3); {для X = 1..3, D[X]0 изначально} F := D[X] end;

Написание итеративной формы также труда не представляет.

к занятию № 2

Паровозики
N локомотивов, имеющих номера от 1 до N и установленных на железнодорожную колею, начинают двигаться в одну сторону, причем локомотив номер k изначально движется со скоростью k км/ч. Если локомотив, движущийся с большей скоростью, нагоняет более медленный локомотив, дальше они движутся один за другим со скоростью впереди идущего локомотива. Очевидно, через некоторое время после начала движения локомотивы разобьются на несколько групп, движущихся с разной скоростью.
Написать программу, определяющую, сколько начальных расстановок s из N! Возможных дадут в результате p групп движущихся локомотивов.
Формат входных данных
Два числа — 0N17 и 0pN + 1.
Формат выходных данных
Одно число — s.

[посмотреть подсказку] Паровозики

Рассмотрим функцию от трех переменных F(X, Y, Z), которая показывает число расстановок при которых Y паровозиков образуют Z групп, причем самый первый паровозик имеет номер X. Для ответа достаточно просуммировать эту функцию по первой переменной. Разберем, чему наша функция равна. Возможны два варианта — первый паровозик образует отдельную группу или тормозит хотя бы один локомотив за собой. В первом случае необходимо суммировать выражения вида F(I, Y – 1, Z – 1) при IX (лидер имеет больший номер и при этом образуется столько же групп).

function F(x, y, z : byte) : Tcal; var i : byte; s : Tcal; begin if D[x, y, z] = -1 then begin s := 0; for i := 1 to x — 1 do s := s + F(i, y — 1, z — 1); for i := x + 1 to y do s := s + F(x, y — 1, z); D[x, y, z] := s end; F := D[x, y, z] end;

Обратите внимание на тип Tcal. Дело в том, что типа LongInt недостаточно, поэтому требуется использование иных средств. В данном случае положение спасает тип Comp (Double тоже подходит).

Граничные условия попробуйте написать самостоятельно. Сделав это, Вы поймете, что написать итеративное решение за время проведения олимпиады практически невозможно (чемпионы не в счет).

Справедливости ради заметим, что задача допускает строгое математическое решение, связанное с подсчетом сочетаний, но оно ненамного эффективнее рассмотренного здесь.

к занятию № 2

Плитки
У Пети имеется неограниченный набор красных, синих и зеленых плиток размером 1 * 1. Он выбирает ровно N плиток и выкладывает их в полоску. Например, при N = 10 она может выглядеть следующим образом:

(буквой К обозначена красная плитка, С — синяя, З — зеленая).
После этого Петя заполняет следующую таблицу:

	Красный	Синий	Зеленый
Красный	Y	Y	Y
Синий	Y	N	Y
Зеленый	Y	Y	N

В клетке на пересечении строки, отвечающей цвету А, и столбца, отвечающего цвету Б, он записывает Y, если в его полоске найдется место, где рядом лежат плитки цветов А и Б и N в противном случае. Считается, что плитки лежат рядом, если у них есть общая сторона. (Очевидно, что таблица симметрична относительно главной диагонали — если плитки цветов А и Б лежали рядом, то рядом лежали и плитки цветов Б и А.) Назовем такую таблицу диаграммой смежности данной полоски.
Так, данная таблица представляет собой диаграмму смежности приведенной выше полоски.
Петя хочет узнать, сколько различных полосок имеет определенную диаграмму смежности. Помогите ему.
(Заметьте, что полоски, являющиеся отражением друг друга, но не совпадающие, считаются разными. Так, полоска

не совпадает с полоской, приведенной в начале условия.)

Формат входных данных
Первая строка входного файла содержит число N (1Формат выходных данных
Выведите в выходной файл количество полосок длины N, имеющих приведенную во входном файле диаграмму смежности.

Плитки

Прежде всего вспомним задачу “Взрывоопасность”. Идея, положенная в основу ее решения, заработает и здесь. Итак, разбиваем все полоски из плиток на 64 группы (соответственно количеству матриц смежности), нумеруя их следующим образом. Берем все возможные матрицы смежности (всего их 64) и выписываем 6 букв из матриц подряд (то, что ниже главной диагонали, нас не интересует, так как никакой информации не несет). Меняем “Y” на “1”, а “N” — на “0” и получаем двоичный код нашей группы. Каждую из групп дополнительно разобьем на три подгруппы, в зависимости от плитки, лежащей справа. Теперь наращиваем полоску вновь справа. Прописать вручную все 576 (64 группы, 3 подгруппы, 3 наращиваемых цвета) возможных комбинаций невозможно. К счастью, рассматривать группы нет необходимости, если воспользоваться битовой арифметикой. Достаточно рассмотреть всевозможные пары крайних плиток и определить смежность, которую они образуют. Она способна в каждой группе либо превратить “N” в “Y” (если ранее не встречалась), либо ничего не изменить. Определив позицию возможного изменения, создаем маску, в которой все биты равны нулю, кроме изменяемого. Остается только применить полученную маску к каждой группе (путем логического “или”). Не стоит забывать, что все эти операции производятся над длинными числами.

Function Check(i, j : shortint; s : integer) : integer;var r, k : integer;begin if ij then begin k := j; j := i; i := k end; if i = 2 then j := j + 2; if i = 3 then j := j + 3; r := 1; for k := 1 to j — 1 do r := r * 2; Check := s or r; {применяем маску r к группе s}end;…for i := 0 to 63 do begin for l := 1 to 3 do for k := 1 to 3 do begin NewS := Check(l, k, i);{определяем новый номер группы} Add(Na[News][k], A[i][l], Na[NewS][k]);{и добавляем в нее все, что было в старой} {Na[News][k] := Na[News][k] + A[i][l] — аналог в обычной арифметике} end end;

к занятию № 2

От автора сайта А.П. Шестакова: Настоящая публикация подготовлена Евгением Владимировичем Брызгаловым, аспирантом кафедры информатики факультета информатики и экономики ПГПУ, неоднократным участником олимпиад сначала школьников, а затем и студентов по программированию. В 1999-2000 учебном году команда, капитаном которой был Е.В. Брызгалов, вышла в полуфинал международных командных соревнований студентов по программированию АСМ.

Статьи к прочтению:

Выходные данные. Владимир Жириновский — Россия 24

Похожие статьи: