Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 27. 11. 2014 09:15

hans66
Příspěvky: 263
Pozice: Student kombinovaného studia
Reputace:   
 

Pascal- Backtracking

Sestavte backtrack algoritmus generující pětice čísel (zobrazeného do kříže) z čísel 1..8 a to tak, že žádné sousední políčka v kříži neobsahují po sobě jdoucí čísla..
//forum.matweb.cz/upload3/img/2014-11/76119_V%25C3%25BDs56t%25C5%2599i%25C5%25BEek.PNG

Chtěl bych vás požádat o radu jak na to? Nenapadá mě jak to udělat. Nechci to od vás naprogramovat, spíš poradit :-)

Offline

 

#2 27. 11. 2014 20:40 — Editoval O.o (27. 11. 2014 21:14)

O.o
Veterán
Příspěvky: 1402
Reputace:   16 
 

Re: Pascal- Backtracking

↑ hans66:

Ahoj,

ja jsem se s tim tedy nikdy nesetkal, ale mam tu jednu moznost, jak bys to mohl dat pomerne snadno dohromady.

Nejprve naznacim kriz:

   A
B X C
   D

Jestli jsem to spravne pochopil, tak na pozici AXD nesmi byt 123, ani 321, ale muze tam byt napr. 468 (je to tak?), stejne tak to plati pro BXD.
Pokud jsem to pochopil spravne, pak bych zacal tim, ze prvni vyberu cislo uprostred, odeberu cisla, ktera nemohu pouzit do kraju a potze tam zbytek rozhazim nahodne.


Presneji takto:

Mam pole cisle Array = [element1,element2,...,elementn], kde n je konecny index podle toho, kolik zvolis cisel pro sestavu.
V tvem pripade: n = 7 (zacinam cislovat od nuly), kdy tvoj pole vypada takto:
array = [1,2,3,4,5,6,7,8];
Na pozici X zvolim jedno nahodne cislo z array, napr:

   A
B 3 C
   D

Do druheho pole si pridam cislo, ktere jsem prave pouzil (predpokladam, ze opakovat se cisla nesmeji, jinak ho sem pridavat nemusis): check = [3];
Dale vim, ze cisla A, B, C a D nesmeji obsahovat 2 ani 4 (protoze ty jsou pred a po 3), pridam je tedy take do druheho pole: check = [3,1,2];
No a ted do cisel A, B, C a D mohu dat nahodne jakekoli cislo z array, pokud to cislo neni v check.
Jinymi slovy, na pozice A, B, C a D nam zustava rozdil mnozin (array - check) = [4,5,6,7,8].

Obecne do check prijde nahodne cislo z array (rekneme cislo X) a k tomu pridas hodnoty X-1 a X+1 a to jsou tri hodnoty, ktere se v krizi nemohou nikde objevit.


Pochopil jsem zadani spravne?

EDIT: podminka bude (n != X && n != X-1 && n != X+1), nemusis si to ukladat do pole navic, ja jsem to psal, protoze se mi to tak snadneji vysvetlovalo jako predstavu dvou mnozin.

Offline

 

#3 28. 11. 2014 10:56

Honzc
Příspěvky: 4641
Reputace:   248 
 

Re: Pascal- Backtracking

↑ hans66:
Než dostaneš nějakou radu, tak je potřeba ujasnit zadání.
Tedy otázky?
1.Mohou se čísla v "kříži" opakovat?
2.Co se myslí pojmem "...žádné sousední políčka v kříži..." Myslí se tím, že mohou sousedit "rohem", ale už ne "stranou"? (i když podle obrázku, kde je napsáno platný to vypadá, že nesmí sousedit pouze stranou stranou)
3.Po sobě jdoucí znamená, že kombinace např. 12 je nepřípustná, ale 21 je kombinace přípustná?

Offline

 

#4 28. 11. 2014 15:58

hans66
Příspěvky: 263
Pozice: Student kombinovaného studia
Reputace:   
 

