Реферат: Динамическое программирование, алгоритмы на графах
for i:=1 to k do
inc(table[n,k],t(n-k,i))
end;
t:=table[n,k]
end;
begin
read(n);
fillchar(table,sizeof(table),0);
for i:=1 to n do
begin
table[i,i]:=1;
table[i,1]:=1
end;
{неопределенные элементы метим –1}
for i:=2 to n do
for j:=2 to i-1 do
table[i,j]:=-1;
sum:=0;
for i:=1 to n do
sum:=sum+t(n,i);
writeln('sum=',sum)
end.
Задача 10 . Плитки (Чемпионат школьников по программированию, Санкт-Петербург, 1999 г. ).
У Пети имеется неограниченный набор красных, синих и зеленых плиток размером 1´1. Он выбирает ровно N плиток и выкладывает их в полоску. Например, при N = 10 она может выглядеть следующим образом:
| К | К | К | С | З | К | К | З | К | С |
(Буквой К обозначена красная плитка, С – синяя, З – зеленая)
После этого Петя заполняет следующую таблицу, которая в данном примере выглядит так:
| Красный | Синий | Зеленый | |
| Красный | Y | Y | Y |
| Синий | Y | N | Y |
| Зеленый | Y | Y | N |
В клетке на пересечении строки, отвечающей цвету А, и столбца, отвечающего цвету Б, он записывает "Y", если в его полоске найдется место, где рядом лежат плитки цветов А и Б и "N" в противном случае. Считается, что плитки лежат рядом, если у них есть общая сторона. (Очевидно, что таблица симметрична относительно главной диагонали – если плитки цветов А и Б лежали рядом, то рядом лежали и плитки цветов Б и А.) Назовем такую таблицу диаграммой смежности данной полоски.
Так, данная таблица представляет собой диаграмму смежности приведенной выше полоски.
Помогите Пете узнать, сколько различных полосок имеет определенную диаграмму смежности (заметьте, что полоски, являющиеся отражением друг друга, но не совпадающие, считаются разными. Так, полоска
| С | К | З | К | К | З | С | К | К | К |