Druhá série třetí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

3-2-1 Zase posloupnost

Je dána posloupnost čísel a1, a2, … , an, n≥ 1 a celé číslo k. Napište program, který v této posloupnosti najde souvislý úsek, jehož součet (tj. součet všech jeho členů) se nejvíce blíží číslu k. Souvislý úsek je takový, že existují p , r , 1≤ p ≤ r ≤ n tak, že ai je ze souvislého úseku právě tehdy, když p ≤ i ≤ r. Číslu k se nejvíce blíží takové l, pro které má výraz |k - l | nejmenší hodnotu.

3-2-2 Minimální kruh

Je dána množina bodů v rovině {[x1,y1],[x2,y2],… ,[xn,yn]}, n ≥ 2. Napište program, který k této množině najde střed [x,y] a poloměr takového kruhu, jenž obsahuje všechny body množiny a ze všech kruhů s touto vlastností má nejmenší poloměr.

3-2-3 Podivná matice

Je dána matice 2×2 celých čísel Y1=
(0   3 )
2   1
. Obecně matici Yn+1 o rozměru 2n+1×2n+1 dostaneme z matice Yn o rozměru 2n×2n podle následujícího „receptu“: rozdělíme matici Yn+1 na čtvrtiny (kvadranty) Q0 … Q3, které očíslujeme stejně jako kvadranty matice Y1 (u Y1 klademe pořadové číslo kvadrantu rovné hodnotě prvku, který v tomto kvadrantu leží). Pak začneme do matice Yn+1 vpisovat čísla 0, 1, … , 22n+2-1 v tomto pořadí: 0 napíšeme do kvadrantu Q0 na místo 0 v matici Yn, 1 do Q1 na místo 0 v Yn, …, 4 do kvadrantu Q0 na místo 1 v Yn, 5 do Q1 na místo 1 v Yn, … Obecně zapisujeme číslo i do kvadrantu Qi mod 4 na místo, které v matici Yn zaujímá číslo ⌊i / 4 ⌋. Např. pro n=2 je to matice
( 0 12 3 15 )
8 4 11 7
2 14 1 13
10 6 9 5
.

Napište program, který pro dané n a k, k<2n, vytiskne k-tý řádek matice Yn (řádky se číslují odshora počínaje 0). Pozor, číslo 22n udávající počet prvků matice může být poměrně velké ve srovnání s velikostí paměti vašeho počítače.

3-2-4 Preprocesor

Jsou specifikovány dva typy textových souborů, a sice soubory definiční a soubory zdrojové. V definičních souborech se definují makra a konstanty (konstanta je vlastně makro bez parametrů, proto se dále pod pojmem makro rozumí i konstanta, není-li uvedeno jinak). Ve zdrojových souborech je napsán text s použitím nadefinovaných maker, přičemž výsledný tvar textu dostanete nahrazením jména makra jeho skutečnou hodnotou.

Definice makra zabírá právě jeden řádek (tzn. je ukončena znakem konce řádku a tento znak se nevyskytuje nikde uvnitř definice). Definice makra se skládá ze dvou částí. V první části je uvedeno jméno makra následované bezprostředně (tzn. bez mezery) seznamem formálních parametrů. Seznam parametrů je uzavřen do kulatých závorek a jednotlivé parametry jsou v něm odděleny čárkou. Jde-li o definici konstanty, tento seznam chybí. Jménem makra je libovolná posloupnost písmen a číslic začínající písmenem, velká a malá písmena se nerozlišují. Jméno formálního parametru má stejný tvar. Za pravou závorkou uzavírající seznam parametrů (jde-li o definici makra) nebo za posledním znakem jména konstanty (jde-li o definici konstanty) následuje alespoň jeden mezerový znak (tj. mezera nebo tabulátor) a po něm následuje druhá část definice, která je tvořena libovolným znakovým řetězcem. Tento řetězec se používá jako náhrada za jméno makra při rozvíjení zdrojových souborů. Lze v něm využít i formálních parametrů s následujícím omezením:

  1. Za výskyt formálního parametru se nepovažuje výskyt odpovídajícího řetězce znaků vázaný ve slově (tzn. takový, který je těsně předcházen nebo následován písmenem nebo číslicí).
  2. Za výskyt formálního parametru se rovněž nepovažuje výskyt v textu uvnitř uvozovek.

Příklady:

Definice konstanty TRUE 1
Makro definované max(x,y) getmax(x,y,1,"x")
a použité ve zdrojovém souboru jako max("AHOJ","Vida")
se rozvine do tvaru getmax("AHOJ","Vida",1,"x")

Nyní už jistě tušíte svůj úkol. Napište program, který načte definiční a zdrojový soubor a ve zdrojovém souboru provede rozvinutí maker při dodržení těchto podmínek:

  1. Za výskyt makra se nepovažuje výskyt vázaný ve slově nebo v textu uvnitř závorek.
  2. Z více definic téhož makra (makra jsou stejná, shodují-li se ve jménu a počtu parametrů) platí ta, která byla v definičním souboru uvedena poslední.
  3. Při rozvíjení maker se postupuje od maker definovaných naposledy, tzn. obsahuje-li rozvinutý zápis makra A jiné makro B definované v definičním souboru před A, rozvine se i B, bylo-li však B definováno až po A, rozvoj se neprovádí.

Například nechť jsou v definičním souboru tyto řádky v pořadí:

A(K,L,M) cosi(K,L,B(M))
B(K)     neco(K)
Potom se ve zdrojovém souboru makro A(1,2,3) rozvine jako cosi(1,2,B(3)). Změní-li se pořadí obou řádků v definičním souboru, pak se makro A(1,2,3) rozvine jako cosi(1,2,neco(3)).