První 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-1-1 Mocnina matice


Napište program, který pro zadaná kladná celá čísla n, k a zadanou čtvercovou matici A řádu n vytiskne k-tou mocninu matice A (tj. součin k exemplářů matice A).

Příklad: Pro n=2, k=2,

A=
( 1 2 )
3 4

program vytiskne

( 7 10 )
15 22

.


1-1-2 Posloupnost čísel


Posloupnost kladných celých čísel an pro n=0,1,2,… je definována rekurzívně tímto způsobem:

  1. a0=0
  2. Je-li a0, a1, … , a2k-1 prvních 2k členů posloupnosti (k≥ 0), pak dalších 2k členů je definováno vztahem aj=(aj-2k+1) mod 3 pro j=2k, … , 2k+1-1.

Napište program, který pro zadané přirozené číslo n vypíše n-tý člen posloupnosti an. Např. pro n=14 program vypíše a14=0.

Poznámka: Generování prvních n členů posloupnosti je zbytečně neefektivní, pokuste se najít lepší řešení.


1-1-3 Přesun koně


Je dána šachovnice o m řádcích a n sloupcích. Napište program, který pro zadaná pole o souřadnicích (x1,y1), (x2,y2) vypíše nejmenší možný počet tahů potřebných na přesunutí šachového koně z pole (x1,y1) na pole (x2,y2). Zadaná celá čísla x1, x2 jsou z rozmezí od 1 do m a y1, y2 od 1 do n.

Příklad: Pro m=n=8 a pole (2,2) a (2,3) program vypíše číslo 3.


1-1-4 Správce paměti


Naprogramujte správce paměti. Správce paměti je nezbytná součást každého složitějšího operačního systému. Jeho funkce je jednoduchá: má k dispozici souvislý úsek paměti, který spravuje. Programům, které si ho zavolají, poskytuje dvě základní služby:

  • služba alokuj přidělí volnou paměť dané velikosti
  • služba uvolni uvolní daný úsek paměti pro další použití.
Podobné funkce plní např. v programovacím jazyce Pascal procedury new a dispose.

Předpokládejme, že je deklarováno (např. znakové) pole, které představuje kus volné paměti. Pole se v každém okamžiku skládá z volných a z obsazených úseků a případně dalších pomocných údajů. Po inicializaci správce je celé pole volné – obsahuje jeden velký volný úsek.

Procedura alokuj, jejímž vstupním parametrem je délka d požadovaného úseku, hledá v poli volný úsek délky alespoň d. Najde-li takový úsek, vyhradí v něm část délky d (tj. prohlásí ji za obsazenou), zbytek ponechá volný a vrátí index (ukazatel apod.) začátku vyhrazené části. Nenajde-li takový úsek, vrátí o tom zprávu.

Procedura uvolni, jejímž parametrem je index začátku obsazeného úseku (vyhrazeného procedurou alokuj), uvolní zadaný úsek pro další použití. Vznikne-li tím několik volných úseků vedle sebe, spojí je v jeden. Procedura může vracet informaci o tom, že byl zadán chybný parametr.

Před prvním použitím je třeba správce paměti inicializovat. K tomu slouží procedura inicializace.

Vaším úkolem tedy je napsat:

  • procedury inicializace, alokuj a uvolni
  • nepovinně (podle chuti) i další procedury, třeba clear (uvolni všechno), maxmem (délka nejdelšího dosud volného úseku) apod.

Pokud váš systém již podobné procedury obsahuje, nesmíte je zavolat, napište je sami.

Příklad deklarací v Pascalu:

const TOPMEM=999;
var MEM:array[0..TOPMEM] of char;
    {a další proměnné podle potřeby}
procedure inicializuj; begin ... end;
function alokuj(LEN:integer):integer; begin ... end;
function uvolni(IND:integer):integer; begin ... end;