Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Idee de rezolvare:
- Ne bazăm pe teorema care permite calculul unui determinant de dimensiune mai mare decât 3x3 prin dezvoltare pe linie sau coloană. În cazul acestei implementări, am ales să fac dezvoltarea pe linie, plecând de la elementul cel mai apropiat de colțul dreapta-jos diferit de 0, de fiecare dată. Astfel, generez întâi zerourile pe coloana respectivă și modific și celelalte valori de pe coloane corespunzător, apoi calculez delta(l, c) ca matrix[l][c] * (-1)^(l + c), elimin din matrice linia si coloana de la care am pornit și reapelez functia det() * delta, pentru a continua calculul. Cazul cu rezolvare imediată este, aici, cel în care matricea este de 2x2 și calculul determinantului se reduce la o formulă.
- Pseudocod:
- def det(n, matrix):
- dacă n = 2 (cazul cu rezolvare imediată):
- returnăm matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0]
- inițializăm linia și coloana de la care vrem să pornim cu -1
- pentru fiecare linie (în sens invers):
- pentru fiecare coloană (în sens invers):
- dacă matrix[linie][coloană] e diferit de 0:
- reținem cele 2 coordonate și ieșim forțat din instrucțiunile repetitive
- dacă linia și coloana rămân -1:
- returnăm -1
- pentru fiecare coloană din matrice:
- dacă aceasta e diferită de cea aleasă anterior:
- calculăm coeficientul necesar reducerii elementelor de pe linie
- pentru fiecare linie din matrice:
- actualizăm corespunzător elementul de pe linia și coloana curentă
- calculăm delta
- eliminăm linia și coloana de la care am pornit, pe rând
- reducem dimensiunea matricei
- returnăm delta * det(n, matrix)
- Implementare Python: https://pastebin.com/bhLgExZ7
- Exemplu: https://pastebin.com/7wg5JqHg
Advertisement
Add Comment
Please, Sign In to add comment