Cvičení z PRM44 Programování I
ZS 2006/7 skupina Y/56
úterý 10:40 K3

1. cvičení 3.října
2. cvičení 10.října
3. cvičení 17.října
4. cvičení 24.října
5. cvičení 31.října
6. cvičení 7.listopadu
7. cvičení 14.listopadu
8. cvičení 21.listopadu
9. cvičení 28.listopadu
10. cvičení 5.prosince
11. cvičení 12.prosince
12. cvičení 19.prosince

1. cvičení 3.října
   • seznámení se studenty
   • různé způsoby nalezení největšího z N prvků, nejde to na méně než N-1 porovnání
   • hledání druhého největšího: tenisový turnaj, druhý může být jen ten, kdo prohrál s vítězem
     zkusit dokázat, že lépe to nejde (je to těžké)
   • hledání cesty (příp. uzavřené cesty) věže po šachovnici, která přejde přes jkaždé pole právě jednou
     • na úplné šachovnici
     • na šachovnici bez jednoho rohového políčka
     • na šachovnici bez dvou protilehlých rohových políček
   • Vážení kuliček pomocí rovnoramenných vah
     nejvýše jedna jiná - máme zjistit, zda tam je a pokud ano jaká je (těžší nebo lehčí)
     • ze 3 na 2 vážení
     • z 12 na tři vážení - je třeba dodělat
   • Úlohy na rozmyšlenou:
     1. třetí z pěti na co nejmenší počet porovnání
     2. velbloud a banány
     3. kulový blesk
     4. identifakce žil kabelu
     5. lámání čokolády
2. cvičení 10.října
   • čokoláda
   • třetí největší z pěti
   • velbloud a banány - najděte obecné řešení
   • kulový blesk
   • identifikace žil kabelu s 27 žilami - najděte obecné řešení
   • hra s dvěma kameny
   • hledání stabilního párování - podrobně bude na přednášce
   • Úlohy na rozmyšlenou
     1. hledání cesty věže po šachovnici s jedním odříznutým rohovým políčkem, která přejde přes každé pole právě jednou
     2. synchronizace automatů
     3. vězni a žárovka
     4. princezna a otočný stolek
     5. hry se třemi a čtyřmi kameny
     6. Páska sudé délky s prémiemi
     7. další fakta o vážení kuliček
3. cvičení 17.října
   • princezna a otočný stolek
   • Páska sudé délky s prémiemi
   • velbloud a banány - obecné řešení
     rozmyslete, zda je skutečně optimální
   • hledání "jiné" koule s jednou správnou navíc
     ze 4 na 2 vážení, z 13 na 3 vážení
   • důkaz, že úlohu na k vážení jde vyřešit nejvýše pro ( 3^^K - 1 ) / 2 ) koulí
   • rozmyslet další fakta o vážení,resp nají "obecný" algoritmus
   • Úlohy na rozmyšlenou
     • zůstávají:
       1. hledání cesty věže po šachovnici s jedním odříznutým rohovým políčkem, která přejde přes každé pole právě jednou
       2. identifikace žil kabelu s N žilami - obecné řešení
       3. synchronizace automatů
       4. vězni a žárovka
       5. hry se třemi a čtyřmi kameny
       6. další fakta o vážení kuliček
     • nové:
       1. rodina jde tunelem s baterkou
       2. měření času hoření, provázku
       3. věž z cihel
       4. mrkev a petržel
       5. Hádání čísel
          Myslím si dvě čísla mezi 2 a 99. Adamovi řeknu jejich součin, Bohoušovi jejich součet.
          Adam: Já nevím, jaká sis myslel čísla.
          Bohouš: Já věděl, že to nebudeš vědět.
          Adam: Tak teď už vím, co je to za čísla.
          Bohouš: Tak já už taky
          Co jsem si myslel za čísla ?
4. cvičení 24.října
   • rodina jde tunelem s baterkou
   • vězni a žárovka
   • mrkev a petržel
     řešení pomocí dynamického programování
   • měření času hoření, provázku
   • pokus o věž z cihel
   • návod pro synchronizaci automatů
   • výpočet n-té mocniny na co nejméně násobení
     rozmyslet, že jde v konstatní paměti
   • Písemný domácí úkol:
     Přineste na příští cvičení nebo
     pošlete emailem na moji adresu tak, aby došlo nejpozději v pondělí do 8 hodin ráno
     s předmětem PRM044 Dcv 1
     1. velbloud a banány - obecné řešení případně i "důkaz", že je optimální
     2. hry se třemi a čtyřmi kameny
   • Úlohy na rozmyšlenou
     1. hledání cesty věže po šachovnici s jedním odříznutým rohovým políčkem, která přejde přes každé pole právě jednou
     2. synchronizace automatů
     3. identifikace žil kabelu s N žilami - obecné řešení
     4. hry se třemi a čtyřmi kameny
     5. další fakta o vážení kuliček
     6. věž z cihel
