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
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..
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
↑ 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
↑ 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
↑ 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.
Offline
↑ 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