Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Оглавление

• Введение 2
• 1.1 Основные определения 4
• 1.2 Условия применимости динамического программирования 6
• ГЛАВА II. КЛАССИЧЕСКИЕ ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ 8
• Задача 1. Числа Фибоначчи 8
• Задача 2. Черепашка 10
• Задача 3. Мячик на лесенке 12
• Задача 4. Степень числа 13
• Задача 5. Робот 14
• Задача 6. Наибольшая общая подпоследовательность (НОП) 17
• Задача 7. Паровозики 19
• Задача 8. Плитки 21
• Задача 9. Задача о рюкзаке (динамическая схема) 23
• Задача 10. Задача о паркете 27
• Литература 32

Введение

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

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

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

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

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

Объектом данного исследования является использование и создание электронного пособия для решения задач динамического программирования.

В качестве предмета исследования рассматривается содержание и реализация электронного пособия.

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

Для реализации поставленной цели необходимо решить следующие задачи:

· Изучить необходимую методическую литературу по динамическому программированию; выполнить анализ предметной области, на основании которого будет подобран материал для электронного учебного пособия;

· Приобрести практические навыки программирования, а именно: приобретение навыков составления алгоритмов разрабатываемых программ в среде Turbo Pascal

· Изучить особенности электронных учебных пособий, ознакомиться с требованиями, предъявляемыми к ним;

динамическое программирование задача математика

ГЛАВА I. ОСНОВЫ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

1.1 Основные определения

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

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

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

Основы теории динамического программирования были заложены Р. Беллманом в 1953 году. Заметим, что слово программирование в приведенном названии (dynamic programming), также как и в “линейном программировании” (linear programming) не означает составление программ для компьютера.

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

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

1.2 Условия применимости динамического программирования

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

Как только свойство оптимальности для подзадач установлено, обычно становится ясно, с каким именно множеством подзадач будет иметь дело алгоритм. А, так как динамическое программирование в сущности вычисляет решение для всех подзадач, то количество различных подзадач, непосредственно через которые выражается решение задач большей размерности, должно быть таким, чтобы было возможно все их (или по крайней мере ту часть, которая непосредственно необходима для решения задач большей размерности) запомнить в таблице. Это и есть второе свойство задачи, существенное при использовании динамического программирования. Благодаря этому свойству при рекурсивном способе решения подобных проблем мы многократно выходим на одни и те же подзадачи. В таком случае говорят, что у переборной задачи (оптимизационной или подсчета количеств) имеются перекрывающиеся подзадачи. В типичных случаях (но не всегда !!!) количество различных подзадач полиномиально зависит от размера исходных данных. Алгоритм, основанный на динамическом программировании, решает каждую из подзадач единожды и заносит его в таблицу. Когда эта же подзадача встречается снова, программа не тратит время на ее решение, а берет готовый ответ из таблицы. Поэтому общее время решения пропорционально размеру заполняемой таблицы в целом, хотя зачастую на этапе реализации алгоритма хранению подлежит лишь ее часть, например, одна строка. В любом случае это время существенно меньше времени перебора всех возможных вариантов с целью выбора среди них лучшего или подсчета общего количества допустимых вариантов.

ГЛАВА II. КЛАССИЧЕСКИЕ ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

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

Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.

Итак, рассмотрим некоторые классические задачи динамического программирования.

Задача 1. Числа Фибоначчи

Условие

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

Формат входных данных

Одно число 0 < N < 47.

Формат выходных данных

Одно число -- 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;

При этом где-то в середине четвертого десятка программа “подвешивает” самый быстрый компьютер. Попробуем разобраться, почему так происходит? Для вычисления 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 -- размер доски.

Далее следует 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];

Задача 3. Мячик на лесенке

Условие

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

Формат входных данных

Одно число 0 < N < 31.

Формат выходных данных

Одно число -- количество маршрутов.

Решение

Пусть мячик находится на некоторой ступеньке с номером 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;

Задача 4. Степень числа

Условие

