Projekty z programování na FIT VUT: Projekt 3 — maticové operace

Třetí projekt (maticové operace) byl zaměřený na tvorbu obecných řešení, práci s dynamicky alokovanou pamětí a nakonec práce s číselnými poli (a tím pádem ukazateli a vůbec vším, s čím je toto spojeno 😀 ). Úkolem bylo vytvořit program (subroutiny) pro součet a skalární součin vektoru a maticový součin. Toliko k jednoduchým úkolům. Náročnější bylo programování dvou ze čtyř úloh — osmisměrka, počítadlo „bublin“, průchod bludištěm a konečně „Kulečník“. Ale postupně.

Dobrá rada ze začátku zdarma: NEOPISUJTE!!! Studujete-li FIT na VUT v Brně a řešíte projekt, neopisujte můj kód. Ačkoli je program licencován GPLv3+, tak nedoporučuji opisovat. Prvně — já již projekt odevzdal a pokud vím, tak ten FIŤácký soft pro odhalování plagiátů má ten „můj“ vzorek již uložen. A dále — pokud sami nebudete programovat, nenaučíte se to.

Vstup je ze souboru, přičemž soubor má tvar:

T
A B C

e f g h i
j k l m n

p q r s t
u v w x y

kde T je typ vstupních dat:

  • T = 1 — Vektor; A je počet prvků vektoru; B,C nedefinováno
  • T = 2 — Matice; A je počet řádků, B je počet sloupců; C nedefinováno
  • T = 3 — 3D Matice; A je počet 2D matic, B je počet řádků; C je počet sloupců

a dále následují jednotlivé prvky (ey) v [1,2,3].

Předávání a ukládání dat

Při programování je velice podstatné si hned ze začátku určit (rozmyslet), v čem (jak) budou předávány data. Já jsem ve svém řešení použil strukturu, ve které se ukládají všechny informace k danému souboru (načtená data). Je jedno, jestli se bude ve struktuře nacházet vektor, matice nebo 3D matice. Dále struktura uchovává všechny detaily — typ uložených dat, počet matic, řádků či sloupců.

struct DATA
{
	int typ;
	int pocet_sloupcu;
	int pocet_radku;
	int pocet_matic;
	int vysledna_hodnota;
	int *vektor;
	int **matice;
	int ***vmatic;
};

Jednotlivá pole vektor, matice či vmatic jsou alokovány (a využívány) podle typu. Celkem se routiny mohou využívat až tři struktury: A, B a vysledna.

Například při skalárním sčítání vektorů (a + b) se výsledek uloží do třetí struktury — výsledek, která bude typu 1 — vektor.

Při volání subroutiny jménem vadd() se předávají ukazatele na tři struktury, ve kterých jsou uloženy právě a, b a výsledek. Prototyp funkce tedy bude:

vadd(struct DATA a, struct DATA b, struct DATA vysledek)

Alokace a dealokace paměti

Pokud víme, v čem budeme ukládat data, je nutné alokovat paměť. Napřed je třeba data načíst a při načítání je rovnou překontrolujeme. Při načítání souboru se tedy bude pracovat takto:

  1. Otevře se soubor
  2. Načte se jedno číslo a uloží se do struktury data->typ
  3. Dále se rozhodne dle typu:
    • Jestliže je data->typ rovno 1, načte se jen jedno číslo a uloží se do data->pocet_sloupcu.
    • Jestliže je data->typ rovno 2, načtou se dvě čísla a uloží se do data->pocet_radku a data->pocet_sloupců.
    • Jestliže je data->typ rovno 3, načtou se tři čísla a uloží se postupně do data->pocet_matic, data->pocet_radku a data->pocet_sloupců.
  4. Následně se dle typu alokují příslušná pole dle příslušných rozměrů.
  5. Začnou se postupně načítat jednotlivá čísla do jednotlivých prvků polí.
  6. Pokud „dojdou“ prvky dříve, než bude pole plné (a nebo pokud bude prvků víc), program skončí s chybou. Jinak subroutina vrací úspěch.

