Fórum studentů MFF UK

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.

tak pozeram, ze na analyzach, kombagrach a podobnych uroven klesa, tak aspon zapich z C++ a OOP idu stale hore...

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 (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 druha

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.