Třetí série jedenáctého ročníku KSP
- Termín série: polovinu února 1999
- Odevzdávání: elektronicky přes Odevzdávátko
- Jak řešit: viz Návod na teoretické úlohy a Návod na praktické úlohy
- Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.
Zadání úloh
- 11-3-1: Telefouňové
- 11-3-2: Ffffaktoriál
- 11-3-3: Obdélníčky
- 11-3-4: Machina Universalis
- 11-3-5: Pascal či Céčko?
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.
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.
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.
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éž.
- 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.
- [*] 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.
- Speciálně také vstup a výstup programu je možno prohlásit za word.
- 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ů.
- 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). - [*] Všechny cykly je možné rozložit na podmíněné skoky, tedy konstrukce
typu
if x then goto y
, kdex
je proměnná (výrazů jsme se přeci v předchozím kroku zbavili) ay
návěští. - 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ášť.)
- Zbylým proměnným přiřadíme pevná místa v paměti μ1.
- [*] 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.
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!