Ha! Dnesni zadani bylo docela originalni: :)
<u><b>*** Lodka ***</b></u>
Napiste program, ktery bude lustit nasledujici hlavolam (navrhne prepravu lidi z jednoho brehu reky na druhy). Program nalezne nejkratsi reseni (nejmensi pocet plaveb lodky), vypise toto reseni, jeho delku, a dale pocet vsech ruznych reseni (!) libovolne delky . Uvazovana reseni pritom nesmi obsahovat opakujici se stavy (v ramci jednoho reseni) - s moznosti opakovani rozmisteni osob na brezich by reseni bylo nekonecne mnoho. *proste neprispoustime, aby nekdo jezdil s lodkou porad sem a tam*
<u>Zadani hlavolamu:</u>
Nesouroda skupina lidi se potrebuje dostat z jednoho brehu reky na druhy. Maji k dispozici jedinou lodku (B), do ktere se vejdou jenom 2 osoby. Ve skupine jsou: otec (F), matka (M), dcera (D), syn (S), policista (P) a gangster (G). Lod umi ridit jen otec, matka nebo policista.
Otec nesmi zustat s dcerou bez pritomnosti matky nebo policisty - tedy ani na brehu ANI NA LODCE - (dcera ho silne provokuje ;) , dostal by infarkt), podobne nesmi zustat se synem bez pritomnosti otce nebo policisty matka. Gangster nesmi zustat o samote s nikym jinym nez s policistou - je nebezpecny. * tohle byl trochu problem, pak to dovysvetlil: gangster muze byt nekde bud sam (pry neutece), nebo kdyz je s nekym, musi u toho byt i policista, jinak by se G neudrzel a zabijel by... ;) *
<u>Zpusob pouziti (priklad s formalne sprvnym vystupem): </u>
> lodka.exe
Pocet reseni: 211 *to neni spravny vysledek, proste jen nake cislo*
Delka nejkratsiho reseni: 9 *to je pravda*
Nejkratsi reseni:
FMDSPGB <->
! FM
DSPG <-> FMB
! M
MDSPGB <-> F
! PG
...
<-> FMDSPGB
<u>Upresneni:</u>
Format vystupu reseni: vzdy seznam osob, co maji preplout na druhou stranu (bez B, lodka pluje vzdy) + stav rozmisteni (levy breh <-> pravy breh) . Inicialni stav je tedy "FMDSPGB <-> ", koncovy stav rozmisteni je " <-> FMDSPGB".
<u>Rady:</u>
Nesnazte se vymyslet zbytecne optimalizace - reseni nemusi byt skalovatelne pro slozitejsi zadani podobnych hlavolamu. Vas program by mel skoncit za nejvys cca 20 sekund - bez optimalizace lze napsat program, ktery zadani vyresi na pocitacich v laborce za mene nez 30 ms. Pameti muzete pouzivat, kolik mate k dispozice.
;)))
Noo, po par minutach nam v podstate prozradil, jakym nejlepsim algoritmem se to da delat - vzit ty pozice jako body grafu (je jich 128 :) ) - dobre totiz je si ty postavy brat jako bity v cisle (takze napr F = 64, M=32 .. B=1) -, podle tech danych pravidel ty body pospojovat -> vytvorit matici sousednosti -> pak pruchodem do hloubky zkusit vsechny moznosti kam jit (pritom hlidat, abych se nazacyklil)-> kdyz dojdu do cile tak vysledku++; a nekde stranou si pamatuju zatim nejkratsi reseni.
Pak nam vysvetloval jak je to s bitovyma operacema (~,&,^, | , << a tak ) a jak se daji pouzit - napr kdyz mam body x a y, tak prikazem (x ^ y) zjistim, kdo zmenil pozici, nebo co delat, kdyz chci zjistit, co je na 5. a 3. bitu apod.
Stejne se nezdalo, ze by to moc pomahalo... :( Zacinalo se asi v 10:15, a kdyz jsem v 14:00 spokojen odchazel, byl jsem myslim jeden z uplne prvnich, co to uspesne dal.
zap 26.6.06
- Myshaak
- Matfyz(ák|ačka) level III
- Příspěvky: 161
- Registrován: 18. 1. 2006 22:29
- Typ studia: Informatika Mgr.
- Login do SIS: michp5am
zap 26.6.06
"Go for the eyes Boo, go for the eyes! Yeahh!!"
-
- Matfyz(ák|ačka) level I
- Příspěvky: 20
- Registrován: 15. 5. 2006 09:02
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Jen by me celkem zajimalo, kolik tech reseni teda melo byt. On si svym resenim nebyl jisty, no a kdyz jsem mu rekla svych 288, bylo to asi ctvrte cislo, ktere se tam objevilo (a zadna dve nebyla tusim stejna ). Coz byla teda celkem vyhoda, protoze k ziskani zapoctu stacilo mit spravne prvni cast (urceni nejkratsi cesty), kdyz nikdo nevedel, jak ma byt spravne ta druhaPocet reseni: 211 *to neni spravny vysledek, proste jen nake cislo*
Computers are useless. They can only give you answers. - Pablo Picasso
Calm down -- it's only ones and zeros.
Bug? That's not a bug, that's a feature. -T. John Wendel
Calm down -- it's only ones and zeros.
Bug? That's not a bug, that's a feature. -T. John Wendel
- Myshaak
- Matfyz(ák|ačka) level III
- Příspěvky: 161
- Registrován: 18. 1. 2006 22:29
- Typ studia: Informatika Mgr.
- Login do SIS: michp5am
pocet reseni
Jo, taky bych rad vedel, kolik to nakonec melo vyjit, nebo jestli na konci dospeli k nejakymu zaveru, kolik to teda je... ;) Mne vyslo 518, rikal ze to je dost blizko tomu jeho reseni, ale ma to pry jinak.
"Go for the eyes Boo, go for the eyes! Yeahh!!"