Re: Pascal- Backtracking

↑ Honzc: toto je přesné zadání
//forum.matweb.cz/upload3/img/2014-11/86609_bactracking.PNG

je nepřípustný aby byla kombinace 21..
co se týče sousedních políček tak to chápu jako v řádku a ve sloupci

Offline

 

#5 28. 11. 2014 20:45

O.o
Veterán
Příspěvky: 1402
Reputace:   16 
 

Re: Pascal- Backtracking

↑ hans66:

Melo by ti stacit, co jsem ti napsal vyse i vzhledem k typu backtracking algoritmu.

Zkusil sis to uz napsat?

Offline

 

#6 29. 11. 2014 15:29

johnnyjohnny
Zelenáč
Příspěvky: 4
Reputace:   
 

Re: Pascal- Backtracking

↑ O.o:

tak něco jsem vymyslel, ale mam to udelany pres repeat until
var
  Application: TMyApplication;
  a,b,c,d,x:integer;
begin
    randomize;
    x:=random(9)+1;

    repeat            //generujeme b
   b:=random(9)+1;
until (b<>x) and (b<>x+1) and (b<>x-1) ;


      repeat            //generujeme c
   c:=random(9)+1;
until (c<>x) and (c<>x+1) and (c<>x-1) ;

      repeat            //generujeme a
   a:=random(9)+1;
until (a<>x) and (a<>x+1) and (a<>x-1) ;


       repeat            //generujeme d
   d:=random(9)+1;
until (d<>x) and (d<>x+1) and (d<>x-1) ;
    writeln('vygenerovany kriz');
               write(' '); writeln(a);
                       write(b);write(x);writeln(c);
               write(' '); writeln(d);


  readln;

end. 

//forum.matweb.cz/upload3/img/2014-11/71360_backtracking.PNG

Offline

 

#7 29. 11. 2014 16:45 — Editoval O.o (29. 11. 2014 16:50)

O.o
Veterán
Příspěvky: 1402
Reputace:   16 
 

Re: Pascal- Backtracking

↑ johnnyjohnny:

Tak hlavne, ze to funguje :).

Jen asi posledni drobnost. Nejsem si stoprocentne jisty, ze tohle bude splnovat zadani jako backtracking algoritmus. Aktualni reseni je (pokud nerozsirime dimenze) nejlepsi, jak je, ale mozna s tim nebude naplno spokojen vyucujici.

Jen pro jistotu si muzes zkusit pripravit reseni, ktere bude naplnovat ideo backtrackingu vice.
Bezpohyby jste se o tom ucili, tak jen ve zkratce: v zasade vyberes jedno cislo a na dalsi pozici dalsi, podivas se jestli mohou uvedle sebe sedet a kdyz ano, tak jdes dal dokud nedojdes na konec, pokud ne, tak vyberes jine cislo a znovu se podivas na podminky, jestli mohou byt vedle sebe.
(zkusim cislo - ano > pokracuji dalsim cislem
                    - ne > opakuji predesly krok s jinym cislem
cele to opakuj istale dokola, dokud nedojdu k vysledku, ktery chci).

Podminku mas hotovou, tak bych si jen priprail pole se vsemi cisly, ktere mam na vyber, zacyklil to a nechal to generovat reseni. Placni to sem az to budes mit at muzeme obdivovat reseni a ostatni vedi, jak jsi to dale resil prosim ;-).

EDITL I kdyz reseni, ktere mas je podle mne plne v souladu se zadanim jako generator (tady by se asi hodilo rict v ramci moznosti nahodny generator). Takze zbytek bych videl jako dobrovolny xD.
Kdybys hledal vsechna reseni, tak by se ti to delalo lepe s tim zacyklenim, nez abys na kazde misto vzdy volil nahodne cislo (nahodnym cislem se ti mohou opakovat kombinace). Zalezi na tom, jakou aplikaci by jsi z toho chtel mit (nahodny generator nebo hledani vsech kombinaci). :-)

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson