# Zkouška pondělí 7.6.2021 - Euklidovské konstrukce

<{ForumPost(poster="pheeck", timestamp=2021-06-13 15:36:41)}>
**Písemná část**  
  
1 úloha  
2 hodiny času  
začalo se až když nebyly žádné otázky k zadání (což v našem případě trvalo 50 minut :D)  
Holan a Pergel  
  
Člověk se toho snaží sepsat co nejvíc na papír (nebo do markdownu, v mém případě) - každý nápad  
a pak papír odevzdá a s Holanem se v ústní části na tom papíru snaží najít alespoň náznak řešení.  
Taková je moje zkušenost. S Pergelem to bude asi jiné.  
  
**Hledání Euklidovských konstrukcí**  
*Zde je odkaz na pdf: [https://ksvi.mff.cuni.cz/~holan/210607_ ... trukce.pdf](https://ksvi.mff.cuni.cz/~holan/210607_zk_konstrukce.pdf)  
Pravděpodobně na Holanově stránce však nebude moc dlouho viset, takže tady je i hůře zformátovaná verze:*  
*edit: došlo mi, jak se na na forum nahrávají soubory, takže tedy je pdf, pokud odkaz už nefunguje:*

210607_zk_konstrukce.pdf

Euklidovská konstrukce je množina objektů tří druhů:  
 bod  
 přímka  
 kružnice  
  
Postup konstrukce  
je posloupnost kroků, kterými z jedné (vstupní) konstrukce  
vytvoříme konstrukci jinou (výstupní).  
  
Kroky přitom mohou být dvou druhů:  
 AB sestrojit přímku procházející body A a B  
 A(B) sestrojit kružnici se středem A procházející bodem B  
Po každém kroku navíc určíme průsečíky vytvořené přímky nebo  
kružnice se stávajícími přímkami nebo kružnicemi  
a přidáme je do konstrukce jako nové body.  
Počet kroků budeme nazývat délka (postupu) konstrukce.  
  
Příklad: Nalezení středu dvou daných bodů A a B:  
(1) p1=AB  
(2) k2=A(B)  
(3) k3=B(A),{C, D}=k2∩k3  
(4) p4=CD,{S}=p1∩p4  
Znakem ∩ značíme průsečík.  
  
**Zadání**  
Navrhněte program, který pro všechna celá čísla N od 1 do 20  
zjistí minimální délku konstrukce potřebnou k tomu, abychom pro  
dva různé body A a B sestrojili bod X, který dělí vzdálenost AB  
v poměru 1:N, tedy  
|AX| = |AB|/(1+N) a |XB| = |AB|*N/(1+N)  
  
Pro N=1 je odpověď 4, protože výše uvedený postup konstrukce úlohu  
řeší na čtyři kroky a kratší postup neexistuje.  
  
V odpovědi popište  
1) postřehy  
2) zdůvodněnou volbu algoritmu  
3) representaci dat  
4) dekompozici programu  
5) diskusi  
, v případě potřeby i  
0) upřesnění zadání.  
  
Paměť, čas: Přiměřeně, žádná zvláštní omezení.  

----

**Řešení písemné části**  
  
Prohledávání stavového prostoru do šířky, popř. podle Holana do hloubky, ale s tím,  
že omezíme maximální hloubku (zanoření) (tedy chtěl takový hybrid prohledávání do hlouky a do šířky).  
Bude potřeba dosadit si vlastní konkrétní vzdálenosti a s nimi počítat.  
Pardon, nepodám detailní postup, protože jsem písemnou část měl špatně.  
  
Asymptotická složitost v závislosti na n by nebyla hezká. Šlo ale o to, uvědomit si,  
že i tak by pro to n = 1...20 algoritmus alespoň během pár hodin doběhl.  
Doporučuju tohle: Když dostanete v úloze až podezdřele malý vstup, přemýšlejte  
i nad šíleně neefektivními řešeními.  
  

----

  
**Ústní část**  
  
Na ústní část jsem šel o dva dny později, distančně a měl jsem Holana.  
  
Nějaký čas jsme strávili nad mým papírem, který byl obsáhlý, ale správné  
řešení na něm nebylo. Zkoušel jsem hodně věcí. Za konečné řešení jsem  
označil nějaké optimalizování algoritmu pro rozdělení přímky na více částí  
ze základky/střední. Za to, že jsem v jedné části papíru měl náznaky,  
že jsem nad prohledáváním stavového prostoru přemýšel a za to, že jsem  
na papíru rozebíral všemožné způsoby (grafy, dynamické p., rozděl a panuj, ...),  
jak by se to možná (ne)dalo řešit jsem dostal pomyslné bonusové body, ale  
přece jenom jsem to měl špatně.  
  
Holan po mně pak chtěl, abych mu řekl něco o virtuálních a abstraktních metodách.  
Dal mi čas na rozmyšlenou a já jsem mu řekl nejen o tom, jak ty metody fungují,  
ale i o prototypech a tabulce virtuálních metod a jak konstruktory předků  
postupně vyplňují pointery na ty správné funkce.  
  
Tohle mě zachránilo a já odcházel s dvojkou.

*Attachments:*

- *[210607_zk_konstrukce.pdf](/Forum%20archiv/Attachments/7354_9bf2ce0a74737d81075c7cfb05e500ff)*

<{/ForumPost}>