PRG030 cvičení 1. ročník informatika
- úterý 9:00 K11
- cvičení 3.října
- cvičení 10.října
- cvičení 17.října
- cvičení 24.října
- cvičení 7.listopadu
-->
Obsah cvičení
- cvičení 3.října
- Hledání největšího prvku z N prvků, včetně důkazu, že nejde rychleji
- Hledání druhého největšího prvku z 8 prvků
obecně z N prvků - vzoreček
můžete zkusit dokázat, že nejde rychleji (je to těžší)
- Najděte pro zadané startovní pole cestu věže, která projde přes každé pole právě jednou resp.
takovou, která je "uzavřená" (skončí na sousedním políčku stratovního pole) pro šachovnici 8 x 8
- Totéž pro šachovnici bez levého dolního rohu
- Totéž pro šachovnici bez levého dolního rohu a horního pravého rohu
- Velbloud má nosnost 1000 banánů a spotřebu 1 banán na 1 km. Na hromadě je 3000 banánů,
najděte způsob, jak do co největší vzdálenosti přepravit 1000 banánů.
Zkuste úlohu řešit obecně.
- Písemný úkol:(přineste na cvičení)
Na políčcích pásky sudé délky jsou napsána nějaká kladná čísla. Dva hráči se střídají ve hře.
Hráč na tahu si může vybrat, které z krajních políček pásky si ustřihne. Po skončení hry vyhrál
ten z hráčů, kterému se podařilo ustříhat políčka s větším součtem.
Nalezněte jednoduchou neprohrávající strategii pro hráče, který začíná.
- rozmyslete si (a zkuste napsat pro sebe - nemusíte nosit):
Najděte prostřední z pěti čísel.
Snažte se:
- o co nejjednodušší zápis algoritmu
- o co nejmenší počet porovnání
- cvičení 10.října
- Najděte pro tabulku čokolády o K řádcích a L sloupcích způsob, který ji na co nejmenší počet lámání nakouskuje
na K*L kousků o jednom dílku.
- návrh programu, který čte ze vstupu posloupnost čísel ukončenou číslem -1 a vytiskne tři největší v ní obsažené
a jeho zápis v Pascalu
poznámky:
- konstanty jako nástroj pro usnadnění modifikací programu - zde const konec=-1
- pokud o číslech víme, že jsou všechny větší než nějaké číslo MIN, můžeme vynechat uspořádávání prvních tří přečtených čísel a začít např s čísly MIN-3, MIN-2 a MIN-1
- Úlohy na rozmyšlenou:
- Mladík se uchází o princeznu. Získá ji, pokud uspěje v následující zkoušce.
Mladíka postaví se zavázanýma očima před otáčecí čtvercový stůl, v jehož rozích stojí 4 sklenice.
Každá sklenice může být v jedné ze dvou poloh - dnem vzhůru a dnem dolů. Mladík může v každém kole
šáhnout na kterékoli dvě sklenice a podle své vůle případně změnit polohu některých z nich. Účelem je,
aby všechny 4 sklenice byly ve stejné poloze. Pokud se to stane - princezna mu to oznámí, on v zkoušce
obstál a mohou se chystat zásnuby. Pokud princezna neoznámí úspěch, hra pokračuje dalším kolem. Před
tím však sluha stolkem otočí (mladík neví jak).
- Máme N podezřelých koulí, mezi nimi je nejvýše jedna špatná (tj. lehčí nebo těžší). Pomocí rovnoramenných vah máme na co nejmenší
počet vážení zjistit která ze 2*N+1 možností nastala (buď jsou všechny koule správné nebo je jedna z nich špatná a musíme zjistit nejen,
která to je, ale i zda je lehčí či těžší než správné koule).
Uvažujte dvě varianty zadání: buď máme na počátku kromě podezřelých koulí i nějaké správné nebo nemáme
snažte se najít nějaké zajímavé tvrzení
- písemný domácí úkol:
pošlete mi jako přílohu mailu na na můj oficielní fakultní email s předmětem "Dvc1"
soubor v priloze se bude jmenovat vasim prijmenim, podpis bude i na první řádce v souboru
- prostřední z pěti čísel - úloha z minula
- V urně jsou bílé a černé koule. Hráč (do urny nevidí) v každém tahu vybere dvě koule a vrátí jednu
podle následujícího předpisu:
B+B vrátí B , B+Č vrátí Č , Č+Č vrátí B (musí mít tedy k dispozici i bílé koule mimo urnu)
zjiste na čem záleží jaká koule zbyde v urně jako poslední.
- Minimalizujte počet cest nahoru a dolů elektřikáře, který má za úkol spárovat dolní a horní konce žil
kabelu s n žílami (popište algoritmus elektřikáře a vyjádřete nutný počet cest jako funkci počtu žil).
Řešte např. pro n=27, ale raději obecně.
- cvičení 17.října
obsah bude doplněn
Následující podprogram by měl realizovat matice. Je dobře? Není-li, najděte chyby
hanojské věže