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ů - rozmyslete vzoreček
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
na šachovnici bez rohového pole a1
na šachovnici bez dvou protilelehlých rohových polí (např. a1 a h8)
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).
Našli jsme způsob jak na dvě vážení jde úlohu vyřešit pro N=3, a pro N=9 na tři vážení.
Na rozmyšlenou:
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ě.
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í strategie pro hráče, který začíná.
Vězni, žalářníci a lampa
Ve vězení je N vězňů odsouzených na doživotí a každý z nich má svou vlastní celu bez oken. Každý den je jeden z vězňů odveden do speciální místnosti, kde je vyslýchán. V této místnosti je na stropě žárovka a na zdi vypínač. Před prvním výslechem je žárovka zhasnutá. Během výslechu může vězeň žárovku pomocí vypínače libovolně rozsvěcet a zhasínat. Když další den přivedou do místnosti dalšího vězně na výslech, tak je žárovka v takovém stavu (rozsvícená nebo zhasnutá), v jakém ji nechal předchozí vězeň. Vězni jsou vyslýcháni v libovolném pořadí a každý z vězňů může být vyslechnut i vícekrát – pokud by výslechy probíhaly po nekonečně mnoho dní, tak by byl každý z vězňů vyslechnut nekonečně mnohokrát. Od určitého okamžiku tedy určitě nastane stav, že každý z vězňů byl vyslechnut alespoň jednou. Pokud pak kdykoliv potom kterýkoliv z vězňů během výslechu řekne: „nyní jsme byli všichni vyslechnuti alespoň jednou“, tak budou všichni vězni propuštěni. Pokud někdo tuto větu řekne dříve než je to pravda, tak budou všichni vězni popraveni. Před začátkem výslechů se vězni mohou půl hodiny společně procházet po vězeňském dvoře a domluvit si strategii, jak rozsvěcet a zhasínat žárovku a kdy má někdo pronést propouštěcí formuli. Vaším úkolem je pro vězně tuto strategii vymyslet. K výslechům mohou vězně vodit zcela libovolně, jediným pravidlem, které vyšetřovatelé musí dodržet je, že v libovolném okamžiku musí platit:
" Každý vězeň bude ještě v budoucnu vyslechnut, pokud celý proces neskončí popravou či propuštěním vězňů"
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).
pokuste se najít nějaké další poznatky o vážení koulí
Stejná úloha, Kromě podezřelých koulí máme k dispozici i libolný počet zaručeně správných koulí
(o této úloze se dají odvodit zajímavější trvrzení, která vnesou více světla i do úlohy původní).
cvičení 6.října
řešení úlohy cesty na šachovnici
řešení úlohy páska sudé délky
řešení úlohy vězňové
diskuse úlohy 2 o elektrikáři - zůstává na rozmyšlenou
diskuse úlohy 5 o princezně
klíčem k řešení je uvědomit si, že princ má v každém tahu na výběr jen ze dvou možností:
může šáhnout buď na diagonálu nebo stranu stolku zůstává na rozmyšlenou
Pojem vyhrané a prohrané pozice, jaké vlastnosti mají množiny vyhraných a prohraných pozic.
- Rozmyslete si důkladně!
Dva kameny
Dva hráči hrají následující deskovou hru. Hracím plánem je jedna řada tvořená 1000 políčky, pole jsou očíslována zleva doprava přirozenými čísly od 1 do 1000. Na začátku hry na náhodně zvolených dvou různých polích leží hrací kameny. Výchozí situaci hry lze tedy popsat dvojicí různých celých čísel od 1 do 1000. Oba hráči se ve hře pravidelně střídají. Hráč, který je na tahu, zvolí jeden z kamenů a přemístí ho o libovolný počet polí směrem doleva. Musí přitom kámen posunout alespoň o jedno políčko a zároveň svým tahem nesmí přeskočit jiný hrací kámen ani nesmí umístit přesouvaný kámen na již obsazené políčko. (Tah tedy nelze provést s kamenem stojícím na políčku číslo 1 ani s kamenem stojícím na políčku i, je-li políčko číslo i-1 právě obsazené.) Hra končí ve chvíli, kdy už nelze provést žádný tah, tzn. až se dostanou oba hrací kameny na políčka s čísly 1 a 2. Zvítězil ten z hráčů, který svým tahem dosáhl této koncové situace. Určete, jaké pozice jsou vyhrané a jaké prohrané. Úlohu jsme vyřešili.
Čtyři kameny
Stejná úloha jako byla úloha se dvěmi kameny, ale se čtyřmi hracími kameny. Výchozí situace hry je tedy popsána čtveřicí
různých celých čísel od 1 do 1000 (čísla políček, na nichž leží kameny). Hra končí ve chvíli, kdy se hrací kameny dostanou na pole s čísly 1, 2, 3 a 4. Úkolem je opět určit, pro které výchozí situace hry si může zajistit výhru začínající hráč, a nalézt vítěznou strategii hry.
Na rozmyšlenou:
Na stůl tvaru odélníka pokládají dva hráči střídavě mince (všechny jsou stejné). Mince musí ležet celá na stole, nesmí ležet na druhé. Prohraje ten, který už další minci nemůže položit. Je hra pro začínajícího hráče vyhraná nebo prohraná?
Tahání koulí z urny.
V urně je na začátku B bílých a C černých koulí. Hra probíhá tak, že vždy vytáhneme z urny dvě koule a vrátíme
tam jednu podle těchto pravidel:
vytáhneme-li dvě černé, vrátíme bílou,
vytáhneme-li dvě bílé, vrátíme bílou,
vytáhneme-li dvě koule různé barvy, vrátíme černou.
Abychom hru mohli hrát, musíme tedy mít k dispozici i dostatečně mnoho bílých koulí mimo urnu. V každém kroku se zmenší počet koulí
v urně o jednu. Nakonec tam tedy zbyde jen jedna. Ten, kdo hru hraje, do urny nevidí a neví, kolik jakých koulí v ní je. Dovedli byste předpovědět, koule jaké barvy v urně zbyde jen na základě počtů bílých a černých koulí na začátku?
Kulový blesk
Jistých N rodin bydlí v bytech, které označíme celými čísly od 1 do N. Rodiny se dohodly provést cyklickou N-směnu bytů
(viz též film Kulový blesk). Rodina z bytu číslo 1 chce do bytu číslo 2, rodina z bytu číslo 2 do bytu číslo 3, atd.,
až rodina z bytu číslo N se bude stěhovat do bytu číslo 1. Výsledné záměny bytů je třeba dosáhnout postupným prováděním dvojsměn.
Některé rodiny se tudíž budou během celé akce stěhovat vícekrát. Každá rodina se ale může přestěhovat nejvýše jednou za den.
V jednom dni může samozřejmě probíhat souběžně více dvojsměn bytů. Určete, jaký nejmenší počet dní postačí pro dané N
k uskutečnění celé zamýšlené akce. Sestavte rozpis, podle něhož je třeba při výměnách bytů postupovat,
aby se tohoto minimální počtu dní dosáhlo (tzn. rozpis určující, kdo se který den stěhuje kam).
Věž z cihel
Máme k dispozici neomezenou zásobu cihel, všechny cihly jsou stejné. Na stůl budeme pokládat cihly na sebe jednu na druhou.
Každá cihla musí ležet na cihle předchozí, může ji ovšem částečně přesahovat do strany. Není však povoleno umístit více cihel
do stejné výšky nad deskou stolu. Zjistěte, jak nejdále od hrany stolu se se svou stavbou z cihel dokážete dostat.
Zkuste najít jakékoli nové tvrzení o úloze s koulemi
hra se třemi kameny
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ů.
elektrikář - písemný domácí úkol napište algoritmus
úloha o tahání koulí z urny - 1. úloha z minula
pojem invariantu
pokládání mincí na stůl
kulový blesk zůstává na rozmyšlenou
věž z cihel
velbloud - zkuste obecně
Vážení koulí
jde na 3 z 12 podezřelými koulemi bez správné
odhad pro kolik nejvýše koulí můžeme rozhodnout za k vážení
Úlohy na rozmyšlenou:
Všechny úlohy, co jsme nedodělali
Zkuste najít jakékoli nové tvrzení o úloze s koulemi
Zkuste úlohu řešit úlohu o vážení obecně:
pro kolik koulí dovedete úlohu vyřešit máte-li možnost vážit k krát
kolik potřebujete vážení pro vyřešení úlohy s N podezřelými koulemi
Položte si otázku, jak se tyto výsledky změní když nemáte k dispozici správné koule resp.
jich máme jen omezený počet.
cvičení 20.října
Komentář k domácímu úkolu
Připomenutí, že se máte zaregistrovat do Codexu a zřídit si účet v laboratoři v Karlíně
12 koulí bez správné na 3 vážení, 13 koulí na 3 vážení, máme-li jednu správnou
Návod na obecné řešení úlohy o vážení
Obecné řešení úlohy o velbloudovi
Na rozmyšlenou:
Najděte vyhrávající a prohrávající pozice ve hře NIM:
Na začátku je na hromádce N sirek, hráči se střídají v odebírání sirek.
V jednom tahu může hřáč odebrat jednu, dvě nebo tři sirky. Prohrává ten, který vezme poslední sirku.
Na zahradě je N záhonů, na každý z nich je možno vysít buď mrkev nebo petržel.
Nikdy však nesmí být dva záhony petržele na sousedních záhonech. Najděte efektivní způsob jak spočítat
pro N počet možností, jak lze N záhonů osít - předpokládejte, že N může být hodně velké
a tedy probrání všech možností není únosné.
Pokud jste někdy programovali, zkuste top naprogramovat v jazyce, který znáte (stačí napsat kód, není nutné spouštět.
Ti, kdo neprogramovali zkusí počítat výsledek pro N=10.
Provázky
Mám naolejovaný provázek. Když ho na jednom konci zapálím, bude postupně odhořívat, až za 1 hodinu dohoří na druhý konec (a zhasne). Provázek však není všude stejně široký, a proto ani nehoří stále stejně rychle. Nelze tedy tvrdit, že např. polovina provázku
shoří za půl hodiny. Lze splnit následující úkoly ?
mám jeden provázek a potřebuji změřit půl hodiny
mám dva provázky a potřebuji změřit čtvrt hodiny
Pozn: okamžik, od kdy začínám měření, si mohu zvolit sám
Zkuste vyřešit a odevzdat úlohu Součet dvou čísel v Codexu, abyste alespoń věděli v čem byl problém,
pokud to nepůjde, nevadí, vše si ukážeme
cvičení 27.října
(Zjednodušený) přehled příkazů vstupu a výstupu - read, readln, write, writeln, formátovaný výstup, čtení čísel
Program prohledání největšího čísla, druhého největšího čísla
Zjednodušený tvar for cyklu
Program pro hledání trojic celočíselných délek stran pravoúhlých trojúhelníků menších než zadané číslo rozmyslet: optimalizace kódu, aby nedocházelo ke zbytečně se opakujícím výpočtům uvnitř cyklů
Předvedení prostředí Borland Pascalu,
nastavení pracovního adresáře (Change Dir), práce s editorem, přepínámí velikosti písma, help, kontextový help (Ctrl+F1), překlad a spouštění programu, napsání jednoduchého programu, běhové a syntaktické chyby
Předvedení systému CodEx
Domácí úkol:
Pohrajte si s překladačem Borland Pascalu, abyste uměli formulovat případné dotazy na jeho práci
Zkuste odevzdat několik příkladů v CodExu
Na rozmyšlenou zůstávají všechny úlohy, které jsme nevyřešili
cvičení 3.listopadu
bylo suplováno kvůli mé nemoci
petržel a mrkev
analýza kódu
frekvence minima a maxima
délka nejdelší konstatní posloupnosti
nové úlohy v CodExu
cvičení 10.listopadu
komentář k odevzdaným úlohám v CodExu
výpočet částečného součtu jednoduché mocninné řady
většinou je vhodný inkrementální výpočet, který počítá (i+1)-ní člen z i-tého
reprezentace permutace jako dvojice proměnných pole a číslo udávající délku použité části
budeme později umět udělat v Pascalu lépe
Algoritmus nalezení následující permutace v lexikografickém uspořádání
do 17.11. bude v CodExu úloha na jeho implementaci
Pořadí permutací
Zjistit kolikátá je zadaná permutace, algoritmus jsme probrali,
řešení pošlete do Codexu - úloha bude do 17.11.
Rozmyslete si a napište proceduru, která zjistí permutaci (čísel 1..N), která je v lexikografickém uspořádání na K-tém místě
vrátíme se k tomu na příštím cvičení
Nové úlohy v CodExu vypracujte do 23.11. termíny prodlužovat nebudu
reprezentace matice jako dvojice - pole a velikost "použité části"
později budeme umět lépe
Algoritmus Gaussovy eliminace, pivotizace
napsali jsme podstanou část procedury, doprogramujte ji resp. napište si novou
cvičení 24.listopadu
komentář k odevzdávání úloh v Codexu,
prodloužil jsem termíny k odevzdávání
opakování předávání parametrů
opakování záznamů
funkce, která hledá pozici prvního výskytu jedné posloupnosti v druhé
algoritmus kontroly správného uzávorkování,
pomocí čítače otevřených závorek a pomocí zásobníku
Algoritmus správnosti uzávorkování s více typy závorek
pomocí zásobníku (pomocí více čítačů je špatně)
jednoduchá písemka
snažte se "srovnat krok", případně nabízím individuální konzultace
Staré i nové úlohy v CodExu
cvičení 1.prosince
komentář k písemce
komentář ke Codexu
Všichni, kdo jsou pozadu si do příště přečtou Satrapovu knížku o Pascalu
(mohou vynechat to, co dosud na přednášce nebylo), aby srovnali krok a mohli mít dotazy
Práce se soubory
Jednoduché příklady na práci se soubory
cvičení 8.prosince
úloha o frontě před kinem
generování všech kombinací k-té třídy z n prvků
generování všech variací generování všech variací k-té třídy z n prvkůc
rozmyslet: generování všech kombinací generování všech kombinací s opakováním k-té třídy z n prvků
Přineste písemně na příští cvičení řešení Yosarianovy úlohy:
Program, který přečte ze vstupu celé číslo K (menší než 10) a po té okopíruje na výstup vstupní soubor,
v němž bude zahvězdičkováno každé slovo, pro které platí, že "některé z K následujících slov končí na 'ova' ".
Vyřešte nové úlohy v CodExu !!! - je tam i variace na zarovnávání do bloku
rozmyslete si látku z přednášky o rekurzi
Domluvili jsme hromadnou konzultaci v úterý 15.prosince v 15:40 (podle rozvrhu má být volná posluchárna K12, sejdeme se tedy tam)