Форум «Всё о Паскале» _ Задачи _ Кратчайшая цепочка домино
Автор: volsub 22.12.2007 16:45
Доброе утро!
Любимая сестра попросила помочь с программами к сессии. Но вот не задача, я последние 5 лет вообще не писал ничего. Поэтому я несколько в шоке от того, что преподают на первом курсе!
=================================== Задание: Костяшки N домино (N максимальное кол-во очков на половинке костяшки, обычно 6) по правилам этой игры выкладываются в прямую цепочку, начиная с выбранной произвольной костяшки, в оба конца до тех пор, пока это возможно.
Найти: Найти такой вариант выкладывания заданных костяшек, при котором к моменту, когда цепочка не может быть продолжена, "на руках" останется максимальное число очков.
Результат: Вывести вариант на экран. ===================================
Поиск использовал, нашел тему в форуме: "задача про домино, поиск наибольшей замыкающейся последовательности" (ссылку увы привести не могу) :-(
Скопировал исходник, создал файл со своими данными. Но судя по всему, я несколько не понимаю сам принцип работы данного кода. Или данные не корректным образом отдаю программе.
Вот, решение с рекурсией (читай: полным перебором). Вроде, работает, но стопроцентной уверенности, если честно, нету (думал, решу за пять минут, но вышло несколько побольше, и на доводку меня не хватило).. Смешно, но самым сложным было вывести полученную цепочку .
{ Домино, рыба с минимальной суммой очков } { 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 за помощь. (Почему-то плюсик поставить не могу в репутацию... )
Цитата(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)
Смешно, но самым сложным было вывести полученную цепочку .
С ней вроде все в порядке!. Элементы выводятся корректно.
Автор: Lapp 24.12.2007 18:26
Цитата(volsub @ 24.12.2007 0:26)
(Почему-то плюсик поставить не могу в репутацию... )
Можешь либо дождаться 25 постов, либо попросить кого-то.. )))
Цитата(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" и поменяв индексы различных циклов на то, чтобы они шли с нуля, а так же изменив размерность массивов.
Сказывается отсутствие игровой практики. Забыл про пустышки..
Автор: Michael_Rybak 24.12.2007 19:07
Цитата
Можешь либо дождаться 25 постов, либо попросить кого-то..
Поздно.
Автор: volsub 24.12.2007 20:05
Цитата(Lapp @ 24.12.2007 14:26)
Можешь либо дождаться 25 постов, либо попросить кого-то.. )))
Спасибо, Michael_Rybak за то что "отплюсовали"!
Цитата(Lapp @ 24.12.2007 14:26)
Ох.. надо посмотреть снова. По идее, так быть не должно. В конце я уже вставлял заплатки чисто инстинктивно.. Надо посмотреть на свежую голову.
Я вчера до трех проходил trace'ром - следил за значениями - но так и не смог разобраться. Единственное, что удалось сделать - это реально начать строить цепочку в обе стороны, но фишка в том, если допустим беру пару (2:1) строиться начинает обе стороны - но в обе с двойки.
Т.е. примерно так: 3:3 3:2 (1:2) 2:4 4:6 ....
Я так понимаю, что именно при первом проходе не верно начальная инициализация происходит?
Цитата(Lapp @ 24.12.2007 14:26)
Сказывается отсутствие игровой практики. Забыл про пустышки..