Referat Rezolvarea Ecuatiilor Diofantice.rtf

Mai jos puteti citi fragmente din Referat Rezolvarea Ecuatiilor Diofantice.rtf si de asemenea puteti face Download Referat Rezolvarea ecuatiilor diofantice.rtf

Citeste fragmente din Referat Rezolvarea Ecuatiilor Diofantice.rtf

Rezolvarea ecuaюiilor diofantice Orice congruenюг ax1+c0 (mod b) se poate scrie ca o ecuaюie ax1+bx2+c=0 (оn care a 0), b1 є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 gгsirea soluюiilor оntregi ale unei ecuaюii liniare cu coeficienюi оntregi. Daca f(x1,…, xn) este un polinom оn x1,…, xn cu coeficienюi оntregi, atunci ecuaюia f(x1,…, xn) = A se numeєte diofanticг dacг soluюiile ei sunt numere оntregi. Denumirea acestor ecuaюii derivг de la numele matematicianului grec Diofantos din Alexandria. Dacг o astfel de ecuaюie admite soluюii, 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 soluюie pentru ax+by=c, atunci totalitatea soluюiilor se poate reprezenta sub forma: x= x0+bt, y= y0 –at, unde t este un numгr оntreg oarecare. O soluюie a ecuaюiei se poate obюine cu ajutorul penultimei fracюii de aproximare pentru reprezentarea sub formг de fracюie continuг a lui a/b. Considerвnd cг penultima fracюie este m/n, x0=nc, y0=-mc. Exemplu: Fie ecuaюia: 43x+19y=2. Fracюiile de aproximare ale lui 43/19 sunt: 7/3, 9/4, 43/19. Din fracюia 9/4 se obюine x0=4*2=8, y0=-9*2=-18. Astfel, soluюia generalг se poate scrie de forma: x=8+19t єi y=-18-43t, unde t este un numгr oarecare. Implementare Algoritmul de mai sus este valabil, dupг cum am precizat, оn cazul cвnd cele 2 numere a єi b sunt prime оntre ele. Dacг dorim rezolvarea unei ecuaюii оn care cele 2 numere nu sunt neapгrat prime оntre ele, se poate proceda оn felul urmгtor: se calculeazг cel mai mare divizor comun al lor (sigur este diferit de 1), iar apoi se evalueazг dacг ecuaюie poate sau nu avea soluюii, оn funcюie de valoarea lui c. Dacг c este divizibil cu cmmdc-ul celor 2 numere, atunci se simplificг оntreaga ecuaюie cu cmmdc єi problema se reduce la cea prezentatг mai sus. Dacг c nu se оmparte exact la cmmdc, atunci putem spune cг ecuaюia nu are soluюii оntregi. Pe lвngг 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 fracюie. Dar se poate calcula soluюia єi оn aceste cazuri: · a=0, b=0 Оn acest caz soluюia depinde valoarea lui c: § c=0 => x єi y poate fi orice numгr оntreg § c 0 => nu existг soluюii · a=0, b 0 Ecuaюia devine: by=c. Deci y se poate calcula, юinвnd оnsг cont cг vorbim numai de numere оntregi. · a0, b= 0 Analog cu cazul anterior. Dacг unul dintre numerele a sau b are valoarea 1 nu se mai poate vorbi de penultima fracюie de aproximare, deci єi aceste cazuri trebuie tratate separat. O altг observaюie este aceea cг fracюia de aproximare (m/n) aproximeazг fracюia (a/b) оn plus sau оn minus. De aceea оn la sfвrєit trebuie sг corectez rezultatul оn funcюie de aceasta, юinвnd seama єi de semnul fracюiei 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,yZn"); else stop(); return 0; else // by=c if (c%b) stop(); else printf("xZn"); printf("y=%ldn",c/b); return 0; else //ax=c if (c%a) stop(); else printf("x=%ldn",c/a); printf("yZn"); 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*xy=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,cоZ"); 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=%ldtn",n1); else printf("x=%stn",n1<0?"-":""); else if (labs(n1)!=1) printf("x=%ld%+ldtn",x0,n1); else printf("x=%ld%stn",x0,n1<0?"-":""); if (!y0) if (labs(n2)!=1) printf("y=%ldtn",n2); else printf("y=%stn",n2<0?"-":""); else if (labs(n2)!=1) printf("y=%ld%+ldtn",y0,n2); else printf("y=%ld%stn",y0,n2<0?"-":""); printf("unde t este un numar intregn"); puts("Apasati o tasta (x pentru a termina)..."); c=getch(); while (c!= x );