Uvolnění polí bude probíhat stejně — vyhodnotí se typ a dle typu se provede free(). A (překvapivě) je na stejném principu (tj. kontrole data->typ i funkce pro výpis výsledku na terminál).

Jednoduché maticové operace

Sem spadají všechny tyto operace:

  • Vektorový součet dvou vektorů (a b)
  • Skalární součin dvou vektorů (a*b)
  • Součin matic (A*B)
  • Maticový výraz (A*B*A)

Zde není moc o čem psát — jedná se o triviální cykly, mající na vstupu vždy dvě vstupní struktury a strukturu, do které se bude vše ukládat. Vždy na začátku subroutiny se vyplní pocet_radku/sloupcu a typ výsledné struktury. Poté se zavolá alokační subrotina, která pro tato data alokuje prostor.

Například při vektorovém součtu (a + b) je nutné, aby byly data->pocet_sloupcu v a i b shodné. data->typ výsledné struktury bude 1. Alokační funkce poté rovnou alokuje vektor o velikosti vysledek->pocet_sloupcu.

Osmisměrka

Již náročnější úloha je osmisměrka. Úkolem je zjistit, zda se zadaný vektor nachází v zadané matici v kterémkoli z osmi možných směrů. Myslím, že není třeba, abych popisoval, co to osmisměrka je.

Opět poměrně jednoduché řešení. Postupně se bude procházet matice po jednotlivých prvcích. Pokud je daný prvek, na kterém se zrovna „stojí“ shodný s prvním prvkem vektoru, tak se postupně začnou kontrolovat jednotlivé směry: je-li na i-tém kroku prvek na matice[x+x_increment,y+y_increment] shodný s prvkem vektor[i], poté je hledání ukončeno a oznámeno,že se v matici nachází vektor.

Pokud se někde budou lišit, přeskočí se na další z osmi směrů. Dalším důvodem k přeskoku do dalšího směru je, pokud se posun v matici v daném směru dostane mimo rozměry matice. Pokud se dostane hledání až na konec matice a vektor se v matici neindentifikuje, bude hledání označeno jako neúspěšné.

Celkem jednoduchý algoritmus, horší je jeho napsání, ale i tak se při řádné dekompozici zjednoduší na několik cyklů a podmínek 🙂

Počítadlo Bublin

Bublina je v tomto pojetí seskupení nulových prvků v matici takových, že sousedí v jednom ze čtyř směrů — S, J, V, Z. Například v matici na demonstračním obrázku je 5 bublin:

Princip mnou vytvořeného algoritmu:

  1. Najít v poli všechny nuly a jejich souřadnice zapsat do pole. Při procházení bude prvky v poli měnit následně:
    • Byl-li prvek nenulový, změní se jeho hodnota na nulu.
    • Byl-li prvek nulový, změní se jeho hodnota na hodnotu jedna.
  2. Postupně procházet souřadnice s nulami. Při skoku se inkrementuje počítadlo nul. A daná souřadnice se odstraní ze seznamu. Jednička se změní na číslo 2 — tedy se označí jako započítaná.
  3. Postupně se projdou 4 sousední prvky. Pokud narazí na již započítaný prvek (neboli na prvek s hodnotou 2), počítadlo bublin se opět dekrementuje — neboť právě započítaná bublina již náleží k už jednou započítané.

Jediný problém je ve chvíli, kdy je bublina tvaru

5 0
0 0

neboli bublina je ve tvaru písmene L. V tomto případě je nutné snížit počítadlo ještě jednou — protože právě přidaná bublina spojila dvě jiné — musí se nejen negovat inkrementace z bodu 2), ale ještě snížit bubliny na jednu.

Má implementace navíc obsahuje bonusové rozšíření — systém totiž pracuje i se 3D maticí, takže je o něco delší a složitější, ale princip zůstává stejný.

Pokud je třeba hledat ve 2D matici, algoritmus tuto 2D převede na 3D matici, kterou posléze zpracovává.

A to je opět vše. Nic náročného, nic moc obtížného. Tentokrát bez dokumentace, pouze zdrojáky.

V případě, že byste rádi použili některou část, dodržte prosím licenci GPL verze 3 a nebo pozdější.

Napsat komentář

Vaše emailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *