5. Potyczki Informatyczne Nowej Generacji

Zadanie eliminacyjne w konkursie WIPING5 organizowanym przez
Wydział Informatyki Zachodniopomorskiego Uniwersytetu Technologicznego w Szczecinie

Odwracanie

Pewnie nie raz spotkałeś/spotkałaś się już z zagadnieniem odwracania macierzy kwadratowej. Twoim zadaniem będzie napisanie programu, który będzie wykonywał to zadanie według niżej określonych zasad.

Aby wyznaczyć macierz odwrotną do podanej macierzy A, należy dołączyć do niej prawostronnie macierz jednostkową, a następnie, wykonując szereg operacji na tak złączonej macierzy, należy doprowadzić ją do postaci, w której z lewej strony uzyskamy macierz jednostkową:

[A | I] → przekształcenia → [I | A^-1]

Każda z kolumn jest kolejno doprowadzana do preferowanej formy (tj. jedynka na głównej przekątnej, pod i nad przekątną zera) zgodnie z dwoma krokami:

1. aby uzyskać jedynkę na przekątnej, musisz wykonać dzielenie danego wiersza przez stałą;
2. aby wyzerować element z danego wiersza, należy odjąć od niego wielokrotność wiersza, w którym w kroku 1) została ustawiona jedynka na przekątnej.

Uwaga! Wszystkie dozwolone operacje, jakie możesz wykonywać, zawsze dotyczą całych wierszy!

Wejś›cie 

Kolejno:

• wiersz zawierający całkowitą wartość n – wymiar macierzy (2 <= n <= 10)
• n wierszy po n wartości zmiennoprzecinkowych, rozdzielonych spacjami, reprezentujących kolejne elementy macierzy

Wyjś›cie

• nieznana z góry liczba wierszy tekstu, reprezentujących kolejne etapy realizacji algorytmu: macierz wstępna – po dołączeniu macierzy jednostkowej, macierz po przekształceniu pierwszej kolumny, …, macierz po przekształceniu n-tej kolumny;
• wypisane liczby mają mieć stałą długość 8 znaków, z czego 4 przeznaczone są na część ułamkową;
• liczby w wierszu oddzielone są dodatkowo spacją;
• na końcu wiersza po ostatniej liczbie znajduje się wyłącznie znak nowej linii;
• macierze składające się na macierz rozszerzoną są rozdzielone znakiem belki (ASCII 124);
• ponadto, jeśli moduł wypisywanej liczby jest mniejszy niż 10^-14, to należy wypisać 0;
• kolejne macierze rozdziela pusty wiersz.

Przykł‚ad

Wejś›cie: 

3
1 2 -1
2 3 -2
1 0 1

Wyjście:

  1.0000   2.0000  -1.0000|  1.0000   0.0000   0.0000
  2.0000   3.0000  -2.0000|  0.0000   1.0000   0.0000
  1.0000   0.0000   1.0000|  0.0000   0.0000   1.0000

  1.0000   2.0000  -1.0000|  1.0000   0.0000   0.0000
  0.0000  -1.0000   0.0000| -2.0000   1.0000   0.0000
  0.0000  -2.0000   2.0000| -1.0000   0.0000   1.0000

  1.0000   0.0000  -1.0000| -3.0000   2.0000   0.0000
  0.0000   1.0000   0.0000|  2.0000  -1.0000   0.0000
  0.0000   0.0000   2.0000|  3.0000  -2.0000   1.0000

  1.0000   0.0000   0.0000| -1.5000   1.0000   0.5000
  0.0000   1.0000   0.0000|  2.0000  -1.0000   0.0000
  0.0000   0.0000   1.0000|  1.5000  -1.0000   0.5000

Wyjaśnienie: 

• pierwsza macierz – złączenie macierzy wejściowej z macierzą jednostkową
• druga macierz – ustawienie jedynki na przekątnej w 1. kolumnie (w tym wypadku poprzez podzielenie przez 1 - element na przekątnej), ustawienie zer pod przekątną w 1. kolumnie poprzez operacje: w₂ = w₂ – 2*w₁; w₃ = w₃ – 1*w₁ (wykorzystanie pierwszego wiersza do wyzerowania elementów);
• trzecia macierz – operacje na kolumnie numer 2
• ...