Referat REZOLVAREA ECUATIILOR DIOFANTICE

Incarcat la data: 19 Septembrie 2007

Autor: Iulia Andreea

Pret: 50 credite

Rezolvarea ecuaiilor diofantice Orice congruen ax1+c?0 (mod b) se poate scrie ca o ecuaie ax1+bx2+c=0 (n care a? 0), b?1 i c, x1, x2 sunt numere ntregi. Dac a, b, c sunt numere ntregi date i x1 i x2 sunt considerate necunoscute, problema se reduce la gsirea soluiilor ntregi ale unei ecuaii liniare cu coeficieni ntregi. Daca f(x1,, xn) este un polinom n x1,, xn cu coeficieni ntregi, atunci ecuaia f(x1,, xn) = A se numete diofantic dac soluiile ei sunt numere ntregi. Denumirea acestor ecuaii deriv de la numele matematicianului grec Diofantos din Alexandria. Dac o astfel de ecuaie admite soluii, atunci ea admite o infinitate de n-upluri care o satisfac. n continuare se va trata cazul n=2: ax+by=c Dac a i b sunt numere prime ntre ele i x0, y0 constituie o soluie pentru ax+by=c, atunci totalitatea soluiilor se poate reprezenta sub forma: x= x0+bt, y= y0 at, unde t este un numr ntreg oarecare. O soluie a ecuaiei se poate obine cu ajutorul penultimei fracii de aproximare pentru reprezentarea sub form de fracie continu a lui a/b. Considernd c penultima fracie este m/n, x0=nc, y0=-mc. Exemplu: Fie ecuaia: 43x+19y=2. Fraciile de aproximare ale lui 43/19 sunt: 7/3, 9/4, 43/19. Din fracia 9/4 se obine x0=4*2=8, y0=-9*2=-18. Astfel, soluia general se poate scrie de forma: x=8+19t i y=-18-43t, unde t este un numr oarecare. Implementare Algoritmul de mai sus este valabil, dup cum am precizat, n cazul cnd cele 2 numere a i b sunt prime ntre ele. Dac dorim rezolvarea unei ecuaii n care cele 2 numere nu sunt neaprat prime ntre ele, se poate proceda n felul urmtor: se calculeaz cel mai mare divizor comun al lor (sigur este diferit de 1), iar apoi se evalueaz dac ecuaie poate sau nu avea soluii, n funcie de valoarea lui c. Dac c este divizibil cu cmmdc-ul celor 2 numere, atunci se simplific ntreaga ecuaie cu cmmdc i problema se reduce la cea prezentat mai sus. Dac c nu se mparte exact la cmmdc, atunci putem spune c ecuaia nu are soluii ntregi. Pe lng aceasta, intervin o serie de cazuri critice n care algoritmul de mai sus nu poate fi aplicat, cum ar fi de exemplu cazurile n care nu exist penultima fracie. Dar se poate calcula soluia i n aceste cazuri: a=0, b=0 n acest caz soluia depinde valoarea lui c: c=0 => x i y poate fi orice numr ntreg c ? 0 => nu exist soluii a=0, b? 0 Ecuaia devine: by=c. Deci y se poate calcula, innd ns cont c vorbim numai de numere ntregi. a?0, b= 0 Analog cu cazul anterior. Dac unul dintre numerele a sau b are valoarea 1 nu se mai poate vorbi de penultima fracie de aproximare, deci i aceste cazuri trebuie tratate separat. O alt observaie este aceea c fracia de aproximare (m/n) aproximeaz fracia (a/b) n plus sau n minus. De aceea n la sfrit trebuie s corectez rezultatul n funcie de aceasta, innd seama i de semnul fraciei a/b. Sursa programului #include #include #include long int v[100]; //obtine penultima fractie de aproximare void get_mn(long int &a,long int &b,int k) { if (k>0) { long int aux=v[k-1]*b+a; a=b;b=aux; get_mn(a,b,k-1); } else a=a+b-(b=a); } long int _cmmdc(long int a,long int b) { while (a!=b) if (a>b) a-=b; else b-=a; return a; } void stop() { printf("Nu exista solutii...\n"); } int solutii(long int a,long int b,long int c, long int &x0,long int &n1,long int &y0,long int &n2) { long int m,n,cmmdc=1,_a,_b; int nr=-1; _a=labs(a);_b=labs(b); if ((_a>1)&&(_b>1)) cmmdc=_cmmdc(_a,_b); if (cmmdc!=1){ if (c%cmmdc) {stop();return 0;} else a/=cmmdc,b/=cmmdc,c/=cmmdc; } m=a;n=b; if (!(a*b)) if (!a) if (!b) { //0=c if (!c) printf("x,y?Z\n"); else stop(); return 0; } else { // by=c if (c%b) stop(); else { printf("x?Z\n"); printf("y=%ld\n",c/b); } return 0; } else { //ax=c if (c%a) stop(); else {printf("x=%ld\n",c/a); printf("y?Z\n"); } return 0; } if (labs(m)==1) { // inseamna ca este de forma ?x+b*y=c, deci nu exista // penultima fractie de aproximare x0=c*m;n1=-b*m; y0=0;n2=1; return 1; } else if (labs(n)==1) { // inseamna ca este de forma a*x?y=c, deci nu exista // penultima fractie de aproximare x0=0;n1=1; y0=c*n;n2=-a*n; return 1; } // m si n sunt diferite de 1, si diferite intre ele m=labs(m);n=labs(n); while (m!=1){ if (m>n){ v[++nr]=m/n; m-=m/n*n; } else if (m0) if (_a*n<_b*m) c=-c; if (a*b<0) if (_a*n>_b*m) c=-c; if (a<0) m=-m; if (b<0) n=-n; x0=n*c;n1=b; y0=-m*c;n2=-a; return 1; } void main(void) { long int a,b,c,x0,y0,n1,n2; do{ clrscr(); puts("Se rezolva ecuatia: ax+by=c, a,b,x,y,cZ"); printf("a=");scanf("%ld",&a);fflush(stdin); printf("b=");scanf("%ld",&b);fflush(stdin); printf("c=");scanf("%ld",&c);fflush(stdin); printf("----------------------------------------\n"); if (solutii(a,b,c,x0,n1,y0,n2)){ if (!x0) if (labs(n1)!=1) printf("x=%ldt\n",n1); else printf("x=%st\n",n1<0?"-":""); else if (labs(n1)!=1) printf("x=%ld%+ldt\n",x0,n1); else printf("x=%ld%st\n",x0,n1<0?"-":""); if (!y0) if (labs(n2)!=1) printf("y=%ldt\n",n2); else printf("y=%st\n",n2<0?"-":""); else if (labs(n2)!=1) printf("y=%ld%+ldt\n",y0,n2); else printf("y=%ld%st\n",y0,n2<0?"-":""); printf("unde t este un numar intreg\n");} puts("Apasati o tasta (x pentru a termina)..."); c=getch(); }while (c!='x');

Textul de mai sus reprezinta un extras din "Referat REZOLVAREA ECUATIILOR DIOFANTICE". Pentru versiunea completa a documentului apasa butonul Download si descarca fisierul pe calculatorul tau. Prin descarcarea prezentei lucrari stiintifice, orice utilizator al site-ului www.studentie.ro declara si garanteaza ca este de acord cu utilizarile permise ale acesteia, in conformitate cu prevederile legale ablicabile in domeniul proprietatii intelectuale si in domeniul educatiei din legislatia in vigoare.

In cazul in care intampini probleme la descarcarea fisierului sau documentul nu este nici pe departe ceea ce se doreste a fi te rugam sa ne anunti. Raporteaza o eroare

Important!

Referatele si lucrarile oferite de Studentie.ro au scop educativ si orientativ pentru cercetare academica.

Iti recomandam ca referatele pe care le downloadezi de pe site sa le utilizezi doar ca sursa de inspiratie sau ca resurse educationale pentru conceperea unui referat nou, propriu si original.