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
• 1-1-2: Posloupnost čísel
• 1-1-3: Přesun koně
• 1-1-4: Správce paměti

---

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,

program vytiskne

.

---

1-1-2 Posloupnost čísel

---

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

1. a₀=0
2. Je-li a₀, a₁, … , a_2^k-1 prvních 2^k členů posloupnosti (k≥ 0), pak dalších 2^k členů je definováno vztahem a_j=(a_j-2^k+1) mod 3 pro j=2^k, … , 2^k+1-1.

Napište program, který pro zadané přirozené číslo n vypíše n-tý člen posloupnosti a_n. Např. pro n=14 program vypíše a₁₄=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 (x₁,y₁), (x₂,y₂) vypíše nejmenší možný počet tahů potřebných na přesunutí šachového koně z pole (x₁,y₁) na pole (x₂,y₂). Zadaná celá čísla x₁, x₂ jsou z rozmezí od 1 do m a y₁, y₂ 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;

Menu