IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Кратчайшая цепочка домино, (и снова домино только с вариацией - максимальное число оставшихся)
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 6
Пол: Мужской

Репутация: -  0  +


Доброе утро!

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

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

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

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

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

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

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

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


Прикрепленные файлы
Прикрепленный файл  dm2.txt ( 142 байт ) Кол-во скачиваний: 261
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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


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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3





Группа: Пользователи
Сообщений: 6
Пол: Мужской

Репутация: -  0  +



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

Огромное спасибо 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 С ней вроде все в порядке!. Элементы выводятся корректно.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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


Поздно.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6





Группа: Пользователи
Сообщений: 6
Пол: Мужской

Репутация: -  0  +


Цитата(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
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 1:52
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name