Druhá série sedmé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

7-2-1 Letiště

Bylo, nebylo. V nejmenované zemi na nejmenovaném světě bylo n letišť. Mezi těmito letišti byla provozována pravidelná letecká doprava. Každá z jejích linek spojovala vždy dvě letiště. A nám se podařilo získat seznam jejich linek. Vaším úkolem bude napsat program, který pro zadaný seznam linek, tj. seznam dvojic letišť spojených nějakou leteckou linkou, zjistí, zda je možné dopravit se letecky z každého letiště na každé.

Poznámka: Letiště jsou očíslována od 1 do n.

7-2-2 Bludiště

Čtverečková síť velikosti n×n (n≤ 20) představuje bludiště. Některá pole sítě jsou zaplněná - nelze na ně vstoupit. Vaším úkolem je nalézt nejkratší cestu z daného výchozího na dané cílové pole. Délku cesty měříme počtem navštívených polí. V jednom kroku můžete přejít z pole, na kterém stojíte, na libovolné nezaplněné sousední pole ve směru vodorovném, svislém nebo šikmém. Napište program, který pro zadané výchozí a cílové pole a pro seznam zaplněných polí nalezne tuto nejkratší cestu.

7-2-3 Bezva řada

Posloupnost znaků nazveme „bezva řada“, jestliže splňuje všechny následující podmínky:

  1. obsahuje sudý počet znaků A
  2. počet znaků B není dělitelný třemi
  3. neobsahuje žádný znak C
  4. obsahuje nejvýše tři znaky D.

Napište program, který zjistí, zda je zadaná vstupní posloupnost znaků bezva řada. V programu použijte co nejmenší počet proměnných. Počet proměnných použitých ve vašem programu bude součástí hodnocení této úlohy.

7-2-4 Matice

Matice je matematický objekt charakterizovaný svým rozměrem – počtem řádků a sloupců. Matice se dají násobit. Násobení matic není komutativní, tj. A*B se nemusí rovnat B*A. Je však asociativní, tj. (A*B)*C = A*(B*C). Na vynásobení dvou matic o rozměrech o ×p a p ×r je potřeba provést o ·p ·r operací obyčejného číselného násobení a výsledná matice má rozměr o ×r. Máme-li tedy násobit několik matic A1 až An o rozměrech ai×ai+1, tj. hledáme hodnotu A1*A2*… *An, pak z hlediska počtu provedených obyčejných násobení zřejmě záleží na pořadí, v němž vypočítáme dílčí součiny matic.

Vaším úkolem tedy je napsat program, který pro zadanou posloupnost rozměrů matic, jež se mají vynásobit v daném pořadí, určí pořadí výpočtu dílčích součinů matic, aby počet číselných násobení byl minimální.

Příklad: Máme vynásobit matice o rozměrech 3×5, 5×2, 2×4 v uvedeném pořadí. Musíme násobit nejprve první dvě matice a pak výsledek vynásobit třetí maticí, použijeme při tom 3·5·2+3·2·4=54 násobení. Kdybychom vynásobili nejprve druhé dvě a pak výsledkem vynásobili první maticí, použili bychom 5·2·4+3·5·4=100 násobení.