zap 26.6.06

Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
Příspěvky: 162
Registrován: 18. 1. 2006 22:29
Typ studia: Informatika Mgr.

zap 26.6.06

Příspěvek od Myshaak »

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.
"Go for the eyes Boo, go for the eyes! Yeahh!!"
aja
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 15. 5. 2006 09:02
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Příspěvek od aja »

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:
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
Uživatelský avatar
jaruch
Supermatfyz(ák|ačka)
Příspěvky: 376
Registrován: 5. 2. 2005 14:06
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Příspěvek od jaruch »

tak pozeram, ze na analyzach, kombagrach a podobnych uroven klesa, tak aspon zapich z C++ a OOP idu stale hore...
Shit shit, who the fuck is shooting us?
I've got a universe to master...
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
Příspěvky: 162
Registrován: 18. 1. 2006 22:29
Typ studia: Informatika Mgr.

pocet reseni

Příspěvek od Myshaak »

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!!"
Odpovědět

Zpět na „2005“