Druhá série prvního ročníku KSP

Tyto úlohy pocházejí z desetileté ročenky KSP. Jejich řešení bohužel nemáme v elektronické podobě, takže na ně budete muset přijít sami.

Zadání úloh

1-2-1 Ticovo číslo

Ticovo číslo tn je definováno takto:

t0 = t1 = t2 = 1
tn = tn-1 + tn-2 + tn-3     pro n>2 (n celé).

Napište program, který pro zadané n vypíše přesnou hodnotu Ticova čísla tn.

Pozor! Posloupnost Ticových čísel roste poměrně rychle, nemůžete tedy předpokládat, že se ho podaří uchovat v jednoduché číselné proměnné.

1-2-2 Schůdná matice

Nechť M je celočíselná čtvercová matice řádu n obsahující nuly a jedničky, přičemž M1,1 = Mn,n = 1. Matice M je schůdná, jestliže se dá přejít z prvku M1,1 na prvek Mn,n. Z libovolného prvku matice lze přejít na kterýkoli nenulový sousední prvek. Sousedními prvky k Mi,j jsou:

Mi+1,j jestliže i<n
Mi-1,j jestliže i>1
Mi,j+1 jestliže j<n
Mi,j-1 jestliže j>1.

Napište program, který načte ze vstupu matici a zjistí, zda je schůdná.

1-2-3 Chutné výrazy

Chutným výrazem nazveme aritmetický výraz složený z nezáporných celých čísel, kulatých závorek a operátorů +, -, *, / s obvyklou syntaxí a prioritami. Znak / představuje celočíselné dělení.

Napište program, který přečte ze vstupu řetězec, zjistí, zda je to chutný výraz, a v kladném případě vytiskne jeho hodnotu.

Příklad: Pro vstup 5-(2+4)/2 program vytiskne 2.

1-2-4 Křížové reference

Napište generátor křížových referencí (GKR). GKR je program, který na vstupu dostane text složený z řádků. Vyhledá v něm všechny identifikátory a vytiskne jejich abecední seznam, přičemž u každého identifikátoru uvede čísla řádků, na nichž se vyskytl. Identifikátor je neprázdná posloupnost písmen a číslic začínající písmenem. U identifikátorů delších než 8 znaků uvažuje GKR jen prvních 8 znaků. Vstupní text je k dispozici jenom jednou (představujte si třeba, že vstupuje z klávesnice) a nemusí se vejít do operační paměti.

Příklad: Pro vstupní text

KREMILEK A VOCHOMURK
A
A:=A+1; C++;
(*KARELNOVY) ();
!KARELNOVOTNY!

vydá GKR výstup

A        1 2 3
C        3
KARELNOV 4 5
KREMILEK 1
VOCHOMUR 1