IMHO.WS

IMHO.WS (http://www.imho.ws/index.php)
-   Программирование (http://www.imho.ws/forumdisplay.php?f=40)
-   -   Помогите с задачей на логику или комбинаторику (http://www.imho.ws/showthread.php?t=78064)

TDz 21.01.2005 00:04
Помогите с задачей на логику или комбинаторику
 
Нужно выложить доминошки (их 28 всего насколько я знаю) так чтобы начиналось с 1 и заканчивалось 6.

Правила игры в домино думаю все знают. Я пытался создать таблицу чтоб решить комбинатрикой - с помощью графической леснички пости складывается - н овсё равно пару остаёться.

Может кто-то сталкивался с такой задей или знает алгоритм или вообще имеет какие-то мысли - помогите плз

dyr_farot 21.01.2005 11:37
можно и рекурсией обойтись -- ложиш первую кость ( незнаю 0:0 это или 1:1 ) к ней в цикле цепляеш все остальные подходящие и передаеш полученную цепочку в эту же функцию. в ней к цепочке опять цепляеш вс подходящие и...

TDz 21.01.2005 11:59
Problema v tom shto nado ispolzovat vse kosti a kazhdij raz podhodjashih minimum neskolko. Mne sobsno ne progu nado napisat a prosto zadachu reshit - najti takuju cepochku kotoraja ispolzuja vse dominoshki nachinaecca s 1 a konchaecca 6

dyr_farot 21.01.2005 12:09
нет никакой проблемы. используя рекурсию ты пройдеш по всем возможным цепочкам. и, соответственно, получиш искомую

TDz 21.01.2005 12:19
ja hot po softu no ne siljon v programminge :)
toest prosto nado napisat progu dlja perebora vseh variantov?

dyr_farot 21.01.2005 12:24
совсем проще говоря -- да

TDz 21.01.2005 14:33
Itogo immem
mnozhestvo domino - {00, 01,02,03,04,05,06,11,12,13,14,15,16,22,23,24,25,26,33,34,35,36,44,45,4 6,55,56,66}

pravilo slozhenija abs(domino1-domino2)==10 || abs(domino1-domino2)<=6
toest nado proverit 27! variantov

Ja poka raberacca budu kak eto sdelat bez 27 pod-ciklov :) mog bi plz pomoch s kodom dlja generacii vsego lista - toest prosto shtob sgeneriroval ves spisok variantov a ja ego sam rasparsju i videru nuzhnuju stroku ottuda

dyr_farot 21.01.2005 15:34
начал код ваять и понял что правил не помню :)
кость 2:0 и 0:2 -- одинаковы или их две
+ сколько всего костей?

TDz 21.01.2005 15:39
Tolko odna. Kostej 28 kazhecca

added: Pereschital spisok shto daval vishe - taki 28

Ghost 21.01.2005 16:24
TDz
Вот, наковырял на делфе консольную прогу (в турбо-паскале - Stack Overflow :( ). Только работает она очень долго. Сижу думаю, как ее уменьшить...
Код:
program domino;

{$APPTYPE CONSOLE}

uses
  SysUtils;

const
  n = 28;
  d: array [1..28] of byte = (
    00, 01, 02, 03, 04, 05, 06,
        11, 12, 13, 14, 15, 16,
            22, 23, 24, 25, 26,
                33, 34, 35, 36,
                    44, 45, 46,
                        55, 56,
                            66);

var
  r: string;

procedure outDomino(s: string);
var
  i: byte;
begin
  for i := 1 to length(s) do write(d[ord(s[i])]:3);
  writeln;
end;

procedure chain(s: string; last: byte); far;
var
  i: byte;
begin
  if r <> '' then exit;
  if length(s) = n then begin
    if last = 6 then r := s;
  end else begin
    for i := 1 to n do if pos(chr(i), s) = 0 then begin
      if ((d[i] mod 10) = last) or ((d[i] div 10) = last) then
        chain(s + chr(i), (d[i] mod 10) + (d[i] div 10) - last);
    end;
  end;
end;

begin
  r := '';
  chain('', 1);
  writeln('result:');
  outDomino(r);
end.

Saruman 21.01.2005 16:45
Имхо, рекурсия тут не катит - слишком много вариантов для перебора получается. Нужно по-другому как-то подходить.

Ghost 21.01.2005 17:06
Гыхм... Выкинул дупли (один черт потом можно вставить в любое место) и сделал отсечение неполных цепочек, если не осталось костей с 6-кой. Все равно прога что-то долго перебирает... :( Думаю дальше....

Сижу и вот и думаю: а с использованием всех костей точно можно выстроить цепочку с разными числами на концах? Потому что, смотрю на строки, которые выдает прога - получается постоянно цепочка с 1 на концах... :idontnow:

Прога не решаема :contract:
Объясняю: количество костей с одинаковыми значениями (исключаю дупли - они никакой роли ни на что не влияют) четно, но 1 и 6 в наборе должно быть нечетное число. Если выкинуть 1-6, задачу решить можно. А с данными условиями - нельзя :mad:

Saruman 21.01.2005 17:24
Угум, Ghost прав. Привожу другое доказательство.
Представим набор домино в виде графа, вершины 0-7 соответственно номерам на костяшках домино, каждая костяшка - ребро, соединяющее соответствующие вершины. Тогда для того, чтобы получить незамкнутую цепочку костяшек (как в условии задачи), нужно, чтобы ровно две вершины имели нечетное число ребер. В нашем же случае число ребер у всех вершин четно => имеет только замкнутые цепочки.
Если нужно получить незамкнутую цепочку, нужно из полного набора домино удалить одну костяшку (не дубль).

PS: условие взято из решения к задаче про домино вот здесь

Ghost 21.01.2005 17:31
Saruman
Добавлю еще то, что удалять нужно именно 1-6. Если удалить другую, то и на концах цепочки будут значения с удаленной костяшки. О как :contract:

TDz 21.01.2005 18:19
Тоесть спользуя все доминошки можно сделать только неразрывную цепь. Чтобы получить цепочку как надо надо вынять один элемент - в данном случае 1-6 ака 6-1

Saruman 21.01.2005 18:28
TDz
Аха, именно.

dyr_farot 22.01.2005 13:39
проблема в том, что ( насколько я помню ) в домино можно к дюблям кости сбоку прикладывать ( тогда цепочка получается )
если это не учитывать -- фигня получается

TDz 22.01.2005 16:41
Кости действительно поворачиваются чтобы не делать длинных линий, но суть от этого не меняется. Дубли ложатся боком для красоты - опять таки не влияет. Думаю с заданием этим всё ясно. Ещё раз спасибо всем за помощь

dyr_farot 24.01.2005 14:06
так они ложаться так ( если не ошибаюсь):

4
_
2
1|2 2|2 2|3
2
_
5
а если выкладывать именно цепочкой нужно...

с пробелами проблема
боковые костяшки -- над 2/2

TDz 24.01.2005 14:59
hm da eto vopros
nado obmozgovat

aramis 24.01.2005 19:14
тогда ето уже не линия, котороя начинается на а и кончается на б

dyr_farot 24.01.2005 19:19
а про линию никто и не говорил.


Часовой пояс GMT +4, время: 08:38.

Powered by vBulletin® Version 3.8.5
Copyright ©2000 - 2026, Jelsoft Enterprises Ltd.