# zap 26.6.06

<{ForumPost(poster="Myshaak", timestamp=2006-06-26 17:28:09)}>
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.
<{/ForumPost}>

<{ForumPost(poster="aja", timestamp=2006-06-26 19:25:48)}>

 > Pocet reseni: 211 *to neni spravny vysledek, proste jen nake cislo*

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 :lol: (a zadna dve nebyla tusim stejna :wink: ). 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 druha :wink:
<{/ForumPost}>

<{ForumPost(poster="jaruch", timestamp=2006-06-26 19:31:02)}>
tak pozeram, ze na analyzach, kombagrach a podobnych uroven klesa, tak aspon zapich z C++ a OOP idu stale hore...
<{/ForumPost}>

<{ForumPost(poster="Myshaak", timestamp=2006-06-27 10:35:01)}>
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.
<{/ForumPost}>