Matematické Fórum

↑ Honzc:
Zase správně:D
Já vím že furt otravuju... sorry.
Mohl bys mi ale napsat postup jak to řešíš? Moc by mi to pomohlo;)
DÍK.

ahoj všem,
chtěl bych se zeptat, kdybych chtěl takovouto úlohu naprogramovat, třeba pro 4 nádoby, metoda prohledávání do šířky, stím, že bych

negeneroval celý stavový strom, ale jen do té doby něž najdu cílový stav. Zajímá mě, jaká programovací technika bude nejpřijatelnější?

Neřeším ani tolik časovou ani pamětovou složitost, jde mi spíš o to, to co nejjednodušeji napsat.


díky

Možná se pletu, ale po zběžném prozkoušení první úlohy a prohlédnutí dalších bych řekl, že počítač ani není potřeba. Vzhledem k zadání bude totiž dost výhodné postupovat odzadu. Netvrdím, že to je extra elegantní nebo univerzální, ale pro úlohy, které se tu objevily by to mělo fungovat rozumně.

Mame nadoby o objemu 10, 7, 7 a 4 litry, v 10-ti litrove nadobe je 10 litru, jedna 7-mi litrova nadoba je prazdna, v druhe 7-mi litrove nadobe je 7 litru, 4 litrova nadoba je prazdna. Jak pomoci prelevani docilime stavu 10, 2, 2, 3 ?

Autor skryl část textu. Zobrazit/skrýt!

Skrytý text:

jiz uvedene reseni ulohy

Pozorování (P): Při každém přelévání se aspoň jedna z "interagujících" nádob naplní nebo vyprázdní ( =: stane se extremistou). Vzhledem k tomu, že ve všech úlohách máme dojít do stavu, kdy je právě jedna z nádob extremista se to bude dost hodit.

Konkrétně k první úloze.
Máme nádoby objemu 10, 7, 7, 4 a dojít do stavu (10 2 2 3). Budeme přemýšlet, jaký byl poslední krok (tedy předposlední stav). Z našich nádob je extremista pouze 1. a proto se musela posledního přelévání účastnit (zřejmě jsme ji plnili). Padá tedy v úvahu přelévání mezi 1-2 (1-3 je to samé) nebo mezi 1-4. Zbývá rozhodnout, kolik se kde přelilo, pokud to vůbec šlo.
Pomůže nám, že i v předposledním stavu potřebujeme aspoň jednoho extremistu (buď to už je výchozí stav, kde je toto bylo ve všech úlohách splněno, nebo nejaký stav, do kterého se dostaneme přeléváním - potom (P)).

Možnosti:
(a)   přelévání mezi 1-2:  předposlední stav musí být tvaru (x y 2 3). Zřejmě 3. ani 4. nádoba není plná/prázdná. 1. nádoba určitě nebude plná (abychom do ní mohli lít) ani prázdná (to by znamenalo, že jsme do ní posledním krokem z 2 přelili 10 litrů - nelze). Extremista tedy musí být 2. Prázdná nebude (lijeme z ní), tedy bude plná (a snadno dopočteme, kolik vody je tedy v 1).
První kandidát na předposlední stav je tedy (5 7 2 3).

(b)   přelévání mezi 1-4:  stejnou úvahou - chci (x 2 2 y),  1., 2. ani 3. extremista nebude -> 4. musí být plná.
Druhý kandidát tedy (9 2 2 4).

A situace se moc nezměnila, takže lze stejnou metodou pokračovat.
Asi jsem to napsal dost děsivě, ale na papíře snad bude naprosto jasné, o co jde. Pořád to je trochu patlačka, ale po pár krocích už se člověk rozkouká (rozmyslí si, co dělá a které možnosti už od pohledu nemá cenu zkoušet) a jde to docela rychle.  Pro takovéto hezké úlohy se to dokonce ani moc nevětví. Zadané úlohy je asi reálné takto dořešit, ale ikdyby se to po pár krocích začalo už moc větvit, a člověk to zas začal zkoušet od začátku, tak má aspoň víc stavů, do kterých se trefovat.

tip: Pokud máš problém přepnout na zpětný chod "přilitím čeho odkud jsem mohl dostat toto", můžeš radši o úloze přemýšlet jako o přelévání nezaplněného objemu. Pravidla pro přelévání vody z X do Y jsou stejná jako pro přelévání prázdnoty z Y do X.

V tom 4. kroku máš ještě jednu možnost:
2  9  4  6  7  6
9  9  4  6  0  6
která snad bude někam pokračovat. Kvůli volbě velikosti nádob to většinou vychází tak, že liji z plné, ale občas se najde překvapení.

Ahoj, poradíte mi taky někdo s přeléváním?
Mám úkol- 5 nádob o objemu 10, 10, 5, 7  a 7 l, počáteční stav je 0, 0, 5, 7, 0 a mám dosáhnout stavu 4, 0, 1, 1, 6 - je to absolutně nad mé síly a nervy...plácám se v tom snad měsíc..Díky za každé nakopnutí.

↑ bejba: Nejsou to náhodou zadání z Brainquestu?