PC Tema 3

Multe aplicații foarte puternice din informatică, de la instrumente de simulare, până la algoritmi de bioinformatică se bazează pe noțiuni de algebră liniară.

Introducere

Să de amintim de la orele de algebră: pe determinantul unei matrice pătratice se pot face operați liniare între două linii sau coloane influentând valoarea determinantului astfel:

• înmulțirea unei linii sau coloane cu o constantă face și valoarea determinantul să se înmulțească cu aceeași constantă;
• adunarea sau scăderea a două linii sau două coloane între ele păstrează constantă valoarea determinantului.

Cerință

Dându-se un număr n întreg, în intervalul [2; 255], și o matrice pătratică de n x n valori raționale, să se scrie o funcție recursivă care să calculeze determinantul acestei matrice.

Date de intrare

Numărul n, valoare întreagă, în intervalul [2; 255] urmat de n * n numere de tip double, reprezentând conținutul matricei.

Exemplu

3
1 1 2
3 1 4
2 3 1

Date de ieșire

O singură valoare de tip double, reprezentând valoarea determinantului matricei, în format științific, litere mici și două zecimale precizie.

Exemplu (pentru intrarea de mai sus)

8.00e+00

Algoritm

Pașii pentru realizarea acestui algoritm, implică, pentru matricea de n x n, eliminarea prin operații liniare a elementelor de pe prima linie, lăsând o valoare nenulă doar pe prima poziție și memorând constantele cu care s-au înmulțit coloanele. Apoi, se apelează recursiv funcția de calcul al determinantului pentru o submatrice de n-1 x n-1. Fie coloanele matricei de n x n numerotate de la 0 la n-1.

1. Daca coloana de pe poziția 0 are pe prima linie 0, se caută prima coloană care are pe prima linie o valoare nenulă și se adună la coloana 0 (dacă nu există nici una, determinantul e 0).
2. Pentru coloanele de la 1 la n - 1, se înmulțește fiecare coloană cu valoarea din colțul din stânga sus și se împarte la primul element de pe coloană. Dacă coloana are deja 0 pe prima linie, ea nu se procesează. Produsul factorilor se memorează. Rezultatul va fi că pe prima linie din matrice va fi aceeași valoare.
3. Pentru coloanele de la 1 la n - 1 se scade coloana 0, astfel, se obține o matrice unde pe prima linie toatele elementele mai puțin primul sunt 0.
4. Valoarea determinantului este egală cu valoarea din stânga sus, împărțită la valoarea memorată, înmulțită cu valoarea determinantului submatricei de la (1,1) la (n-1, n-1).

Exemplu (pentru matricea de mai sus)

1. Pentru coloanele de la 1 la 2, se înmulțește fiecare coloană cu valoarea din colțul din stânga sus (1) și se împarte la primul element de pe coloană.

1 1 2     1 1*(1/1) 2*(1/2)                                              1 1 1
3 1 4 =>  3 1*(1/1) 4*(1/2) (se memorează factorii 1/1 * 1/2 = 0.5) =>   3 1 2
2 3 1     2 3*(1/1) 1*(1/2)                                              2 3 0.5

2. Pentru coloanele de la 1 la 2 se scade coloana 0.

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

3. Valoarea determinantului este colțul din stânga sus împărțit la produsul memorat, înmulțit cu determinantul submatricei următoare:

                         -2   -1
Det(m) = 1 / 0.5 *  Det(         ) = 8
                          1  -1.5

4. Dacă matricea e mai mare de 3 x 3, pentru calculul submatricei următoare, se folosește recursiv același algoritm.

Observații

1. Formatul textului de la ieșire trebuie să fie identic cu cel de la secțiunea "Date de ieșire" pentru a evita depunctarea de către programul de evaluare.
2. Atenție: Nu afișați în consolă nimic altceva decât se cere explicit în problemă. Mai concret, nu printați nimic înainte de citirea textului de la tastatură (ex: Introduceți textul: ).
3. Pentru a vă ușura introducerea datelor, puteți scrie matricea de test într-un fișier, în formatul specificat la #Date de intrare, și la execuție puteți redirecta stream-ul standard de intrare să citească din fișier, în loc de tastatură:

   ./exec <inputFile.txt
   

   Unde inputFile.txt este numele fișierului ce conține matricea de intrare, iar exec este numele executabilului vostru.

4. Nu uitați de condiția de oprire pentru funcțiile recursive

Restricții

Obligatoriu se va implementa următoarea funcție: double computeDeterminant(double matrix[][], unsigned char start, unsigned char end); - unde matrix reprezinta matricea, start reprezintă coordonata punctului din stânga sus din matrice de unde începe calculul determinantului, iar end va fi colțul din dreapta jos unde se termină calculul determinantului și care va fi în permanență n-1; această funcție se va apela prima oară cu argumentele matrix, 0, n-1.

Livrabile și modalitate de predare

Predarea se face pe platforma Web-Cat și constă în upload-ul unui singur fișier sursă C care să implementeze funcționalitatea cerută.

Notare

Pentru această temă se pot acorda 10 puncte:

• 7 puncte pentru comportamentul aplicației, care se acordă automat de către platforma de testare, imediat după predare, în funcție de calitatea temei;
• 3 puncte pentru stilul de scriere a programului, alinierea codului, nume lizibile de variabile, etc., care se acordă ulterior de către un cadru didactic.

Atenție: Pentru această temă se pot SCĂDEA 11 puncte, dacă aceasta se dovedește că este copiată.

Termen limită

Termenul limită pentru depunerea temei este 31 decembrie, ora 23:55. Apoi, pentru fiecare zi întârziere, veți fi penalizați cu un punct.