Кратчайшая цепочка домино, (и снова домино только с вариацией - максимальное число оставшихся) Опции

[volsub]

Доброе утро!

Любимая сестра попросила помочь с программами к сессии. Но вот не задача, я последние 5 лет вообще не писал ничего. Поэтому я несколько в шоке от того, что преподают на первом курсе!

===================================
Задание:
Костяшки N домино (N максимальное кол-во очков на половинке костяшки, обычно 6) по правилам этой игры выкладываются в прямую цепочку, начиная с выбранной произвольной костяшки, в оба конца до тех пор, пока это возможно.

Найти:
Найти такой вариант выкладывания заданных костяшек, при котором к моменту, когда цепочка не может быть продолжена, "на руках" останется максимальное число очков.

Результат:
Вывести вариант на экран.
===================================

Поиск использовал, нашел тему в форуме: "задача про домино, поиск наибольшей замыкающейся последовательности" (ссылку увы привести не могу) :-(

Скопировал исходник, создал файл со своими данными. Но судя по всему, я несколько не понимаю сам принцип работы данного кода. Или данные не корректным образом отдаю программе.

Ткните носом, куда стоит копать?

Сообщение отредактировано: volsub - 22.12.2007 12:46

[Lapp]

Вот, решение с рекурсией (читай: полным перебором). Вроде, работает, но стопроцентной уверенности, если честно, нету (думал, решу за пять минут, но вышло несколько побольше, и на доводку меня не хватило)..
Смешно, но самым сложным было вывести полученную цепочку .

{ Домино, рыба с минимальной суммой очков }
{ by Lapp }
const
  n=8; {размерность домино}

var
  d,Fish: array[1..n,1..n]of integer;
  Right,Left,m,mx,xx,i,j,k,l: integer;
  s,sl,sr: string;

function Put(l,r:integer):boolean;
var
  i,j,x,R0,L0: integer;
  f: boolean;
begin
  if d[l,r]=0 then begin
    Inc(m);
    R0:=Right;
    L0:=Left;
    if r=Left then Left:=l else Right:=r;
    if Left=0 then Left:=l;
    d[l,r]:=-1;
    d[r,l]:=m;
    f:=true;
    for i:=1 to n do f:=f and Put(i,Left);
    for i:=1 to n do f:=f and Put(Right,i);
    if f then begin
      x:=0;
      for i:=1 to n do for j:=1 to n do if d[i,j]=0 then x:=x+i+j;
      if x>xx then begin
        Fish:=d;
        xx:=x;
        mx:=m
      end
    end;
    d[l,r]:=0;
    d[r,l]:=0;
    Right:=R0;
    Left:=L0;
    Dec(m);
    Put:=false
  end
  else Put:=true
end;

begin
  xx:=0;
  m:=0;
  for i:=1 to n do for j:=1 to n do d[i,j]:=0;
  Left:=0;
  Right:=0;
  Put(2,3); { <<== Здесь задается первый ход }

  for i:=1 to n do begin
    for j:=1 to n do Write(Fish[i,j]:3);
    WriteLn
  end;
  m:=1;
  s:='';
  for k:=1 to mx do
  for i:=1 to n do begin
    for j:=1 to n do if Fish[i,j]=m then begin
      Str(i,sl);
      Str(j,sr);
      if j=l then Insert(sl+':'+sr+' ',s,1) else s:=s+' '+sl+':'+sr;
      l:=i;
      Inc(m)
    end
  end;
  WriteLn(s);
  ReadLn
end.

Сообщение отредактировано: Lapp - 23.12.2007 15:22

[volsub]

Добрый вечер.

Огромное спасибо Lapp за помощь. (Почему-то плюсик поставить не могу в репутацию... )

Вот, решение с рекурсией (читай: полным перебором). Вроде, работает, но стопроцентной уверенности, если честно, нету (думал, решу за пять минут, но вышло несколько побольше, и на доводку меня не хватило)..

Исходный код забрал, потестировал и вот возникли вопросы:
00. Странно, но у меня при выполнении все время кладет только вправо? Я что-то не правильно делаю? :-?
01. Каждый раз, в независимости от значения "Put(2,3); { <<== Здесь задается первый ход }" - костяшка переворачивается. Т.е. отправляю - пару (2,3), а в результах приходит все равно перевернутая (3:2).

Кроме того, домино вроде содержит пустышки (т.е. элементы вида 0:0,0:1,0:2... - явно девелоперы домино придумывали... ;) ) , но с этим я смог более менее разобраться сделав - "step over" и поменяв индексы различных циклов на то, чтобы они шли с нуля, а так же изменив размерность массивов.

Смешно, но самым сложным было вывести полученную цепочку .

С ней вроде все в порядке!. Элементы выводятся корректно.

[Lapp]

(Почему-то плюсик поставить не могу в репутацию... )

Можешь либо дождаться 25 постов, либо попросить кого-то.. )))

00. Странно, но у меня при выполнении все время кладет только вправо? Я что-то не правильно делаю? :-?
01. Каждый раз, в независимости от значения "Put(2,3); { <<== Здесь задается первый ход }" - костяшка переворачивается. Т.е. отправляю - пару (2,3), а в результах приходит все равно перевернутая (3:2).

Ох.. надо посмотреть снова. По идее, так быть не должно. В конце я уже вставлял заплатки чисто инстинктивно.. Надо посмотреть на свежую голову.

Кроме того, домино вроде содержит пустышки (т.е. элементы вида 0:0,0:1,0:2... - явно девелоперы домино придумывали... ;) ) , но с этим я смог более менее разобраться сделав - "step over" и поменяв индексы различных циклов на то, чтобы они шли с нуля, а так же изменив размерность массивов.

Сказывается отсутствие игровой практики. Забыл про пустышки..

[Michael_Rybak]

Можешь либо дождаться 25 постов, либо попросить кого-то..

Поздно.

[volsub]

Можешь либо дождаться 25 постов, либо попросить кого-то.. )))

Спасибо, Michael_Rybak за то что "отплюсовали"!

Ох.. надо посмотреть снова. По идее, так быть не должно. В конце я уже вставлял заплатки чисто инстинктивно.. Надо посмотреть на свежую голову.

Я вчера до трех проходил trace'ром - следил за значениями - но так и не смог разобраться. Единственное, что удалось сделать - это реально начать строить цепочку в обе стороны, но фишка в том, если допустим беру пару (2:1) строиться начинает обе стороны - но в обе с двойки.

Т.е. примерно так:
3:3 3:2 (1:2) 2:4 4:6 ....

Я так понимаю, что именно при первом проходе не верно начальная инициализация происходит?

Сказывается отсутствие игровой практики. Забыл про пустышки..

Я тоже не игрок. В вики прочёл!