Задача на замощение таблицы m*n домино 1*2

Olechka35

Дата: Вторник, 28.12.2010, 04:46 | Сообщение # 1

Новичок

Группа: Пользователи

Сообщений: 5

Репутация: 0

Замечания: 0%

Статус: Offline

Помогите, пожалуйста! Есть задача:
"Дана таблица MxN. Нужно посчитать количество замощений таблицы доминошками 1*2."
Очевидно, должен быть рекурсивный алгоритм, типа посчитать количество замощений для очередного профиля, но я что-то никак не могу дотумкать.
Препод скинул примерный код на C++:

Code

int n, m;
vector < vector<long long> > d;

void calc (int x = 0, int y = 0, int mask = 0, int next_mask = 0)
{
          if (x == n)
                  return;
          if (y >= m)
                  d[x+1][next_mask] += d[x][mask];
          else
          {
                  int my_mask = 1 << y;
                  if (mask & my_mask)
                          calc (x, y+1, mask, next_mask);
                  else
                  {
                          calc (x, y+1, mask, next_mask | my_mask);
                          if (y+1 < m && ! (mask & my_mask) && ! (mask & (my_mask << 1)))
                     calc (x, y+2, mask, next_mask);
                  }
          }
}
int main()
{
          cin >> n >> m;
          d.resize (n+1, vector<long long> (1<<m));
          d[0][0] = 1;
          for (int x=0; x<n; ++x)
                  for (int mask=0; mask<(1<<m); ++mask)
                          calc (x, 0, mask, 0);
          cout << d[n][0];
}

Но я с C++ не очень, не могу на Паскаль перевести. Помогите, пожалуйста!

P.S. Алгоритм также описан здесь http://informatics.mccme.ru/books/sbory.pdf (на 102-й странице)

Добавлено (28.12.2010, 04:46)
---------------------------------------------
Помогите, пожалуйста! Задача то вроде должна получиться коротенькая, на рекурсию, но я ну никак не могу с этими профилями и битами догнать!!!

Сообщение отредактировал Olechka35 - Вторник, 28.12.2010, 01:54

Seqular

Дата: Вторник, 28.12.2010, 12:28 | Сообщение # 2

Хранитель

Группа: Администраторы

Сообщений: 859

Репутация: 35

Статус: Offline

Честно, сложная задачка. Вот кое-что про создание и работу с динамической матрицей:

Quote

{$R-}
Type
MyType = Word;
Type
PMyVector = ^MyVector;
{ "Строка" динамической матрицы }
MyVector = Array[1 .. 1] of MyType;

MyArrayPtr = ^MyArray;
{ Сама матрица - представляется как массив указателей на "строки" }
MyArray = Array[1 .. 1] of PMyVector;

Var
DynamicArray: MyArrayPtr; { Указатель на матрицу }
Count,
I,J,Size: Word;
Begin
Write('Число элементов массива: ');
ReadLn(Count);

{ Выделяем память под указатели на "строки" }
GetMem(DynamicArray, Count * SizeOf(PMyVector));
{ И для каждой "строки" - выделяем память для хранения данных }
For i := 1 To Count Do
GetMem(DynamicArray^[i], Count*SizeOf(MyType));

For I:=1 to Count do { Lines }
For J:=1 to Count do { Columns }
{ Немного изменяется способ обращения к элементу матрицы }
DynamicArray^[I]^[J]:=I*J;

For I:=1 to Count do
begin
WriteLn;
For J:=1 to Count do
Write(DynamicArray^[I]^[J]:4);
end;

{ Освобождаем память в обратном порядке: }
{ Сначала - удаляем все "строки" }
For i := 1 To Count Do
FreeMem(DynamicArray^[i], Count*SizeOf(MyType));
{ А теперь и указатели на них ... }
FreeMem(DynamicArray, Count * SizeOf(PMyVector));
End.

Поддерживаю также проект сообщество молодых сисадминов

Olechka35

Дата: Вторник, 28.12.2010, 14:53 | Сообщение # 3

Новичок

Группа: Пользователи

Сообщений: 5

Репутация: 0

Замечания: 0%

Статус: Offline

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

Code

program domino;
const
   n=2;
   m=4;
type
    TMatrix = array [1..n, 1..m] of integer;
var d: tMatrix;
i,j:integer;
sum: longint;
function go(d1:tMatrix): longint;
var i, j,k,i1,j1: integer;
s2: longint;
d2:TMatrix;
stop:boolean;
begin
    k:=0;
    i:=1;
    j:=1;
    s2:=0;
    stop:=false;
    for i:=1 to n do
  for j:=1 to m do begin
  if (d1[i,j]=0) and (stop=false) then begin
     stop:=true;
     i1:=i;
     j1:=j;
  end;
  if d1[i,j]=1 then k:=k+1;
  end;
  i:=i1;
  j:=j1;
   if k=n*m then s2:=1
   else begin
  if (i<n) and (d1[i+1,j]=0) then begin
     d2:=d1;
     d2[i,j]:=1;
     d2[i+1,j]:=1;
     s2:=s2+go(d2);
  end;
  if (j<m) and (d1[i,j+1]=0) then begin
     d2:=d1;
     d2[i,j]:=1;
     d2[i,j+1]:=1;
     s2:=s2+go(d2);
  end;
   end;
   go:=s2;
end;

begin
    for i:=1 to n do
       for j:=1 to m do
   d[i,j]:=0;
    sum:=go(d);
    writeln(sum);
    readln;
end.

Сообщение отредактировал Olechka35 - Вторник, 28.12.2010, 17:09

		Среда, 08.01.2025
	Pascal 4 All