задача про домино, поиск наибольшей замыкающейся последовательности Опции

[Zenon]

Здравствуйте.
Поставили перед нами такую задачe. Дано n кубиков домино, как известно они имеют номера с двух сторон, но в задаче сказано, что для данного случая они не ограничены цифрой 6, т.е. значения с обеих сторон могут быть боле 6, например 16 и 12 и т.п. (какие - то разумные пределы конечно есть, но просто больше чем в настоящих, т.е. чем 6). Задние состоит в том, чтобы найти самую длинную замкнутую цепочку.... Если честно теряюсь в догадках и по вопросу алгоритма и по вопросу реализации....
Надеюсь на Вашу помощь.

[volvo]

Ну, поскольку ты не написал, на каком языке тебе нужно решение - вот так программа выглядит на Паскале (если костяшек больше 28, измени MAX)...

{$M $C000,0,650000}
const
  max         = 28;
  yes         : boolean = false;

  max_num = 20; { <--- Максимальное число на костяшке домино !!! }

var
  m           :array [0..max_num,0..max_num] of boolean;
  n           :byte;
  cep,best :array [1..max*2] of byte;
  p,maxlen        :integer;

procedure ReadData;
var i,a,b : byte;
begin
  p:=1; maxlen:=0;
  assign(input,'dm.txt'); reset(input);
  fillchar(cep,sizeof(cep),0);
  fillchar(m,sizeof(m),false);
  readln(n);
  for i:=1 to n do begin
     readln(a,b);
     m[a,b]:=true; m[b,a]:=true;
  end;
  close(input);
end;

procedure WriteResults;
var i : integer;
begin
  writeln(maxlen div 2);
  if (maxlen>1) then begin
     i:=1;
     while (i<pred(maxlen)) do begin
        write(' <', best[i], ' ', best[i+1],'> :');
        inc(i,2);
     end;
     write(' <', best[pred(maxlen)], ' ', best[maxlen], '>');
  end;
  writeln;
end;

procedure s_cep;
begin
  if (p-1>maxlen) then begin
     move(cep,best,p-1);
     maxlen:=p-1;
     yes:=(maxlen div 2=n);
  end;
end;

function exist(k:integer):boolean;
var i : integer;
begin
  i:=0; while (i<=max_num) and not(m[k,i]) do inc(i);
  exist:=(i<=max_num);
end;

procedure make_cep(f:integer);
var s:integer;
begin
  if yes then exit;
  if (m[f,f]) then begin
         m[f,f]:=false;
         cep[p]:=f; cep[succ(p)]:=f; inc(p,2);
         if exist(f) then make_cep(f) else s_cep;
         dec(p,2);
         m[f,f]:=true;
  end else
  for s:=0 to max_num do
      if (m[f,s]) then begin
         m[f,s]:=false; m[s,f]:=false;
         cep[p]:=f; cep[succ(p)]:=s; inc(p,2);
         if exist(s) then make_cep(s) else s_cep;
         dec(p,2);
         m[f,s]:=true; m[s,f]:=true;
      end;
end;

var i:integer;
begin
  ReadData;
  for i:=0 to max_num do make_cep(i);
  WriteResults;
end.

При исходном файле

5
1 2
1 3
2 16
3 6
5 16

Программа вывела результат:

5
<5 16> : <16 2> : <2 1> : <1 3> : <3 6>

Тестируй...