QReferate - referate pentru educatia ta.
Referatele noastre - sursa ta de inspiratie! Referate oferite gratuit, lucrari si proiecte cu imagini si grafice. Fiecare referat, proiect sau comentariu il poti downloada rapid si il poti folosi pentru temele tale de acasa.



AdministratieAlimentatieArta culturaAsistenta socialaAstronomie
BiologieChimieComunicareConstructiiCosmetica
DesenDiverseDreptEconomieEngleza
FilozofieFizicaFrancezaGeografieGermana
InformaticaIstorieLatinaManagementMarketing
MatematicaMecanicaMedicinaPedagogiePsihologie
RomanaStiinte politiceTransporturiTurism
Esti aici: Qreferat » Referate informatica

Rezolvarea ecuatiilor diofantice





Orice congruenta ax1+c0 (mod b) se poate scrie ca o ecuatie ax1+bx2+c=0 (in care a 0), b1 si c, x1, x2 sunt numere intregi. Daca a, b, c sunt numere intregi date si x1 si x2 sunt considerate necunoscute, problema se reduce la gasirea solutiilor intregi ale unei ecuatii liniare cu coeficienti intregi. Daca f(x1, . , xn) este un polinom in x1, . , xn cu coeficienti intregi, atunci ecuatia f(x1, . , xn) = A se numeste diofantica daca solutiile ei sunt numere intregi. Denumirea acestor ecuatii deriva de la numele matematicianului grec Diofantos din Alexandria. Daca o astfel de ecuatie admite solutii, atunci ea admite o infinitate de n-upluri care o satisfac.



In continuare se va trata cazul n=2: ax+by=c

Daca a si b sunt numere prime intre ele si x0, y0 constituie o solutie pentru ax+by=c, atunci totalitatea solutiilor se poate reprezenta sub forma: x= x0+bt, y= y0 -at, unde t este un numar intreg oarecare. O solutie a ecuatiei se poate obtine cu ajutorul penultimei fractii de aproximare pentru reprezentarea sub forma de fractie continua a lui a/b. Considerand ca penultima fractie este m/n, x0=nc, y0=-mc.

Exemplu:

Fie ecuatia: 43x+19y=2.

Fractiile de aproximare ale lui 43/19 sunt: 7/3, 9/4, 43/19.


Din fractia 9/4 se obtine x0=4*2=8, y0=-9*2=-18. Astfel, solutia generala se poate scrie de forma: x=8+19t si y=-18-43t, unde t este un numar oarecare.

Implementare

Algoritmul de mai sus este valabil, dupa cum am precizat, in cazul cand cele 2 numere a si b sunt prime intre ele. Daca dorim rezolvarea unei ecuatii in care cele 2 numere nu sunt neaparat prime intre ele, se poate proceda in felul urmator: se calculeaza cel mai mare divizor comun al lor (sigur este diferit de 1), iar apoi se evalueaza daca ecuatie poate sau nu avea solutii, in functie de valoarea lui c. Daca c este divizibil cu cmmdc-ul celor 2 numere, atunci se simplifica intreaga ecuatie cu cmmdc si problema se reduce la cea prezentata mai sus. Daca c nu se imparte exact la cmmdc, atunci putem spune ca ecuatia nu are solutii intregi.



Pe langa aceasta, intervin o serie de cazuri critice in care algoritmul de mai sus nu poate fi aplicat, cum ar fi de exemplu cazurile in care nu exista penultima fractie. Dar se poate calcula solutia si in aceste cazuri:

. a=0, b=0
In acest caz solutia depinde valoarea lui c:
. c=0 => x si y poate fi orice numar intreg
. c  0 => nu exista solutii
. a=0, b 0
Ecuatia devine: by=c. Deci y se poate calcula, tinand insa cont ca vorbim numai de numere intregi.
. a0, b= 0
Analog cu cazul anterior.

Daca unul dintre numerele a sau b are valoarea 1 nu se mai poate vorbi de penultima fractie de aproximare, deci si aceste cazuri trebuie tratate separat.

O alta observatie este aceea ca fractia de aproximare (m/n) aproximeaza fractia (a/b) in plus sau in minus. De aceea in la sfarsit trebuie sa corectez rezultatul in functie de aceasta, tinand seama si de semnul fractiei a/b.
Sursa programului



Descarca referat

E posibil sa te intereseze alte referate despre:




Copyright © 2024 - Toate drepturile rezervate QReferat.com Folositi referatele, proiectele sau lucrarile afisate ca sursa de inspiratie. Va recomandam sa nu copiati textul, ci sa compuneti propriul referat pe baza referatelor de pe site.
{ Home } { Contact } { Termeni si conditii }