PC Tema 3: Diferență între versiuni

De la WikiLabs
(Pagină nouă: 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ă. = Introduce...)
 
(Observații)
Linia 51: Linia 51:
  
 
</li>
 
</li>
 +
<li>Nu uitați de condiția de oprire pentru funcțiile recursive<li>
 
</ol>
 
</ol>
  

Versiunea de la data 9 decembrie 2015 14:46

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ă: determinantul unei metrici pătratice de orice dimensiune rămâne constant la operații liniare între două linii sau coloane. Astfel, putem face următoarele operații, fără a influența valoarea determinantului:

  • înmulțirea unei linii sau coloane cu o constantă;
  • adunarea sau scăderea a două linii sau două coloane între ele.

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 matrici.

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.4 -4.3  1.2
0.3  1.5  3.1
0    0.1  0.2

Date de ieșire

O singură valoare de tip double, reprezentând valoarea determinantului matricei.

Exemplu (pentru intrarea de mai sus)

0.28

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. 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. 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ă. Rezultatul va fi că pe prima linie din matrice va fi aceeași valoare.
  2. 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.
  3. Valoarea determinantului este egală cu valoarea din stânga sus, înmulțită cu valoarea determinantului submatricei de la (1,1) la (n-1, n-1).

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:

  1. 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 23 decembrie, ora 23:55. Apoi, pentru fiecare zi întârziere, veți fi penalizați cu un punct.