Dokumentace k projektu pro předměty IZP a IUS
Maticové operace projekt č. 3
9.12.2007
Autor:
Václav Uhlíř,
[email protected] Fakulta Informačních Technologii Vysoké Učení Technické v Brně
Obsah 1.
Definice úvodem..........................................................................................................................1 1.1. Zadání programu......................................................................................................................1 1.2. Základní výpočty.....................................................................................................................1 1.3. Rozšířené funkce......................................................................................................................1 1.3.1. 1.3.2. 1.3.3. 1.3.4.
2.
Test sudoku..............................................................................................................................................1 Křížová rotace.........................................................................................................................................1 Submatice................................................................................................................................................1 Orba........................................................................................................................................................1
Návrh řešení................................................................................................................................2 2.1. Základní výpočty.....................................................................................................................2 2.1.1. Součet matic............................................................................................................................................2 2.1.2. Součin matic...........................................................................................................................................2
2.2. Rozšířené funkce......................................................................................................................2 2.2.1. 2.2.2. 2.2.3. 2.2.4.
Test sudoku..............................................................................................................................................2 Křížová rotace.........................................................................................................................................2 Submatice................................................................................................................................................2 Orba........................................................................................................................................................3
3.
Závěr............................................................................................................................................3
4.
Metriky kódu..............................................................................................................................4
i
1.
Definice úvodem
1.1.
Zadání programu
Cílem tohoto projektu je vytvoření programu v jazyce C, který bude provádět výpočty a operace s maticemi. Matice budou zadávané jako pole v souboru a na začátku souboru budou definovány rozměry matice.
1.2.
Základní výpočty
Výpočet součtu matic a výpočet násobení matic jsou definovány v zadání a není potřeba hledat nebo upravovat vzorce. Program zpracuje dvě vstupní matice a vrátí jednu výslednou. Pokud matice nevyhovují zvolené operaci, vypíše program „false“.
1.3. 1.3.1.
Rozšířené funkce Test sudoku
Program podle zadání provede test hodnot prvku v každém sloupci, každé řádce a v každé submatici. Pokud proběhnou všechny testy v pořádku, vrátí program „true“, v opačném případě vrátí „false“.
1.3.2.
Křížová rotace
Program provede rotace řádků a sloupců podle zadání a vypíše výslednou matici.
1.3.3.
Submatice
Program zjistí, jestli druhá zadaná matice je submaticí první. Pokud bude test úspěšný, vrátí program „true“.
1.3.4.
Orba
Program přepíše zdrojovou matici do výsledné, kde budou prvky seřazeny podle struktury „orání“.
1
2.
Návrh řešení
Program bude načítat matice ze souborů, kde budou jako první informace o rozměrech matice. Pokud budou rozměry nulové nebo záporné, vypíše program „false“. Program bude načítat počet prvků nezávisle na formátování. Pokud bude počet zadaných prvků menší než počet požadovaných, vypíše program chybu. Pokud bude zadaných prvků víc než je požadováno, program bude přebytečné prvky ignorovat.
2.1. 2.1.1.
Základní výpočty Součet matic
Pro provedení součtu matic potřebujeme matice o stejných rozměrech. Pokud matice vyhovují, program postupně sečte dané prvky z první matice s prvky matice druhé a uloží výsledné čísla do matice třetí. Pokud se nebude shodovat počet řádků nebo sloupců matice, vypíše program „false“.
2.1.2.
Součin matic
Pro součin matic program kontroluje, jestli počet sloupců první matice odpovídá počtu řádků druhé matice. V případě rozdílnosti těchto souřadnic vypíše program „false“. Pokud budou souřadnice správné, vytvoří program výslednou matici o rozměrech počtů řádků z první matice a počtu sloupců z matice druhé. Matice pak bude naplněna součtem násobků prvků podle systému násobení matic.
2.2. 2.2.1.
Rozšířené funkce Test sudoku
Aby mohla matice být systémem sudoku, musí mít rozměry N2xN2 . Pokud tomu matice neodpovídá, vypíše program „false“. Program očekává pouze hodnoty od 1 do N. Pokud některé číslo neodpovídá, program zase vrátí „false“. Program vrací také „false“, pokud se některá z hodnot v libovolném z řádků, sloupců nebo v libovolné z N submatic opakuje. Pokud matice projde všemi testy, program vypíše jako úspěšné otestování „true“.
2.2.2.
Křížová rotace
Program provede nejdříve postupnou rotaci řádků, kde první hodnota udává počet rotací. Pokud je hodnota záporná, program k ní přičte hodnotu počtu sloupců. Dále program provede rotace všech řádků a zopakuje celý potup se sloupci. Po úspěšném splnění rotací program výslednou matici vypíše.
2.2.3.
Submatice
Nejdříve program zkontroluje, jestli je údajná submatice menší než zadaná matice. Pokud je možnost, že druhá matice je submaticí, začne program porovnávat postupně všechny prvky z první matice s prvním prvkem z matice druhé. Pokud program narazí na shodu, spustí se cyklus pro porovnání každého dalšího prvku s prvky submatice. Pokud některý prvek neodpovídá, musí se program vrátit za první shodný prvek v aktuálním cyklu a pokračovat s testováním na shodnost s prvním prvkem submatice. Tento postup jsem zvolil z důvodu, že v submatici může být libovolné opakování posloupnosti prvků. Kdyby se stejná posloupnost objevila v matici s větším počtem 2
opakování, program by při běžném procházení danou submatici „přehlédl“. Pokud program nalezne danou submatici vypíše „true“. V případě, že druhá zadaná matice není submaticí první matice, program vypíše „false“.
2.2.4.
Orba
Program se bude pohybovat maticí jako „orající člověk“ a dané hodnoty bude přepisovat do výsledné matice o stejných rozměrech jako matice vstupní. Program se maticí pohybuje šikmo nahoru (přičítáním souřadnic {-1,1}) a v opačném směru (šikmo dolů{1,-1}), za podmínek, že pokud narazí na horní nebo dolní hranu, udělá „krok“ doprava a změní primární směr a pokud narazí na levou nebo pravou hranu, udělá „krok“ dolů a zase změní primární směr. Pokud je program nucen udělat 2 krát po sobě krok (buď dolů a doprava nebo v opačném pořadí – stává se v rohu matice), mění primární směr jenom jednou.
3.
Závěr
Program kompletně zpracovává zadané operace a vypočítává výsledky. Program, ale nekontroluje přetečení vstupních čísel. Kontrolu přetečení u sčítání a násobení matic jsem zapoznámkoval kvůli velké náročnosti výpočtu a předpokladu, že uživatel nebude zadávat přehnaně vysoké hodnoty.
3
4.
Metriky kódu
Počet souborů: 1 soubor Počet řádků zdrojového kódu: 687 Velikost dat před kompilací: 22 953b Velikost spustitelného souboru: 18 887b (systém Linux)
4
