Úloha: Kvaternionová maticová násobička
Kvaterniony (quaternions) a kvaternionovou algebru vymyslel v roce 1843 známý irský matematik sir William Rowan Hamilton, který původně hledal rozšíření komplexních čísel z 2D plochy do 3D prostoru. Takové rozšíření však není možné vytvořit, nejbližší ekvivalent komplexních čísel jsou až čtyřrozměrné struktury. Hamilton provedl revoluční krok v tom, že jím vymyšlené kvaterniony nesplňovaly vlastnost do té doby považovanou za samozřejmost ‒ komutativitu. Později se objevily i další užitečné struktury, které komutativitu nesplňují, například matice.
Kvaterniony jsou obdobou komplexních čísel, ovšem s tím rozdílem, že mají čtyři na sebe kolmé jednotky, které označujeme symboly 1, i, j a k. Každý kvaternion lze popsat lineární kombinací všech čtyř jednotek: q=x+yi+zj+wk. Pro vzájemné násobení těchto jednotek platí následující vztahy: 1×1 = 1, 1×i = i, 1×j = j, 1×k = k, i×1 = i, j×1 = j, k×1 = k, i×j = k, j×i = ‒k, j×k = i, k×j = ‒i, k×i = j, i×k = ‒j, i×i=j×j=k×k = ‒1, i×j×k = ‒1.
Všimněte si, že při násobení není obecně zachována komutativita operací, tj. například výsledek operace jk se nerovná výsledku operace kj. To znamená, že kvaterniony netvoří algebraickou strukturu ‒ komutativní těleso a při násobení dvou kvaternionů si musíme dát pozor na pořadí operací (ostatně podobně jako při násobení matic). Násobení jedničkou (skalární složkou, 1) zachovává hodnotu druhého prvku, podobně jako je tomu u reálných i komplexních čísel.
Vaším úkolem je vytvořit program, který co nejrychleji vynásobí posloupnost různě velikých kvaternionových matic. Násobení kvaternionových matic je analogické běžnému násobení matic. Uvědomte si však, že násobení matic je asociativní. To znamená, že A×B×C = (A×B)×C = A×(B×C), kde A,B,C jsou matice. Výpočetní složitost násobení posloupnosti matic se tedy může lišit v závislosti na rozměrech jednotlivých matic a jejich uzávorkování.
Vstup:
Ve vstupním souboru je na prvním řádku uveden počet matic, které chceme vynásobit. Další řádky obsahují vždy specifikaci kvaternionové matice. První řádek obsahuje počet řádků matice a na druhém řádku je počet sloupců matice. Další řádky obsahují vlastní matici tak, že jeden řádek vstupu je jeden řádek matice. Čísla na řádcích jsou oddělena mezerami. Čtveřice čísel představuje vždy jeden kvaternion. Každá složka kvaternionu je vždy celé číslo v rozsahu ‒2 147 483 648 až 2 147 483 647 Jednotlivé matice jsou zadány korektně (tj. matice jsou mezi sebou rozměrově kompatibilní tak, aby se daly vzájemně násobit). Navíc můžete předpokládat, že při násobení matic nedojde nikdy k přetečení.Výstup:
První řádek obsahuje počet řádků výsledné matice a na druhém řádku je počet sloupců výsledné matice. Další řádky obsahují vlastní matici tak, že jeden řádek vstupu je jeden řádek matice. Čísla na řádcích jsou oddělena mezerami. Čtveřice čísel představuje vždy jeden kvaternion. Výsledná matice odpovídá matici, která by vznikla postupným násobením matic na vstupu.Vstup:
2 2 3 9 9 -7 3 -9 0 -9 -1 -2 0 2 7 -3 1 -1 2 -2 -6 8 1 0 0 -4 -4 3 2 3 -4 -8 -7 -3 6 4 -6 -4 5 8 -4 8 4 7 -4 -5 -1 -3 -7 -5 5 -10 -8
Výstup:
2 2 197 72 -94 -88 38 108 35 50 -61 28 -23 -53 -97 -126 39 4