{{indexmenu_n>5}} ======== HW 05 - Maticové počty ======== ^ Termín odevzdání | 31.03.2018 23:59 PDT (([[https://www.timeanddate.com/time/zones/pst|PDT]]))| ^ Povinné zadání | 2b | ^ Volitelné zadání | 2b| ^ Bonusové zadání | **5b** 12.17.05.2018 23:59 PDT| ^ Počet uploadů | 20 | V této úloze budete mít za úkol implementovat maticové operace sčítání, odčítání a násobení. Všechny prvky všech matic (i v průběhu výpočtu) se vejdou do 32-bitového znaménkového typu integer. Pokud nebude vstup ve správném formátu nebo nepůjde provést příslušnou maticovou operaci, tak vypiště "''Error: Chybny vstup!''" a konec řádku na standardní chybový výstup a ukončete program s návratovou hodnotou ''100''. Není třeba kontrolovat bílé znaky (mezery a nové řádky); stačí tedy ověřit, že jsou na vstupu dvě celá čísla reprezentující velikost matice a následně správný počet celých čísel odpovídající velikosti matice (například pomocí ''scanf()''). Pokud budete používat dynamickou alokaci paměti (''malloc()'', ''calloc()''), tak doporučujeme použít program [[http://valgrind.org/|Valgrind]] ještě před nahráním do odevzdávacího systému pro kontrolu práce s pamětí. Velikost vstupních matic (povinného a volitelného zadání) je přesně specifikována vstupním formátem, proto je **doporučeno načítat vstup postupně po celých číslech** a nikoliv po řádcích např. funkcí ''getline()''. V případě bonusového zadání se může použití funkce ''getline()'' zdát výhodné, ale ani tady to není nutné. Opět můžete načítat první řádek postupně po celých číslech a tím identifikovat počet sloupců. Následně můžete již alokovat potřebnou velikost paměti, např. funkcí ''realloc()'' a postupovat identicky s povinným/volitelným zadáním. ====== Povinné zadání ====== Na standardním vstupu jsou pouze dvě matice s jednou operací (+,-,*). Vaším úkolem je provést zadanou operaci a vypsat na standardní výstup výslednou matici. ===== Formát vstupu ===== Na standardním vstupu jsou dvě nebo i více matic oddělených jedním řádkem se znakem operace (+,-,*). Každá matice má na prvním řádku nejprve svoji velikost ($n$, $m$) a následuje $n$ řádků vždy s $m$ hodnotami matice. Jednotlivé hodnoty jsou oddělené mezerami (//whitespaces//). ===== Formát výstupu ===== Formát výstupu je stejný, ale obsahuje pouze jednu matici. Nezapomeňte, že na konci řádku není mezera a i za posledním řádkem je znak nového řádku. ==== Příklad 1 - pub01-m ==== $ \left( \begin{array}{cc} 76 & 98 & -31 \\\\ 30 & 30 & 32 \end{array} \right) - \left( \begin{array}{c} 89 & 25 & 38 \\\\ 1 & -32 & -38 \end{array} \right) = \left( \begin{array}{c} -13 & 73 & -69 \\\\ 29 & 62 & 70 \end{array} \right) $ ^ Standardní vstup ^ Očekávaný výstup ^ Očekávaný chybový výstup ^ Návratová hodnota ^ | 2 3 76 98 -31 30 30 32 - 2 3 89 25 38 1 -32 -38 | 2 3 -13 73 -69 29 62 70 | žádný | 0 | ==== Příklad 2 - pub02-m ==== $ \left( \begin{array}{cc} -59 & 78 & -85\end{array} \right) \times \left( \begin{array}{c} 78 \\\\ -28 \\\\ -97\end{array} \right) = \left( \begin{array}{c} 1459\end{array} \right) $ ^ Standardní vstup ^ Očekávaný výstup ^ Očekávaný chybový výstup ^ Návratová hodnota ^ | 1 3 -59 78 -85 * 3 1 78 -28 -97 | 1 1 1459 | žádný | 0 | ==== Příklad 3 - pub03-m ==== ^ Standardní vstup ^ Očekávaný výstup ^ Očekávaný chybový výstup ^ Návratová hodnota ^ | 2 3 16 41 -98 * 3 1 96 -67 49 | žádný | Error: Chybny vstup! | 100 | ==== Příklad 4 - pub04-m ==== $ \left( \begin{array}{cc} 81 & -96 & -56 & -9 \\\\ -19 & 66 & 37 & -21 \\\\ 20 & 49 & -71 & -49 \\\\ 45 & -96 & 20 & 8\end{array} \right) \times \left( \begin{array}{c} -89 & -96 \\\\ 76 & 75 \\\\ 65 & 2\end{array} \right) $ ^ Standardní vstup ^ Očekávaný výstup ^ Očekávaný chybový výstup ^ Návratová hodnota ^ | 4 4 81 -96 -56 -9 -19 66 37 -21 20 49 -71 -49 45 -96 20 8 * 3 2 -89 -96 76 75 65 2 | žádný | Error: Chybny vstup! | 100 | ====== Volitelné zadání ====== Na vstupu je sekvence matic o maximální délce 100 spolu se zadanými operacemi. Operace vyhodnocujte podle jejich priority a vypište až výslednou matici. To odpovídá tomu, jako kdyby byl následující výraz s maticemi A až F: $$ A + B * C + D * E - F$$ ozávorkován následujícím způsobem: $$ A + (B * C) + (D * E) - F$$ ==== Příklad 1 - pub01-o ==== $ \left( \begin{array}{cc} 6 & 4\end{array} \right) + \left( \begin{array}{cc} -6 & 7\end{array} \right) + \left( \begin{array}{cc} -6 & -4\end{array} \right) = \left( \begin{array}{cc} -6 & 7\end{array} \right) $ ^ Standardní vstup ^ Očekávaný výstup ^ Očekávaný chybový výstup ^ Návratová hodnota ^ | 1 2 6 4 + 1 2 -6 7 + 1 2 -6 -4 | 1 2 -6 7 | žádný | 0 | ==== Příklad 2 - pub02-o ==== $ \left( \begin{array}{cc} 0 & 4 & -9 \\\\ -9 & 6 & -4 \\\\ 3 & 5 & -2 \\\\ -1 & 7 & 5\end{array} \right) \times \left( \begin{array}{cc} -10 & -9 & -8 & 9 \\\\ -4 & 0 & -9 & 1 \\\\ 4 & 6 & -9 & 5\end{array} \right) + \left( \begin{array}{cc} 0 & -9 & 3 & -6 \\\\ 10 & -9 & 8 & -7 \\\\ -1 & 0 & 5 & 1 \\\\ 3 & 2 & -9 & 9\end{array} \right) = \left( \begin{array}{cc} -52 & -63 & 48 & -47 \\\\ 60 & 48 & 62 & -102 \\\\ -59 & -39 & -46 & 23 \\\\ 5 & 41 & -109 & 32\end{array} \right) $ ^ Standardní vstup ^ Očekávaný výstup ^ Očekávaný chybový výstup ^ Návratová hodnota ^ | 4 3 0 4 -9 -9 6 -4 3 5 -2 -1 7 5 * 3 4 -10 -9 -8 9 -4 0 -9 1 4 6 -9 5 + 4 4 0 -9 3 -6 10 -9 8 -7 -1 0 5 1 3 2 -9 9 | 4 4 -52 -63 48 -47 60 48 62 -102 -59 -39 -46 23 5 41 -109 32 | žádný | 0 | ==== Příklad 3 - pub03-o ==== ^ Standardní vstup ^ Očekávaný výstup ^ Očekávaný chybový výstup ^ Návratová hodnota ^ | 2 2 3 x10 -9 5 + 2 2 8 -5 1 8 + 2 2 -4 6 -2 8 | žádný | Error: Chybny vstup! | 100 | ==== Příklad 4 - pub04-o ==== $ \left( \begin{array}{cc} -1 \\\\ 4\end{array} \right) + \left( \begin{array}{cc} -1 \\\\ 0\end{array} \right) + \left( \begin{array}{cc} 8 & 5 \\\\ 10 & -8\end{array} \right) \times \left( \begin{array}{cc} 5 \\\\ 5\end{array} \right) = \left( \begin{array}{cc} 63 \\\\ 14\end{array} \right) $ ^ Standardní vstup ^ Očekávaný výstup ^ Očekávaný chybový výstup ^ Návratová hodnota ^ | 2 1 -1 4 + 2 1 -1 0 + 2 2 8 5 10 -8 * 2 1 5 5 | 2 1 63 14 | žádný | 0 | ====== Bonusové zadání ====== Na vstupu jsou matice zadány ve formátu $název=[x11 \; x12 \; ... \; x1n; x21 \; x22 \; ... \; x2n; ... ; xm1 \; xm2 \; ... \; xmm]$ a maticová operace je poté zadána pomocí názvů jednotlivých matic. * názvy matic jsou velká písmena, přičemž seznam matic předchází zadané operaci * definice jedné matice zabírá jeden řádek * členy matice se zapisují do hranatých závorek * jednotlivé členy na řádku jsou odděleny mezerou, jednotlivé řádky jsou odděleny středníkem * výpočet je oddělen od definic matic volným řádkem * výpočetní operace se skládá z libovolného množství operandů. * operandy jsou pouze +,-,* přičemž operace se vyhodnocují podle priority stejně jako u volitelného zadání * výstupem programu je výsledek maticové operace formátovaný podle pravidel popsaných výše * počet matic je omezen počtem písmen v abecedě, ale délka výrazu není nijak omezena ==== Příklad 1 - pub01 ==== $ B = \left( \begin{array}{cc} 5 & 2 & 4 \\\\ 0 & 2 & -1 \\\\ 3 & -5 & -4\end{array} \right),\;\;\; E = \left( \begin{array}{cc} -6 & -5 & -8 \\\\ -1 & -1 & -10 \\\\ 10 & 0 & -7\end{array} \right),\;\;\; R = \left( \begin{array}{cc} -1 & -7 & 6 \\\\ -2 & 9 & -4 \\\\ 6 & -10 & 2\end{array} \right) $ $ R + E + B = \left( \begin{array}{cc} -2 & -10 & 2 \\\\ -3 & 10 & -15 \\\\ 19 & -15 & -9\end{array} \right) $ ^ Standardní vstup ^ Očekávaný výstup ^ Očekávaný chybový výstup ^ Návratová hodnota ^ | B=[5 2 4; 0 2 -1; 3 -5 -4] E=[-6 -5 -8; -1 -1 -10; 10 0 -7] R=[-1 -7 6; -2 9 -4; 6 -10 2] R+E+B | [-2 -10 2; -3 10 -15; 19 -15 -9] | žádný | 0 | ==== Příklad 2 - pub02 ==== ^ Standardní vstup ^ Očekávaný výstup ^ Očekávaný chybový výstup ^ Návratová hodnota ^ | K=[-10 0 2; -6 10 -6; -9 2 0] D=[0 6 7] M=[10 -5 -4] D*K+M | [-89 69 -40] | žádný | 0 | ==== Příklad 3 - pub03 ==== ^ Standardní vstup ^ Očekávaný výstup ^ Očekávaný chybový výstup ^ Návratová hodnota ^ | R=[6 9; -3 9; -9 10] K=[2 -8 8; -1 2 -4] K+K*R*K | [-96 332 -384; 78 -252 312] | žádný | 0 | ==== Příklad 4 - pub04 ==== ^ Standardní vstup ^ Očekávaný výstup ^ Očekávaný chybový výstup ^ Návratová hodnota ^ | M=[-9 5 9; -7 8 7; 10 -3 3] M*M+M-M | [136 -32 -19; 77 8 14; -39 17 78] | žádný | 0 | ... ==== Příklad 10 - pub10 ==== Poslední veřejný příklad je inspirován jedním ze způsobů výpočtu [[https://cs.wikipedia.org/wiki/Fibonacciho_posloupnost|Fibonacciho čísla]]. Výsledná matice bude obsahovat sumy prvních 24, 25 ((Možno ověřit na [[http://www.wolframalpha.com/input/?i=sum+Fibonacci%5Bx%5D+from+1+to+25|WolframAlpha]])) a 26 Fibonacciho čísel. $$\sum_{i=1}^{25} A^i = \sum_{i=1}^{25}\left( \begin{array}{cc} 1 & 1 \\\\ 1 & 0\end{array} \right)^i$$ ^ Standardní vstup ^ Očekávaný výstup ^ Očekávaný chybový výstup ^ Návratová hodnota ^ | A=[1 1; 1 0] A+A*A+A*A*A+A*A*A*A+A*A*A*A*A+A*A*A*A*A*A+ ... | [317809 196417; 196417 121392] | žádný | 0 | ====== Odevzdání a hodnocení ====== Veřejné příklady + Makefile: * Povinné (man) a volitelné (opt) zadání: {{:courses:b3b36prg:hw:prg-hw05.zip|}} * Bonusové zadání: {{:courses:b3b36prg:hw:prg-hw05b.zip|}} Dále obsahují zip soubory binární spustitelné soubory referenčního řešení ''hw05-test'' a ''hw05b-test'', které lze použít pro ověření funkčnosti programu před jeho odevzdáním. Kromě přiložených testovacích vstupních souborů je doporučeno vytvořit si další testovací vstupy. ===== Kompilace a sestavení programu v US ===== /*Zadání úkolu pouze specifikuje rozhraní (funkce) pro načtení grafu, řešení úlohy hledání nejkratších cest, uložení nalezených cest a uvolnění paměti. Rozhraní je definováno v souboru ''dijkstra.h'' a kromě těchto funkcí lze definovat libovolné další funkce potřebné pro řešení úlohy. Podobně rozdělení na moduly může být řešeno různě. Jedinou podmínkou odevzdávaných souborů je, že žádný odevzdávaný zdrojový soubor neimplementuje hlavní funkci programu ''main''. Ovšem pro účely testování takový soubor potřebujete, jen jej nebudete odevzdávat. */ Váš program může být složený z více souborů. ((Doplněno 28. 3. 2018 na základě studentského dotazu.)) Odevzdané soubory překládany a linkovány předpisem ''Makefile'' pro GNU Make uvedeným níže. Skript je napsán tak, aby využíval automatické detekce zdrojouvých souborů .c, ale zároveň umožňoval specifikovat konkrétní pořadí linkovaných objektových souborů (.o). V případě, kdy je nutné explicitně uvést pořadí tak, aby při sestavení byly postupně zjišťovány jednotlivé funkce definované v ostatních modulech, je možné využít předpisu pořadí zdrojových souborů v souboru ''modules.mk'', který je načítán před automatickou detekcí zdrojových souborů. uniq = $(if $1,$(firstword $1) $(call uniq,$(filter-out $(firstword $1),$1))) -include modules.mk HW=hw05 TARGET=main CFLAGS+=-std=c99 -g -pedantic -Wall -Werror LDFLAGS+=-lm SRC:=$(TARGET).c $(SRC) SRC+=$(wildcard *.c) OBJS:=$(patsubst %.c,%.o,$(call uniq,$(SRC))) bin: $(TARGET) $(OBJS): %.o: %.c $(CC) -c $< $(CFLAGS) $(CPPFLAGS) -o $@ $(TARGET): $(OBJS) $(CC) $(OBJS) $(LDFLAGS) -o $@ clean: $(RM) $(OBJS) $(TARGET) $(RM) -f ${HW}-brute.zip .PHONY: clean zip ^ ^ Povinné zadání ^ Volitelné zadání ^ Bonusové zadání ^ ^ Název v BRUTE | HW05 || HW05B | ^ Odevzdávané soubory | main.c (+ *.h, *.c) ||| ^ Argumenty při spuštění | žádné ||| ^ Kompilace pomocí | clang -pedantic -Wall -Werror -std=c99 ||| ^ Procvičované oblasti | pole variabilní délky \\ indexování v poli | dynamická alokace paměti | dynamická alokace paměti \\ práce s pointry |