2.2.8. Задача о паркете
Комнату размером n*m единиц требуется покрыть одинаковыми плитками паркета размером 2*1 единиц без пропусков и наложений (m£20, n£8, m,n -целые). Пол можно покрыть паркетом различными способоми. Например, для m=2, n=3 все возможные способы укладки приведены на рисунке.
Требуется
определить количество всех возможных
способов укладки паркета для конкретных
значений m£20,
n£8.
Результатом задачи является таблица,
содержащая 20 строк и 8 столбцов.
Элементом таблицы является число, являющееся решением задачи для соответствующих n и m. На месте ненайденных результатов должен стоять символ «*».
Решение. Пусть i - длина комнаты (1£i£8), j - ширина комнаты (1£j£20). «Разрежем» комнату на части. Разрез проводится по вертикали. Плитки, встречающиеся на пути разреза, обходим справа, т.е. при движении сверху вниз на каждом шаге либо обходим справа выступающую клетку, либо нет. При других укладках паркета могут получиться другие сечения. Все варианты сечений легко пронумеровываются, ибо это не что иное, как двоичное число: обход справа плитки соответствует 1, отсутствие обхода - 0. На рисунке сечение выделено «жирной» линией, ему соответствует двоичное число 00100011 (35). Количество различных сечений 2i (пронумеруем их от 0 до 2i-1), где i -длина комнаты.
Считаем, что B[0,0]=1 при любом i, ибо комната нулевой ширины, нулевого сечения и любой длины укладывается паркетом, при этом не используется ни одной плитки. Кроме этого считаем B[k,0]=0 для всех сечений с номерами k<>0, так как ненулевые сечения при нулевой ширине нельзя реализовать.
Попытаемся найти B[k,j] для фиксированного i. Предположим, что нам известны значения B[l,j-1] для всех сечений с номерами l (0£l£2i-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;