# zkouška 11.9.

<{ForumPost(poster="stnicolaus", timestamp=2006-09-13 07:30:25)}>
Dnešní zadání byl HLAVOLAM.  
Máme ohrádku s rozměry MxN (max 3600 mm^2) a K kostiček se známou velikostí a počáteční polohou každé kostičky (min rozměr je 400 mm^2). Úkolem je najít takovou posloupnost tahů, která kostičku č. 1 posune na cílové místo CX, CY s minimálním součtem všech provedených tahů. Další info můžete najít [zde](http://forum.matfyz.info/viewtopic.php?t=839) a [zde](http://mff.fear.cz/forum/viewtopic.php?t=265).  
  
- kostičky se mohou pohybovat pouze nahoru, dolů, vpravo, vlevo  
- dostupná paměť je 1MB, na disku je neomezeně místa  
  
Pěkné řešení spočívá v prohledávání do šířky s modifikací, že na každé hladině prohledáváme možnosti od nejmenší dosud uražené vzdálenosti. Je nutné pamatovat si nějak dosažené stavy, abychom se nezacyklili.  
  
  
Zadání malého příkladu bylo napsat proceduru, která v řetězci A, nahradí 1. výskyt řetězce B řetězcem C.  
U ústního jsem dostal haldu a topologické třídění. Ústní proběhlo ve velké pohodě a musím konstatovat, že doc. Töpfer je skvělý člověk  :D
<{/ForumPost}>