Zadání úloh ústředního kola 42. ročníku
P-III-1
Body X
1=(x
1,y
1), ...,
X
m=(x
m,y
m) (m>=3)
jsou (v tomto pořadí, proti směru
hodinových ručiček) vrcholy konvexního m-úhelníka M v rovině.
Mnohoúhelník M leží vevnitř kruhu K se středem S=(xs,ys) a
poloměrem r
(to znamená, že každé Xi je vniřním bodem K).
Říkáme, že bod u ležící na obvodu (hranici) M je viditelný z bodu v,
jestliže úsečka uv neobsahuje vnitřní body M. (Všimněte si, že podle této
definice jsou všechny body strany XiXi+1
viditelné z každého bodu přímky
XiXi+1;
na druhé straně, obvod M je neviditelný pro vnitřní body M!)
Napište a zdůvodnětě co nejrychlejší program, který:
- Vypočítá a vypíše takové údaje, ze kterých bude pro libovolný bod v ležící
na obvodu kruhu K zřejmé, které body ležící na obvodu M jsou z bodu v viditelné.
- Určí minimální počet bodů ležících na obvodu K tak, aby každý bod na
obvodu M byl viditelný alespoň z jednoho z nich.
Poznámka
V programu můžete použít vzorce z analytické geometrie (např.
pro vzdálenost 2 bodů anebo pro průsečík dvou přímek, přímky a kružnice apod.)
jako funkce; tyto funkce nemusíte programovat.
P-III-2
Multiplikativní složitost
Lineární algoritmus je algoritmus následujícího tvaru:
Vstup: x
1, x
2, ..., x
n (vstupní proměnné)
f
1:=g
1 op h
1
f
2:=g
2 op h
2
....
f
k:=g
k op h
k
Výstup: y
1, y
2, ..., y
m (výstupní proměnné)
přičemž pro každé i=1, ..., k je g
i, h
i prvkem
{x
1, ..., x
n} U {f
1, ..., f
i-1}
a op je jedna z operací +, -, * (sčítání, odčítání, násobení).
Složitost lineárního algoritmu je počet operací op, multiplikativní složitost
lineárního algoritmu je počet operací *.
Například následující lineární algoritmus:
Vstup: a, b, c, d
f1 := a * b
f2 := c * d
f3 := f1 - f2
Výstup: f3
počítá hodnotu výrazu ab-cd a má multiplikativní složitost 2.
Úloha
Zjistěte, jakou činnost vykonává následující lineární algoritmus:
Vstup: a, b, c, d
f
1:=a+b
f
2:=c+d
f
3:=a*c
f
4:=b*d
f
5:=f
1*f
2
f
6:=f
5-f
3
f
7:=f
3-f
4
f
8:=f
6-f
4
Výstup: f
7, f
8
a rozhodněte, zda existuje lineární algoritmus
počítající f
7 a f
8 s
lepší multiplikativní složitostí.
P-III-3
Jsou dány mince v hodnotě q
1, ...,
q
n korun, kde 1<=q1<q2<...<qn jsou přirozená
čísla a q
i+1/q
i je liché přirozené číslo
pro 1<=i<n.
Plátce i příjemce mají k dispozici neomezený počet mincí každé hodnoty.
Plátce má zaplatit příjemci obnos X korun. Platba je optimální, jestliže
se při ní vymění nejmenší možný počet mincí; tj. pro každé 1<=i<=n
dá plátce
xi(>=0) mincí hodnoty qi, příjemce dá yi(>=0) mincí hodnoty qi tak, že
suma (xi-yi)qi = X a přitom suma (xi+yi) je minimální.
Například při mincích s hodnotou 1, 3 a 9 korun (n=3) se dá 17 korun vyplatit
tak, že plátce dá 1 devítikorunu, 2 trojkoruny a 2 jednokoruny, vymění se 5 mincí.
Při optimální platbě ovšem dá plátce 2 devítikoruny a příjemce vrátí 1 jednokorunu,
vymění se 3 mince.
Napište a zdůvodněte program, který pro vstupní kladné celé číslo X určí
optimální způsob platby X korun.
P-III-4
McCullochův stroj
McCullochův stroj slouží ke zpracování čísel. Má vstup a výstup; jestiže
na vstup dáme číslo, tj. konečnou neprázdnou posloupnost cifer 1, 2, ..., 9,
po konečném čase se na výstupu může (ale nemusí) objevit (obecně jiné) číslo -
odpověď stroje na vstupní číslo. V prvním případě (jestliže se odpověď objeví),
vstupní číslo se nazývá přijatelným. Odpověď stroje je vstupním číslem jednoznačně
určená:
- jestliže je vstupní číslo přijatelné, odpověď se objeví vždy a je vždy stejná.
- jestliže vstupní číslo není přijatelné, nikdy se neobjeví odpověď a stroj
se po konečném čase zastaví (tj. můžeme zjistit, že vstupní číslo není přijatelné).
Zavedeme si tato značení:
- Jak již bylo řečeno, čísla jsou pro nás kladná celá
čísla, jejichž desítkový zápis neobsahuje nulu.
- Jestliže X, Y jsou čísla, pak XY označuje jejich spojení: číslo, které dostaneme
napsáním zápisů čísel X, Y za sebou (v tomto pořadí). Např. pro X=53 a Y=728 je
XY=53728 a XYX=5372853. Číslo XX..X (k-krát) zapíšeme jako Xk.
- Zdvojením čísla X je číslo XX, tj. např. zdvojením čísla X=12345 je XX=1234512345.
- Říkáme, že číslo X vytváří číslo Y, jestliže X je přijatelné a po zadání X na
vstup stroje je odpovědí Y. Tento vztah budeme zkráceně zapisovat X->Y.
McCullochův stroj se řídí následujícími pravidly:
- Pravidlo P1: Pro libovolné číslo X, 2X2 je přijatelné a vytváří X (2X2->X).
- Pravidlo P2: Pro libovolná čísla X, Y, jestliže X vytváří Y, pak 7X vytváří Y2. Zkráceně: z X->Y plyne 7X->Y2.
- Pravidlo P3: Pro libovolná čísla X, Y, jestliže X vytváří Y, pak 5X vytváří
zdvojení čísla Y, tedy z X->Y plyne 5X->YY.
- Pravidlo P0: Číslo X je přijatelné pravě tehdy, když to vyplývá z pravidel
P1, P2, P3.
Například 2532->53 podle P1, 72532->532 podle P2, 572532->532532 podle P3,
ale 4253 není přijatelné podle P0.
Operační číslo je číslo složené z cifer 5, 7. Každé operační číslo M určuje
operaci M() v následujícím smyslu: z X->Y plyne MX->M(X). Např. 5 určuje
operaci zdvojení (5(Y)=YY), neboť z X->Y plyne 5X->YY. 75 určuje operaci
připsání 2 ke zdvojení (75(Y)=YY2), neboť z X->Y plyne 75X->YY2.
V řešení můžete bez důkazu využít následující vlastnosti (z minulých kol):
- existuje číslo vytvářející samo sebe (X->X)
- (McCullochův zákon) pro každé číslo A existuje takové číslo X, že
X vytváří AX, tj. X->AX
- (Craigův zákon) Pro každé operační číslo M a pro každé číslo A existuje
číslo X vytvářející M(AX), tj. X->M(AX).
- (Fergussonův zákon) Pro libovolná A, B existují čísla X, Y tak, že
X->AY a zároveň Y->BX.
Číslo X0 je nesmrtelné, jestliže následující proces není konečný
(tj. nevyskytne se v něm nepřijatelné číslo):
Zadám stroji číslo X0.
Jestliže se objeví výsledek X1, zadám stroji číslo X1
Jestliže se objeví výsledek X2, zadám stroji číslo X2
atd.
McCullochův algoritmus zjišťování nesmrtelnosti čísel: Základem algoritmu
je číslo H takové, že X je nesmrtelné, pravě když HX není nesmrtelné.
VSTUP: číslo X
ALGORITMUS:
1) Y:=X; U:=HX
2) stroji S1 zadáme Y; stroji S2 zadáme U
3) Jestliže stroj S1 dá odpověď Z, pak Y:=Z;
jinak STOP - číslo X není nesmrtelné
4) Jestliže stroj S2 dá odpověď V, pak U:=V;
jinak STOP - číslo X je nesmrtelné
5) skok na 2
Úlohy
- Najděte 4 nesmrtelná čísla.
- Najděte 1993 nesmrtelných čísel.
- Je McCullochův algoritmus správný?