Даны два натуральных числа n и k. Требуется определить выражение, которое вычисляет kⁿ . Разрешается использовать операции умножения и возведения в степень, круглыми скобками и переменной с именем k.Умножение считается одной операцией, возведению в степень q соответствует q-1 операция. Найти минимальное количество операций, необходимое для возведения в степень n. Желательно сделать это для как можно больших значений n.

Пример. При n=5 необходимо три операции - (k*k)²*k.

Определим массив Op, его элемент Op[i] предназначен для хранения минимального количества операции при возведении в степень i (Op[1]=0). Для вычисления выражения, дающего n-ю степень числа k, арифметические операции применяют в некоторой последовательности, согласно приоритетам и расставленным скобкам. Рассмотрим последнюю примененную операцию. Если это было умножение, тогда сомножителями являются натуральные степени числа k, которые в сумме дают n. Степень каждого из сомножителей меньше n, и ранее вычислено, за какое минимальное число операций ее можно получить. Итак:

opn1:=min{по всем p:1p<n, Op[p]+Op[n-p]+1}.

Если это возведение в степень:

opn2:=min{ для всех p (1) - делителей n, Op[n div p]+p-1}.

Результат - Op[n]=min(opn1,opn2). Фрагмент реализации:

......

Op[1]:=0;

for n:=2 to ???? do begin

opn:=n;{opn - рабочая переменная}

for p:=1 to n-1 do begin

opn:=Min(opn,Op[p]+Op[n-p]+1);{Min - функция поиска минимума двух чисел}

if (n mod p=0) and (p<>1) then opn:=Min(opn,Op[n div p]+p-1);

end;

Op[n]:=opn;

end;

Задача 5. Робот

Условие

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

Формат входных данных

Во входном файле находятся три числа K, X и Y (0 <= K <= 16, |X|, |Y| <= 16), разделенные пробелами.

Формат выходных данных

В выходной файл ваша программа должна поместить одно число -- количество программ для робота.

Решение

В этой задаче мы сталкиваемся с функцией трех переменных: 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 X <> 16 then s := s + F(X + 1, Y, Z - 1);

if Y <> -16 then s := s + F(X, Y - 1, Z - 1);

if Y <> 16 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 i <> 16 then s := s + Way2[i + 1, j];

if j <> -16 then s := s + Way2[i, j - 1];

if j <> 16 then s := s + Way2[i, j + 1];

Way1[i, j] := s

end

end;

Задача 6. Наибольшая общая подпоследовательность (НОП)

Условие

Подпоследовательность можно получить из некоторой конечной последовательности, если удалить из последней некоторое множество ее элементов (возможно пустое). Например, BCDB является подпоследовательностью последовательности ABCBDAB. Будем говорить, что последовательность Z является общей подпоследовательностью последовательностей X и Y, если Z является подпоследовательностью как X, так и Y. Требуется для двух последовательностей X и Y найти общую подпоследовательность наибольшей длины. Заметим, что НОП может быть несколько.

