Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Кратчайшая цепочка домино

Автор: volsub 22.12.2007 16:45

Доброе утро!

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

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

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

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

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

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

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


Прикрепленные файлы
Прикрепленный файл  dm2.txt ( 142 байт ) Кол-во скачиваний: 170

Автор: Lapp 23.12.2007 19:19

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

{ Домино, рыба с минимальной суммой очков }
{ 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.

Автор: volsub 24.12.2007 4:26


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

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

Цитата(Lapp @ 23.12.2007 15:19) *

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


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

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

Цитата(Lapp @ 23.12.2007 15:19) *

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

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

Автор: Lapp 24.12.2007 18:26

Цитата(volsub @ 24.12.2007 0:26) *
(Почему-то плюсик поставить не могу в репутацию... sad.gif )
Можешь либо дождаться 25 постов, либо попросить кого-то.. smile.gif)))

Цитата(volsub @ 24.12.2007 0:26) *
00. Странно, но у меня при выполнении все время кладет только вправо? Я что-то не правильно делаю? :-?
01. Каждый раз, в независимости от значения "Put(2,3); { <<== Здесь задается первый ход }" - костяшка переворачивается. Т.е. отправляю - пару (2,3), а в результах приходит все равно перевернутая (3:2).
Ох.. надо посмотреть снова. По идее, так быть не должно. В конце я уже вставлял заплатки чисто инстинктивно.. Надо посмотреть на свежую голову.

Цитата(volsub @ 24.12.2007 0:26) *
Кроме того, домино вроде содержит пустышки (т.е. элементы вида 0:0,0:1,0:2... - явно девелоперы домино придумывали... ;) ) , но с этим я смог более менее разобраться сделав - "step over" и поменяв индексы различных циклов на то, чтобы они шли с нуля, а так же изменив размерность массивов.
Сказывается отсутствие игровой практики. Забыл про пустышки.. smile.gif

Автор: Michael_Rybak 24.12.2007 19:07

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


Поздно.

Автор: volsub 24.12.2007 20:05

Цитата(Lapp @ 24.12.2007 14:26) *

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

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

Цитата(Lapp @ 24.12.2007 14:26) *

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

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

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

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

Цитата(Lapp @ 24.12.2007 14:26) *

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

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