5. cvičení 31.října
   • synchronizace automatů
   • vážení kuliček:
     • důkaz, že úlohu na k vážení nejde vyřešit pro ( 3^^K - 1 ) / 2 ) koulí bez správné koule
     • důkaz, že jde-li úlohu na k vážení jde vyřešit pro ( 3^^K - 1 ) / 2 ) koulí,
       pak k tomu není potřeba více než jedna správná koule
     • důkaz, že jde-li úlohu na k vážení jde vyřešit pro ( 3^^K - 1 ) / 2 ) koulí,
       pak bez správné koule to jde s o jednu méně koulemi
   • Na vstupu je posloupnost nezáporných celých čísel ukončená číslem -1 rozdělená čísly nula na úseky kladných čísel,
     pro jednoduchost můžeme předpokládat, že závěrečnou -1 bezprostředně předchází nula
     vstupní posloupnost smíte číst jen jednou
     1. najděte třetí největší číslo z druhého nejdelšího úseku
        na cvičení - jaké proměnné potřebujeme
        domácí úkol zkuste napsat program, který úlohu řeší
        (pokud to je pro Vás těžké, zkuste napsat program řešící náhradní úlohu
        pokud to z dřívějška umíte zkuste napsat v překladači Borland Pascalu)
     2. další modifikace úlohy
     3. zkuste vyřešit úlohu, kdy požadujeme výstup všech čísel nejdelšího úseku, pokud můžete vstupní posloupnost přčíst dvakrát
   • Náhradní úloha pro domácí cvičení:
     Sestavte program, který zjistí ze vstupní posloupnosti kladných čísel ukončené nulou největší a nejmenší číslo
   • Úlohy na rozmyšlenou:
     • hledání cesty věže po šachovnici s jedním odříznutým rohovým políčkem, která přejde přes každé pole právě jednou
     • důkaz, že úlohu na k vážení jde vyřešit pro ( 3^^K - 1 ) / 2 ) koulí
       (již víme, že z více koulí to nejde a, že pokud to jde, potřebujeme k tomu jednu správnou kouli)
6. cvičení 7.listopadu
   • Vyhrané a prohrané pozice ve hrách se třemi a čtyřmi kameny
   • Jednoduché programy pro vyhledávání prvků v poli
     • Domácí úloha:
       1. pro zkušenější: funkce (již bylo na přednášce), která najde prostřední výskyt čísla v poli
          metodou hledání výskytů střídavě zepředu a ze zadu
       2. Najděte v matici řádek, ve kterém se vyskytuje maximální číslo (je-li takových řádek víc, uvažujte první z nich), a zaměňte ho s prvním řádkem matice.
     Přineste na příští cvičení nebo
     pošlete emailem na moji adresu tak, aby došlo nejpozději v pondělí do 8 hodin ráno
     s předmětem PRM044 Dcv 3 v textu programu umístěte na začátek komentář s Vašim jménem
7. cvičení 14.listopadu
   • Podprogram kopírující matici se současnou výměnou prvků umístěných symetricky podle halvní diagonály
   • Podprogram, který vymění prvky matice umístěné symetricky podle hlavní diagonály
   • Podprogram, který najde N největších čísel z matice N x N
     řešení se složitostí N³ - rozmyslet rychlejší řešení
   • Domácí úloha: Napište poprogram, který převede čvtercovou matici pomocí "gaussovských operací" na ekvivalentní horní trojúhelníkovou
   • všichni se pokusí zformulovat obecný algoritmus pro vážení kuliček
8. cvičení 21.listopadu
   • Nalezení N největších čísel z matice N x N se složitost N²
   • Rekapitulace toho, co už víme vážení - dokončení zůstává
   • instruktivní naprogramování výpočtu hodnot částečných součtů složité mocninné řady
   • Domácí úloha:
     uvažujte deklarace
     const
