Rezolvarea ecuatiilor diofantice Categoria: Referat Informatica
Descriere: |
|
||
|
|
|||
|
1 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 <stdio.h> #include <conio.h> #include <math.h> 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; } 1 m=a;n=b; if (!(a*b)) if (!a) if (!b) { //0=c if (!c) printf("x,yZ\n"); else stop(); return 0; } else { // by=c if (c%b) stop(); else { printf("xZ\n"); printf("y=%ld\n",c/b); } return 0; } else { //ax=c if (c%a) stop(); else {printf("x=%ld\n",c/a); printf("yZ\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*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 (m<n) m=m+n-(n=m); } n=v[nr]; get_mn(m,n,nr); if (_a<_b) m=m+n-(n=m); //in functie de fractia de aproximare corectez rezultatul if (a*b>0) 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=%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'); } |
|||
| Referat oferit de www.ReferateOk.ro | |||
Varianta Printabila 
Free Download Referat PDF
Free Download Referat Word |
Home : Despre Noi : Contact : Parteneri |  |
