Třetí série jedenáctého ročníku KSP

Zadání úloh

11-3-1 Telefouňové (10 bodů)

Nejmenovaná telefonní společnost vydala reklamní leták, v němž se chlubí tím, která všechna města telefonizovala. Pro každé z uvedených měst uvádí počet telefonních vedení vedoucích do jiných měst ze seznamu, přičemž mezi každými dvěma městy může vést pouze jedno vedení a je obousměrné. Jak už to u reklamních letáků, zejména pak pocházejí-li od nejmenovaných telefonních společností, bývá, vy jim nevěříte, a proto jste se rozhodli, že vytvoříte program, jenž si seznam přečte a rozhodne, zda existuje telefonní síť daných vlastností a pokud ano, tak nějakou takovou nalezne (nalezením telefonní sítě se myslí vypsání počátečního a koncového města každého vedení).

Příklad 1: Zadání: Praha 3, Brno 2, Horní Kotěhůrky 1, Oulehlice 2. Jeden z možných výsledků: Praha – H. K., Praha – Brno, Brno – Oulehlice, Praha – Oulehlice.

Příklad 2: Zadání: Praha 3, Metelice 1. Výsledek: podvod.

Předpokládejte, že města jsou očíslována od 1 do n a že vstupem je posloupnost n čísel, přičemž i-té číslo udává počet vedení pro i-té město.

Řešení

11-3-2 Ffffaktoriál (9 bodů)

Je všeobecně známo, že n! (faktoriál čísla n, definován jako n!=1 ·2 ·3 ·4 ·… ·n) bývá ohromné číslo končící na mnoho nul. O to překvapivější je ovšem fakt, že je možné snadno zjistit, kolik je poslední nenulová číslice v desítkovém zápisu n!. Napište program, který tuto číslici pro dané n spočte.

Příklad: 6! = 720, poslední nenulová číslice je 2.

Řešení

11-3-3 Obdélníčky (11 bodů)

Jeník Příhoda, syn známého Strýčka Příhody, hrál neobvyklou hru: Měl obdélníkový stůl velikosti a×b a n papírových obdélníčků velikostí ai ×bi a chtěl obdélníčky po stole rozložit tak, aby jejich hrany byly rovnoběžné s hranami stolu a celková plocha zakrytá obdélníčky byla co největší. Obdélníčky se mohly i překrývat, ale nesměly přečnívat přes okraj stolu.

Po krátkém hraní této obtížné hry Jeníka napadlo, že by si mohl napsat program, který pro dané polohy a velikosti obdélníčků spočte, jaká je celková plocha jejich sjednocení. Zkuste to i vy.

Řešení

11-3-4 Machina Universalis (12 bodů)

V tomto pokračování našeho seriálu o tajích teoretické informatiky zkusíme dokázat, že existuje tzv. universální program, to jest program, kterému dodáte na vstupu nějaký program P a vstup pro tento program a on vám odpoví výstupem programu P a nebo nikdy neskončí, pokud program P nikdy neskončí.

Bylo by ovšem velice pracné psát takový program přímo pro Pascal resp. Céčko, a tak si nejdříve nadefinujeme velice jednoduchý assembler a dokážeme, že se v něm dá naprogramovat totéž, co v Pascalu a Céčku.

Mikroassembler μ1 počítá v paměti, která je indexována přirozenými čísly a každá její buňka obsahuje opět nějaké přirozené číslo. K dispozici jsou čtyři instrukce (instrukce INC je "přebytečná" a dala by se nahradit, ale je to zbytečná komplikace; blíže viz úloha 9-3-3):

Program začíná běh svojí první instrukcí a mimo pevně zvolené paměťové buňky obsahující vstup je obsah zbytku paměti nedefinován. Končí pak při pokusu o skok před svou první instrukci, přičemž v pevně zvolených (možno jiných než vstupních) paměťových buňkách je uložen výsledek výpočtu. Na ukázku uveďme program, který sečte čísla na adresách 1 a 2, načež výsledek uloží na adresu 0.

         CLR    3
         CLR    0
         JEQ    1,3,4
         DEC    1
         INC    0
         JEQ    3,3,-3
         JEQ    2,3,-7
         DEC    2
         INC    0
         JEQ    3,3,-3

A nyní slíbený důkaz ekvivalence μ1 a Pascalu (pro Céčko analogicky). Kroky označené [*] uvádíme jen v náznacích, vaším úkolem je popsat je přesně. V průběhu našeho důkazu budeme postupně omezovat, jaké jazykové konstrukce používáme, a to tak, že na konci zbudou přesně obraty odpovídající našemu miniassembleru. Za to pochopitelně zaplatíme prudkým nárůstem velikosti programu a drastickým zpomalením, ale to je jedno, protože naším cílem je pouze dokázat, že se v obojím dá spočítat totéž.

  1. Pro naše úvahy se omezíme na Pascal, v němž typ word pojme libovolné přirozené číslo bez omezení rozsahu. To nám důkaz značně zjednoduší, nicméně sílu jazyka taková úprava nikterak nemění, protože můžeme implementovat dynamicky alokovanou aritmetiku počítající s libovolně dlouhými čísly.
  2. [*] Každý pascalský datový typ je možno reprezentovat jedním wordem (to platí nejen pro základní typy, ale i pro typy strukturované, jako je třeba pole [indexované čímkoliv, tedy vlastně wordem a obsahující libovolné prvky, tedy vlastně wordy, čímž se řeší i případ recordů]). Tím jsme si tedy převedli program na jiný program, který počítá pouze s wordy.
  3. Speciálně také vstup a výstup programu je možno prohlásit za word.
  4. V programu je možno eliminovat volání procedur za cenu zavedení vlastního zásobníku, v němž budou uloženy lokální proměnné procedur a návratové adresy (vše pochopitelně wordy) a objevení se velkého množství skoků.
  5. Všechny výrazy můžeme zavedením vhodných pomocných proměnných rozložit na elementární přiřazení typu x := y @ z, (@ je operátor).
  6. [*] Všechny cykly je možné rozložit na podmíněné skoky, tedy konstrukce typu if x then goto y, kde x je proměnná (výrazů jsme se přeci v předchozím kroku zbavili) a y návěští.
  7. Násobení, dělení, bitové operace a jiné vymoženosti můžeme nahradit pouhým sčítáním, odčítáním, testem na rovnost a nerovnost typu "je menší než". (To je jednoduché, ale poměrně pracné, jelikož je nutno uvažovat každou operaci zvlášť.)
  8. Zbylým proměnným přiřadíme pevná místa v paměti μ1.
  9. [*] Sčítání, odčítání a skoky podmíněné rovností a nerovností je možno převést na instrukce μ1.

Již tedy víme, že libovolný program v Pascalu můžeme přeložit na ekvivalentní program v μ1 (náš důkaz dokonce dává algoritmus, jak to provést). Nyní zkuste na základě tohoto tvrzení sami dokázat, že existuje universální program v našem miniassembleru (pomněte, že programy a jejich vstupy i výstupy je také možné reprezentovat přirozenými čísly), jakož i universální program v Pascalu.

Řešení

11-3-5 Pascal či Céčko? (10 bodů)

A na závěr letošní Vánoční prémiová úloha. Napište program, který jde zkompilovat jak kompilátorem Pascalu, tak kompilátorem Céčka a po spuštění vypíše, čím byl vlastně zkompilován. Další rozpoznávané jazyky budou hodnoceny prémiovými body!

Řešení