Max = 10;
type
index = 1..Max;
malecislo = 0 .. 999;
pole = array [index,index] of malecislo;
matice = record
A : pole;
D : index; {rozmer matice}
end;


     Napište podprogram, který dostane jako parametry
     M - matici, F počet znaků, do kterých má vystoupit číslo, a S jméno výstupního souboru. Podprogram nechá matici vystoupit do výstupního souboru formátovaně, ale tak, že případná nulová čísla budou ve výstupu reprezentována jako F znaků mezera.
     Pokud to již umíte, umístěte podprogram do ladícího programu, abyste ji mohli otestovat. Pokud ne, napište proceduru jen "na sucho" v textovém editoru.

   Úkol pošlete do pondělí rána (9:00) mailem na adresu KRYL@KSVI.MFF.CUNI.CZ se subjektem DcvM1. Text programu umístěte do přílohy (v textovém tvaru), v komentáři na začátku textu programu i v textu mailu uveďte svoje jméno a příjmení.


9. cvičení 28.listopadu
   • Algoritmus a program, který kontroluje správnost uzávorkování výrazu
     • s jedním možným typem závorek
     • s více typy závorek
   • Domácí úkol :Sestavte proceduru, která k zadanému číslu typu integer vytiskne všechny jeho různé celočíselné dělitele.
     úkol pošlete mailem, pokud možno si vytvořte i program, který by vytvořenou proceduru otestoval a pošlete mi ho i se souborem se vstupními daty


10. cvičení 5.prosince
    • úlohy na práci s řetězci:
      1. hledání počtu výskytů zadaného znaku v textovém souboru
      2. hledání počtu výskytů zadaného řetězce v textovém souboru
      3. hledání počtu výskytů zadaného řetězce (přičemž nerozlišujeme mezi velkými a malými písmeny) v textovém souboru
      4. hledání počtu výskytů daného slova (od mezery do mezery) v textovém souboru
      5. Vytvořte program, který vytiskne frekvenční tabulku obsahující N nejčastěji se vyskytujících slov v zadaném vstupním souboru uspořádanou podle počtu jejich výskytů. Slovem rozumíme libovolnou posloupnost písmen anglické abecedy, slova jsou oddělena mezerami resp. konci řádků. Můžete předpokládat, že N je menší než 100 a že ve vstupním souboru je nejvýše 1000 různých slov
      6. cenzura ala Yossarian: Na vstupu je textový soubor obsahující slova napsaná malými písmeny anglické abecedy. Vytvořte na základě vstupujícího čísla N (N <= 13) nový textový soubor, který bude mít zachovánu úpravu (počet mezer mezi slovy, konce řádků) původního, ale budou v něm slova, pro která platí následující tvrzení „některé z následujících N slov končí trojicí písmen ’ova ’ “ vytištěna jako posloupnost hvězdiček.
    • Domácí úkol:
      Úloha číslo 5, pokud si na ni netroufáte, udělejte některou z předchozích. Odlaďte na počítači a zašlete poštou.


11. cvičení 12.prosince
    • zarovnávání textu "do bloku"
    • N je malá konstanta, např. N=5, je zadána posloupnost {a_i}_i=1..N (malých) kladných čísel typu integer.
      Rozhodněte, zda jde vložením vhodných znamének mezi každá dvě z čísel posloupnosti ai získat výraz, jehož hodnota je rovna X
      (stačí nalézt jedno takové řešení). Uvažujte znamenka *, +, -, / (ve významu div). Při vyhodnocování zanedbávejte priority znamének a vyhodnocujte zleva doprava.
    • Uvažujte předchzí problém s přidaným znaménkem . (znamená zřetězení)
    • Domácí úkol:
      Vstupem programu je textový soubor Inp. Slovem nazveme takový úsek textu, který je z obou stran oddělen jednou či více mezerami nebo konci řádků. Napište program, který přečte z klávesnice číslo udávající délku řádky vystupního souboru Out. Do výstupního souboru vytiskneme vstupní text se zarovnanými okraji na levé i pravé straně (jako v knize). Dosáhnete toho tím, že mezi slova vložíte vhodný počet mezer (rovnoměrně rozdělený) a změníte rozdělení slov textu do řádků.
    Program odlaďte a zdrojový kód pošlete poštou, dodržujte jména souborů v programu
12. cvičení 19.prosince
    • povídání o zápočtech
    • hledání nejkratší cesty figury po šachovnici se zakázanými poli
    • Domácí úkol:
      Sestavte program, který ze vstupního souboru přečte šachvnici (se zakázanými poli) potom v cyklu čte z klávesnice startovní a cílové políčko a najde nejkratší cestu věže ze startu do cíle. Uvědomte si, že cesta nemusí vždy existovat. Rozmyslete, jak zobrazit nejkratší cestu na šachvnici
    • Na rozmyšlenou (z konzultace)
      Vytvořte podprogram, který k zadané permutaci najde permutaci, která bezprostředně po ní následuje v lexikografickém uspořádání.