Zkouška - Martin Mareš - 11.1.2008

stnicolaus at 2008-01-11 23:13:57

Zadání dnešní písemky bylo následující:

najděte algoritmus pro výpočet obsah mnohoúhelníku, jehož strany jsou rovnoběžné se souřadnicovými osami a souřadnice jsou celá čísla
najděte algoritmus, který zjistí dělitelnost binárně zapsaného čísla 3
popište Dinicův algoritmus (včetně důkazu korektnosti a složitostí...)

Jak už tu psali lidé přede mnou, času je víc než dost. Já jsem dnes odcházel po 5 hodinách a nebyl jsem poslední :D Atmosféra na zkoušce příjemná a dnešní zadání navíc nebylo z nejtěžších.

Lukas Mach at 2008-01-13 00:25:38

Ten polygon z jednicky muze protinat sam sebe nebo ne? Jestli ne, je na to proste vzorecek (pardon, jestli mi neco uchazi, mam pocit, ze takovy veci jsme na minuly rok na ADS II nemeli).

stnicolaus at 2008-01-13 08:05:39

Lukas Mach wrote:Ten polygon z jednicky muze protinat sam sebe nebo ne? Jestli ne, je na to proste vzorecek (pardon, jestli mi neco uchazi, mam pocit, ze takovy veci jsme na minuly rok na ADS II nemeli).

Nemůže se protínat. Řešení je jednoduché: projdou se postupně všechny body a k obsahu se pořád přičítá y1*(x2-x1).