concursul liis/campion
Scris: 16 Dec 2003, 16:37problema algebra runda1
La prima vedere problema admite o rezolvare simplista, ca la clasa VII.
Iata cum:
Pas1.Se determina minimul diferit de 0 din matrice, fie acesta x0,se determina urmatorul minim nenul nesituat pe linia si coloana primului, se determina al treilea minim nenul nesituat pe liniile sau coloanele selectate pana acum s.a.m.d.
Producem astfel o valoare x0 si o matrice permutare A.
Pas2.Scadem din matricea initiala x0A.
Pas3.Daca toate elementele matricii curente sunt 0 stop, altfel mergi la pas1.
Deoarece pasul 1 se executa in n^3, si se obtine o valoare nula, rezulta ca in cel mult n^2 pasi1 matricea devine nula.
Asadar algoritmul are complexitae n^5.
Ce nu e corect?
Cumva se blocheaza in cadrul pasului 1?
Daca e corect atunci este o rezolvare la fel de rapida ca solutia comisiei.
Radu Visinescu
La prima vedere problema admite o rezolvare simplista, ca la clasa VII.
Iata cum:
Pas1.Se determina minimul diferit de 0 din matrice, fie acesta x0,se determina urmatorul minim nenul nesituat pe linia si coloana primului, se determina al treilea minim nenul nesituat pe liniile sau coloanele selectate pana acum s.a.m.d.
Producem astfel o valoare x0 si o matrice permutare A.
Pas2.Scadem din matricea initiala x0A.
Pas3.Daca toate elementele matricii curente sunt 0 stop, altfel mergi la pas1.
Deoarece pasul 1 se executa in n^3, si se obtine o valoare nula, rezulta ca in cel mult n^2 pasi1 matricea devine nula.
Asadar algoritmul are complexitae n^5.
Ce nu e corect?
Cumva se blocheaza in cadrul pasului 1?
Daca e corect atunci este o rezolvare la fel de rapida ca solutia comisiei.
Radu Visinescu