Осталось обсудить некоторые технические приемы, позволяющие написать довольно простую программу, реализующую описанный алгоритм. Если мы поставим в соответствие каждому из уникальных мест в диаграмме смежности свою степень двойки от 20 до 25 (см. массив констант 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 ответ будет вычислен точно. Но, так как для получения результата используется только сложение целых чисел, потери точности при промежуточных вычислениях не будет, по крайней мере пока ответ не станет превышать 263.
{$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
readln(s);
for j:= 1 to 3 do
if upcase(s[j]) = 'Y' then
can[i, j]:= true;
can[i, j]:= true
end
end;
procedure findcode;
var i, j: byte;
{переводим диаграмму смежности в число}
code:= 0;
for j:= i to 3 do
if can[i, j] then
code:= code + magic[i, j]
assign(input, 'input.txt');
reset(input);
assign(output,'output.txt');
rewrite(output);
readdata;
findcode;
fillchar(total, sizeof(total), 0);
{количество полосок длины 1}
total[1, i, 0]:= 1;
for i:= 2 to n do
for j:= 0 to 63 do
for k:= 1 to 3 do
{cчитаем полоски длины i,
c диаграммой смежности j
и оканчивающиеся цветом k}
total[i mod 2, k, j]:= 0;
for l:= 1 to 3 do
{цикл по конечному цвету
полосок длины i - 1}
if magic[k, l] and j <> 0 then
{цвета l и k могут соседствовать
согласно диаграмме смежности j}
total[i mod 2, k, j]:=
total[i mod 2, k, j] +
total[1 - i mod 2, l, j];
total[1 - i mod 2, l, j - magic[k, l]]
answer:= 0;
{суммируем количество полосок с диаграммой
смежности code и различными окончаниями}
for i:=1 to 3 do
answer:=answer + total[n mod 2, i, code];
writeln(answer:0:0)
end.
Похожая задача (“Симпатичные узоры”) предлагалась и на I-ой Всероссийской командной олимпиаде по программированию. Ее условие и решение можно прочитать в [2].
Задача 11. Паркет (Задача VI Всероссийской олимпиады по информатике, 1994 г.)
Комнату размером NM единиц требуется покрыть одинаковыми паркетными плитками размером 21 единицу без пропусков и наложений (1 N 20, 1 M 8). Требуется определить количество всех возможных способов укладки паркета для конкретных значений N и M.
Решение. Пусть M -- ширина комнаты, которую мы зафиксируем. Попытаемся выразить искомое количество укладок паркета для комнаты длины N, через количество укладок для комнаты длиной N - 1. Однако очевидно, что сделать это не удастся, так как существует еще множество укладок, в которых часть плиток пересекает границу между такими комнатами. Следовательно нам опять придется решать дополнительное число подзадач. А именно, введем обобщенное понятие укладки комнаты длиной N - 1: первая часть комнаты длиной N - 2 уложена плотно, а в (N - 1)-й единице измерения длины комнаты могут находиться пустоты (в N-й единице измерения паркета нет). Если наличие плитки в (N - 1)-й единице измерения обозначить 1, а ее отсутствие -- 0, то количество различных окончаний подобных укладок можно пронумеровать двоичными числами от 0 до 2M - 1. Если количество укладок для каждого из окончаний нам известно (часть из них могут оказаться нереализуемыми, то есть соответствующее количество укладок будет равно 0), то мы сможем подсчитать количество различных укладок комнаты длины N. При этом придется проверять совместимость окончаний. Окончания будем считать совместимыми, если путем добавления целого числа плиток к укладе длиной N - 1 с окончанием j, таких что каждая из них увеличивает длину укладки до N, мы можем получить окончание i укладки длиной N. Если способ совмещения укладок существует, то по построению он единственен. Тогда для определения количества укладок с окончанием i длиной N необходимо просуммировать количества укладок длиной N - 1 с совместимыми окончаниями. Для комнаты нулевой длины будем считать количество укладок равным 1. Формирование динамической схемы закончено. Количество хранимых в программе значений при этом равно 22M=2M+1, то есть оно экспоненциально зависит от одного из параметров задачи и существенно его увеличить не представляется возможным. В нашем случае оно равно 512, то есть применение табличного метода решения оказывается реальным. Ответ на вопрос задачи будет получен на N-м шаге алгоритма в элементе таблицы с номером 2M - 1. При максимальном по условию задачи размере комнаты для получения ответа опять потребуется “длинная арифметика”.
Схему программы для решения этой задачи, которая проще предыдущей, можно найти, например, в [3].
После рассмотрения задач 9-11 может сложиться впечатление, что к данному классу относятся лишь задачи подсчета количеств тех или иных конфигураций, в том числе комбинаторных. Конечно же это не так. Примером оптимизационной задачи, решение которой основано на аналогичных идеях, служит задача “Бизнес-классики”, предлагавшаяся на XIII Всероссийской олимпиаде по программированию (см. [4]).
Многие прикладные и олимпиадные задачи легко сформулировать в терминах такой структуры данных как граф. Для ряда подобных задач хорошо изучены эффективные (полиномиальные) алгоритмы их решения. Рассмотрим в данной лекции те из них, которые используют идеи динамического программирования. Но прежде необходимо познакомиться с некоторыми терминами, встречающимися при описании этой структуры.
Граф называется связанным, если для любой пары его вершин существует путь из одной вершины в другую.
Если каждому ребру графа приписано какое-то число (вес), то граф называют взвешенным.
Страницы: 1, 2, 3
