Kód krychle | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
x | + | - | - | + | + | - | - | + |
y | + | + | - | - | + | + | - | - |
z | + | + | + | + | - | - | - | - |
Tímto způsobem lze postupně dělit typizované krychle bez omezení.
Je dána množina typizovaných krychlí K. Průměty typizované krychle do souřadných rovin xy, yz a xz (typizované čtverce) jsou kódovány pouze kódy dané souřadné roviny, tzn. tak, jako by zbývající souřadnice byla vždy kladná (například průměty typizovaných krychlí do roviny xy jsou kódovány posloupnostmi číslic 1, 2, 3, 4, analogicky u ostatních rovin).
Nechť M a Mmin jsou 2 množiny typizovaných čtverců takové, že M je průmět množiny typizovaných krychlí K do jisté souřadné roviny. Mmin je minimální k M, jestliže platí současně
Vaší úlohou je pro množinu K typizovaných krychlí zadanou jejich kódy určit minimální průměty do všech tří souřadných rovin.
P-III-2
Mějme bílý list ve tvaru obdélníka o šířce a cm a délce b cm (a<b) z nekonečně tenké
a absolutně pružné látky. Zavedeme souřadný systém tak, že má počátek v levém dolním
rohu papíru a osy jsou rovnoběžné s okraji listu. Tento obdélník je zdeformován
tak, že protilehlé delší okraje tohoto listu jsou slepeny a vznikne válec. Ten je dále
ohnut tak, že slepíme podstavy tohoto válce (překryv nutný ke slepení zanedbejte).
Vznikne prostorové těleso, připomínající pneumatiku (V matematice se takové
těleso nazývá toroid). Umístění souřadných os vůči původnímu listu přitom zůstane
zachováno. Na toto těleso je postupně pokládáno N obdélníků z nekonečně tenké a
pružné látky různých barev, jejich strany jsou rovnoběžné se souřadnými osami.
Po položení všech obdélníků jsou vidět obrazce různých barev. Dvě oblasti stejné barvy
považujeme za části téhož obrazce, mají-li společný alespoň jeden bod
(tj. stačí dotyk rohem). Vaší úlohou je určit plochu každého z těchto obrazců.
Zadání je uvedeno v následujícím tvaru:
P-III-3
T-stroj je tvořen řídící jednotkou, která se může nacházet v konečně mnoha
stavech, a nekonečně dlouhou páskou, rozdělenou na jednotlivá pole. V každém
poli může být zapsán 1 symbol nějaké konečné abecedy, nebo může být prázdné,
tj. obsahovat speciální symbol @
. Hlava T-stroje je umístěna vždy nad určitým
polem pásky a může se pohybovat vlevo nebo vpravo právě o 1 pole.
Výpočet T-stroje probíhá v taktech. Na začátku výpočtu je T-stroj v
počátečním stavu, na pásce je zapsána posloupnost znaků z dané abecedy
(vstupní slovo) a je stanovena poloha hlavy nad páskou. V každém
taktu výpočtu T-stroj přečte znak z pole pásky, nad nímž je umístěna
hlava, a na základě tohoto znaku a stavu řídicí jednotky (konfigurace
T-stroje) se zapíše nějaký znak dané abecedy do stejného pole, změní se
stav řídící jednotky a hlava se může posunout o 1 pole doleva nebo doprava,
případně zůstat na stejném poli. Zapsaný znak nemusí být součástí vstupní
abecedy - je možné používat pomocné symboly. Činnost T-stroje končí v
okamžiku, kdy vykoná instrukci STOP
nebo když není definováno, jak má
jeho činnost pokračovat pro příslušnou konfiguraci (znak+stav stroje).
Pokud se T-stroj zastaví, říkáme, že přepsal vstupní slovo na
výstupní slovo.
T-stroj může rozhodovat problémy, na které jsou možné odpovědi ano/ne. Pokud se stroj při zastavení nachází v určitém pevně stanoveném stavu, je odpověď ano, jinak ne.
Činnost T-stroje lze popsat řídícími strukturami podobnými Pascalu, jmenovitě lze použít podmíněné příkazy a cykly typu repeat a while. Návěští před příkazem značí stav T-stroje. Stav S0 je zpravidla počátečním stavem. Jediná proměnná se jménem znak obsahuje znak pole, nad nímž je hlava. Příkaz STOP ukončí výpočet T-stroje, rovněž tak, není-li uvedena reakce na určitou konfiguraci.
@
.
@
, tj. o 1
pozici za konec čísla (během tohoto přesunu obsah pásky neměníme, tj. pokaždé
na dané pole zapíšeme původní znak). Poté se vrátíme o jednu číslici zpět
a otestujeme ji. Je-li to 1, T-stroj zastavíme ve stavu S2 (odpovídajícím
odpovědi ano), jinak ve stavu S1 a odpověď je ne.
begin
... end