HW 05 - Maticové počty

Termín odevzdání 31.03.2018 23:59 PDT 1)
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 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 \; \ldots \; x1n; x21 \; x22 \; \ldots \; x2n; \ldots ; xm1 \; xm2 \; \ldots \; 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 Fibonacciho čísla. Výsledná matice bude obsahovat sumy prvních 24, 25 2) 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:

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

Váš program může být složený z více souborů. 3) 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
2)
Možno ověřit na WolframAlpha
3)
Doplněno 28. 3. 2018 na základě studentského dotazu.
courses/b3b36prg/hw/hw05.txt · Last modified: 2018/05/13 10:17 by faiglj