Решение. Задача о НОП обладает свойством оптимальности для подзадач. Здесь подходящее множество подзадач -- множество пар префиксов (начальных частей) двух данных последовательностей. Покажем это. Пусть Z = {z1, z2, …, zk} одна из НОП для X = {x1, x2, …, xm} и Y = {y1, y2, …, yn}. Если xm = yn, то zk = xm = yn (в противном случае мы могли бы дописать xm = yn в конец последовательности Z и получить НОП длины k+1. Кроме того Zk-1 является НОП для Xm-1 и Yn-1 (если это не так, то мы можем к НОП Xm-1 и Yn-1 дописать xm = yn и получить НОП для X и Y более длинную, чем Z. Если zk № xm, то так как Z -- НОП для X и Y, она тем более является НОП для Xm-1 и Y. Аналогично, если zk № yn, то Z -- НОП для X и Yn-1. Максимальное количество подзадач, которое нам может понадобиться решить, равно mЧn (для каждой пары префиксов X и Y). Это позволяет использовать при решении динамическое программирование. Выпишем рекуррентное соотношение между длинами НОП в подзадачах, обозначив за a[i, j] длину НОП для Xi и Yj:

Приведем программу решения этой задачи для последовательностей, состоящих из не более чем 250 символов:

var x,y,z:string;

a:array[0..250,0..250] of byte;

i,j:byte;

begin

readln(x);

readln(y);

fillchar(a,sizeof(a),0);

for i:=1 to length(x) do

for j:=1 to length(y) do

if x[i]=y[j] then a[i,j]:=a[i-1,j-1]+1

else if a[i-1,j]>=a[i,j-1] then a[i,j]:=a[i-1,j]

else a[i,j]:=a[i,j-1];{длина НОП найдена в a[length(x),length(y)]}

z:='';{строим саму НОП}

i:=length(x);

j:=length(y);

while (i>0) and (j>0) do

if x[i]=y[j] then begin z:=x[i]+z; i:=i-1; j:=j-1 end

else if a[i-1,j]>=a[i,j-1] then i:=i-1 else j:=j-1;

writeln(z)

end.

Задача 7. Паровозики

Условие

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

Написать программу, определяющую, сколько начальных расстановок s из N! Возможных дадут в результате p групп движущихся локомотивов.

Формат входных данных

Два числа -- 0 < N < 17 и 0 < p < N + 1.

Формат выходных данных

Одно число -- s.

Решение

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

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 тоже подходит).

Задача 8. Плитки

Условие

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

К	К	К	С	З	К	К	З	К	С

(буквой К обозначена красная плитка, С -- синяя, З -- зеленая).

После этого Петя заполняет следующую таблицу:

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

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

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

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

(Заметьте, что полоски, являющиеся отражением друг друга, но не совпадающие, считаются разными. Так, полоска

С	К	З	К	К	З	С	К	К	К

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

Формат входных данных

Первая строка входного файла содержит число N (1 <= N <= 100). Следующие три строки входного файла, содержащие по три символа из набора {"Y", "N"}, соответствуют трем строкам диаграммы смежности. Других символов, включая пробелы, во входном файле не содержится. Входные данные корректны, т.е. диаграмма смежности симметрична.

Формат выходных данных

Выведите в выходной файл количество полосок длины 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 i > j 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;

Задача 9. Задача о рюкзаке (динамическая схема)

Условие

Рассмотрим задачу. В рюкзак загружаются предметы n различных типов (количество предметов каждого типа не ограничено). Максимальный вес рюкзака не превышает W.

Каждый предмет типа i имеет вес w_i и стоимость v_i (i=1,2, ..., n). Требуется определить максимальную стоимость груза, вес которого не превышает W. Обозначим количество предметов типа i через k_i, тогда требуется максимизировать v₁*k₁+v₂*k₂+...+v_n*k_n при ограничениях w₁*k₁+w₂*k₂+...+w_n*k_nW, где k_i - целые (0k_i[W/w_i]), квадратные скобки означают целую часть числа.

Пусть вес рюкзака должен быть равен W. Формализуем задачу следующим образом.

Шаг i ставится в соответствие типу предмета i=1,2,...,n.

Состояние y_i на шаге i выражает суммарный вес предметов, решение о загрузке которых принято на шагах 0,1,...,i. При этом y_n=W, y_i=0,1,...,W при i=1,2,...,n-1.

Варианты решения k_i на шаге i описываются количеством предметов типа i, 0k_iW/w_i.

Рассмотрим пример. W=6, и дано четыре предмета

i	wi	vi
1	2	50
2	3	90
3	1	30
4	4	140

Схема работы для данного примера приведена на рисунке. В кружочках выделены только достижимые состояния (суммарные веса для каждого шага в соответствии с приведенной выше формализацией) на каждом шаге. В круглых скобках указаны стоимости соответствующих выборов, в квадратных скобках - максимальная стоимость данного заполнения рюкзака. «Жирными» линиями выделен способ наилучшей загрузки рюкзака.

Текст решения.

Const MaxN=???;

MaxK=???;

Type Thing=Record W,V:Word; end;

Var A:array[1..MaxN,0..MaxK] of word;

P:array[1..MaxN] of Thing;

Old,NewA:array[0..MaxK] of longint;

N,W:integer;

...

procedure Solve;

var k,i,j:integer;

begin

fillchar(Old,sizeof(Old),0);

for k:=1 to N do begin{цикл по шагам}

fillchar(NewA,sizeof(NewA),0);

for i:=0 to W do {цикл по состояниям шага}

for j:=0 to i div P[k].W do {цикл по вариантам решения - количеству предметов каждого вида}

if j*P[k].V+Old[i-j*P[k].W]>=NewA[i] then begin

NewA[i]:=j*P[k].V+Old[i-j*P[k].W];

A[k,i]:=j;{здесь j количество предметов?}

end;

Old:=NewA;

end;

end;

Вывод наилучшего решения.

procedure OutWay(k,l:integer);

begin

if k=0 then exit

else begin

OutWay(k-1,l-A[k,l]*P[k].V);{а здесь вес}

Write(A[k,l],' `);

end;

end;

Первый вызов - OutWay(N,W). Эту схему реализации принято называть «прямой прогонкой». Ее можно изменить. Пусть пункт два формализации задачи звучит следующим образом. Состояние y_i на шаге i выражает суммарный вес предметов, решение о загрузке которых принято на шагах i, i+1, ..., N при этом y₁=W y_i=0,1,...,W при i=2,3, ...,N. В этой формулировке схему реализации называют «обратной прогонкой».

Задача 10. Задача о паркете

Условие

Комнату размером n*m единиц требуется покрыть одинаковыми плитками паркета размером 2*1 единиц без пропусков и наложений (m20, n8, m,n -целые). Пол можно покрыть паркетом различными способоми. Например, для m=2, n=3 все возможные способы укладки приведены на рисунке.

Требуется определить количество всех возможных способов укладки паркета для конкретных значений m20, n8. Результатом задачи является таблица, содержащая 20 строк и 8 столбцов.

Элементом таблицы является число, являющееся решением задачи для соответствующих n и m. На месте ненайденных результатов должен стоять символ «*».

Решение.

Пусть i - длина комнаты (1i8), j - ширина комнаты (1j20). «Разрежем» комнату на части. Разрез проводится по вертикали. Плитки, встречающиеся на пути разреза, обходим справа, т.е. при движении сверху вниз на каждом шаге либо обходим справа выступающую клетку, либо нет. При других укладках паркета могут получиться другие сечения. Все варианты сечений легко пронумеровываются, ибо это не что иное, как двоичное число: обход справа плитки соответствует 1, отсутствие обхода - 0. На рисунке сечение выделено «жирной» линией, ему соответствует двоичное число 00100011 (35). Количество различных сечений 2ⁱ (пронумеруем их от 0 до 2ⁱ-1), где i -длина комнаты.



Не будем пока учитывать то, что некоторые из сечений не могут быть получены. Обозначим парой (k,j) комнату с фиксированной длиной i, правый край которой не ровный, а представляет собой сечение с номером k. B[k,j] - количество вариантов укладки паркета в такой комнате. Задача в такой постановке сводится к нахождению B[0,j] - количество укладок паркета в комнате размером (i,j) с ровным правым краем. Считаем, что B[0,0]=1 при любом i, ибо комната нулевой ширины, нулевого сечения и любой длины укладывается паркетом, при этом не используется ни одной плитки. Кроме этого считаем B[k,0]=0 для всех сечений с номерами k<>0, так как ненулевые сечения при нулевой ширине нельзя реализовать.

Попытаемся найти B[k,j] для фиксированного i. Предположим, что нам известны значения B[l,j-1] для всех сечений с номерами l (0l2ⁱ-1). Сечение l считаем совместимым с сечением k, если путем добавления целого числа плиток паркета из первого можно получить второе. Тогда B[k,j]=B[l,j-1], суммирование ведется по всем сечениям l, совместимым с сечением k..

Данные.

var B:array[0..255,0..20] of Comp;

A:array[1..8,1..20] of Comp;{Результирующая таблица}

function St2(k:integer):integer;{Вычисляем k - ю степень 2}

begin

if k<=0 then St2:=1 else St2:=2*St2(k-1);

end;

procedure Solve;{Основная логика}

var i,j,k,l,max:integer;

begin

for i:=1 to 8 do begin {Цикл по значению длины комнаты}

max:=St2(i)-1;

fillchar(B,sizeof(B),0);

B[0,0]:=1;

for j:=1 to 20 do begin {Цикл по значению ширины комнаты}

for k:=0 to max do {Сечение с номером k}

for l:=0 to max do{Сечение с номером l}

if Can(k,l,i) then B[k,j]:=B[k,j]+B[l,j-1];{Совместимость сечений «зарыта» в функции Can(k,l,i)}

A[i,j]:=B[0,j];

end;

end;

end;

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

Таблица

l	k	Значе-ние b	Новое значе- ние b или резуль- тат	Примечания
1	0	false	false	До данного разряда уложено целое число плиток. Для перехода от l к k не надо ничего укладывать. Переходим к следующему разряду.
1	0	true	несовмести-мы	До этого разряда уложено нецелое число плиток, а на этом «закрываем доступ». Сечения несовместимы.
0	1	false	false	Укладываем целую плитку, количество уложенных плиток остается целым.
0	1	true	несовмести-мы	Для перехода к новому сечению в этом разряде необходимо уложить целую плитку. Однако, укладывая её мы «перекрываем» доступ к нецелой плитке, уложенной до этого.
0	0	false	true	До этого разряда между сечениями было уложено целое число плиток, а на этом можно уложить только полплитки.
0	0	true	false	Нецелую плитку дополняем до целой.
1	1	false	несовмести-мы	В этом разряде l лежит целая плитка. Необходимо уложить целую плитку для того, чтобы была 1 в этом разряде сечения k, но сделать этого мы не можем. Аналогично и для случая, когда b=true.

Данный анализ совместимости сечений реализован в функции Can.

function Can(k,l,pi:byte):boolean;{k,l -номера сечений, pi - количество анализируемых разрядов сечений}

var i,d:integer;b:boolean;

begin

Can:=false;b:=false;

for i:=1 to pi do begin

d:=St2(i);

if k and d =0 then{определяется значение разряда с номером d для сечения k}

if l and d =0 then b:=not(b)

else begin if b then exit end

else if (l and d<>0) or b then exit

end;

Can:=not(b);

end;

Осталось сделать еще несколько замечаний. Во-первых, если произведение n на m нечетно (размеры комнаты), то количество укладок паркетом такой комнаты равно 0. Во-вторых, при m=1 и четном n ответ равен 1. В-третьих, результирующая таблица симметрична относительно главной диагонали. В-четвертых, для комнат размером 2*t достаточно просто выводится следующая рекуррентная формула: A[2,t]=A[2,t-1]+A[2,t-2] (ряд Фибоначчи). Эти замечания реализуются на этапе предварительной обработки и приводят к незначительной модификации логики процедуры Solve. Еще одно замечание касается точности результата. Для больших значений n и m необходимо организовать вычисления с использованием длинной арифметики. Мы ограничимся маленькой хитростью - просто выпишем результат при выводе результирующей матрицы.

...

for i:=1 to 20 do begin

for j:=1 to 8 do

if (i=8) and (j=20) then write(`3547073578562247994':20)

else write(A[j,i]:20);

writeln;

end;

Литература

1. Андреева Е.В. Еще раз о задачах на полный перебор вариантов. “Информатика”, №45, 2000.

2. Беллман Р. Динамическое программирование. M. ИЛ, 1960.

3. Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: “Вильямс”, 2000.

4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2000.

5. Гордеев Э.Н. Задачи выбора и их решение. В кн.: Компьютер и задачи выбора. M.: Наука, 1989.

6. Окулов С.М. 100 задач по информатике. Киров: изд-во ВГПУ, 2000. 7. Липский В. Комбинаторика для программистов. М.: “Мир”, 1988.

8. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ / Под ред. И. В.

9. Красикова. -- 2-е изд. -- М.: Вильямс, 2005. -- 1296 с

Щербина О. А. Методологические аспекты динамического программирования // Динамические системы, 2007, вып. 22. -- c.21-36.

Размещено на Allbest.ru