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
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
postřehy
zdůvodněnou volbu algoritmu
representaci dat
dekompozici programu
diskusi
, v případě potřeby iupř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: