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

Termín odeslání Vašich řešení této série jest určen na polovinu února 1999. Řešení můžete odevzdávat jak elektronicky, tak klasickou poštou na známou adresu.

Dotazy ohledně zadání můžete posílat na adresu ksp@mff.cuni.cz, nebo se ptát přímo na diskusním fóru 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):

  • INC x – zvýšení obsahu paměťové buňky číslo x o 1.
  • DEC x – snížení obsahu paměťové buňky číslo x o 1. Pokud tato již byla nulová, nezmění se.
  • CLR x – uložení nuly do dané paměťové buňky.
  • JEQ x,y,z – pokud je v paměťových buňkách x a y uloženo totéž číslo, skočí o z instrukcí dopředu (z je libovolné celé číslo), v opačném případě neprovede nic.

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í