Реферат: Динамическое программирование, алгоритмы на графах

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

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

Input.txt	Output.txt
10 YYY YNY YYN	4596

Решение. Очевидно, что перебор всех возможных полосок в данной задаче невозможен, так как их количество может составить 2¹⁰⁰ , поэтому следует попытаться найти динамическую схему решения. Понятно, что для того чтобы подсчитать количество полосок длины N , удовлетворяющих заданной диаграмме смежности, необходимо знать количество допустимых полосок длины N – 1, а также количество полосок, в диаграмме смежности которых один диагональный элемент или два симметричных недиагональных элемента равны “N” вместо “Y” в исходной диаграмме. Далее, при рассмотрении полосок длины N – 2, потребуется знать количество полосок, удовлетворяющих еще большему количеству диаграмм смежности и т. д. В результате на каком то шаге нам может понадобиться информация о количестве полосок практически со всеми возможными диаграммами. Общее количество последних составляет 2⁶ = 64 (уникальными, то есть не повторяющимися, а, значит, определяющими количество различных диаграмм, являются только 6 элементов). Так как при увеличении длины полоски диаграмма может измениться в зависимости от сочетания цветов в последнем (новом) и предпоследнем элементах, подсчитывать полоски следует отдельно для трех различных конечных элементов. Таким образом количество хранимой информации возрастает до 64´3 = 192 значений. Столько же значений будет получено в результате пересчета. Но благодаря тому, что количество полосок длины i выражается только через количество полосок длины i – 1, хранить нужно лишь эти 2´192 = 384 значения. Несмотря на малый размер таблицы (массив total в программе) следует отметить, что ее размер экспоненциально зависит от одного из входных параметров — количества цветов k , а именно: 2´k ´2^{k (k +1)/2} . Например, для 8 цветов необходимо было бы хранить 2⁴⁰ элементов, что нереально. Этим данная задача отличается от рассмотренных ранее.

Осталось обсудить некоторые технические приемы, позволяющие написать довольно простую программу, реализующую описанный алгоритм. Если мы поставим в соответствие каждому из уникальных мест в диаграмме смежности свою степень двойки от 2⁰ до 2⁵ (см. массив констант magic в программе), то каждой диаграмме может быть поставлен в соответствие номер от 0 до 63, равный сумме тех степеней двоек, которые соответствуют значениям “Y” (см. процедуру findcode). Если мы подсчитываем количество полосок для диаграммы с номером j , то совместимость добавляемого цвета k стоявшему ранее последним цвету l согласно диаграмме j можно проверить так: magic[k, l] and j <> 0. Данное условие, построенное с помощью битовой операции над целыми числами and, означает наличие в j- ой диаграмме смежности элемента “Y” на пересечении k -й строки и l -го столбца (соответствующая степень двойки массива magic содержится в двоичном представлении числа j ). Выражение j - magic[k, l] соответствует замене в диаграмме с номером j упомянутого элемента “Y” на “N” (по другому это выражение можно было бы записать как j xor magic[k, l]). Подробнее о битовых операциях над целыми числами можно прочитать в [1]. Последний прием заключается в том, что мы не будем на каждом шаге переприсваивать полученные значения элементам массива, предназначенного для хранения результатов предыдущего шага. Для этого результаты для полосок четной длины i будем помещать в половину массива total с первым индексом 0, а нечетные — с индексом 1. В любом из этих случаев значения предыдущего шага доступны по индексу [1 – i mod 2]. Кроме того, ответ на решение этой задачи при всех N , удовлетворяющих условию, требует самостоятельной организации вычислений с помощью так называемой “длинной арифметики” (см., например, [1, 3]).

Приведем программу для решения этой задачи, но использующую вместо “длинной арифметики” тип данных extended, сохраняющий максимально возможное количество значащих цифр (попробуйте модернизировать программу самостоятельно). То есть не для всех значений N ответ будет вычислен точно. Но, так как для получения результата используется только сложение целых чисел, потери точности при промежуточных вычислениях не будет, по крайней мере пока ответ не станет превышать 2⁶³ .

{$N+}

const magic: array [1..3, 1..3] of byte =

((1, 2, 4),

(2, 8, 16),

(4, 16, 32));

var n,i,j,k,l,code: longint;

can: array [1..3, 1..3] of boolean;

total: array [0..1, 1..3, 0..63] of extended;

answer: extended;

procedure readdata;

var s: string;

i, j: byte;

begin

readln(n);

fillchar(can, sizeof(can), false);

for i:= 1 to 3 do

begin

readln(s);

for j:= 1 to 3 do

if upcase(s[j]) = 'Y' then