Théorème chinois
Contenu du snippet
résolution d'un systéme de congruence à l'aide du théoreme chinois
je suis encore débutant et vos suggestions seraient toujours les bienvenus
Source / Exemple :
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define val 100
long pgdc (long a,long b);
long inverse (long a1, long b1);
/*-----program principal------*/
int main()
{ void entete(); //declaration de la fction entete
int tab_a[val],tab_n[val],tab_q[val],tab_qq[val];
int nbr_eq,i,j,k;
long n=1,solution=0;
clrscr();
entete(); //appel de la fction entete
do{
printf("donnez le nombre d'equations qu'il ya dans votre systeme "); scanf("%d",&nbr_eq);
}while(nbr_eq<1 || nbr_eq>val);
/*------------saisie des ai et ni--------------*/
for(i=0;i<nbr_eq;i++)
{
printf("saisissez l'element a%d de l'equation%d ",i+1,i+1);
scanf("%d",&tab_a[i]);
}
printf("\n\tsaisie des modules parielles\n");
for(i=0;i<nbr_eq;i++)
{
printf("saisissez l'element n%d de l'equation%d ",i+1,i+1);
scanf("%d",&tab_n[i]);
}
/*--------------test si les ni sont premiers deux a deux------*/
for(i=0;i<nbr_eq-1;i++)
{
for(j=i+1;j<nbr_eq;j++)
{ if(pgdc(tab_n[i],tab_n[j])!=1)
{ cprintf("les elements %d et %d ne sont pas premiers ntre eux",tab_n[i],tab_n[j]);
printf("\nreprenez la saisie des ni\n");
for(k=0;k<nbr_eq;k++)
{
printf("saisissez l'element n%d de l'equation%d ",k+1,k+1);
scanf("%d",&tab_n[k]);
}
}
}
}
clrscr();entete();textbackground(BLACK);
/*------------affichage du systeme--------------*/
printf("\nle systeme saisi est");
for(i=0;i<nbr_eq;i++)
{textcolor(CYAN);printf("\n");
cprintf(" x=%d mod %d",tab_a[i],tab_n[i]);
}
/*-----------calcul du produit des ni-----------*/
for(i=0;i<nbr_eq;i++)
n*=tab_n[i];
printf("\nle n est %d",n);
//calcul et affichage des qi et qqi
printf("\nles qi sont: ");
for(i=0;i<nbr_eq;i++)
{
tab_q[i]=n/tab_n[i];
printf("q%d=%d\t",i+1,tab_q[i]);
}
printf("\nles inverses respectives des qi dans Zi sont: ");
for(i=0;i<nbr_eq;i++)
{
tab_qq[i]=inverse(tab_q[i],tab_n[i]);
printf("q'%d=%d\t",i+1,tab_qq[i]);
}
/*--------calcul solution finale-------------*/
for(i=0;i<nbr_eq;i++)
solution+=((tab_a[i])*(tab_q[i])*(tab_qq[i]));
solution%=n;
printf("\n\n"); textcolor(RED);textbackground(YELLOW);
cprintf("la solution de cette equation est %d",solution);
gotoxy(1,49);textcolor(CYAN);cprintf("taper une touche pour sortir...");
getch();
return 0;
}
/*------------definition de la fction inverse--------*/
long inverse (long a, long b)
{
long Ro=a,R1=b,q,r,i=0,Vo=0,V1=1,Uo=1,U1=0,V2,U2;
long vect_u[50];
do
{
q=Ro/R1; r=Ro-R1*q; Ro=R1; R1=r;
i++;
U2=Uo-q*U1; V2=Vo-q*V1;
Uo=U1; U1=U2;
Vo=V1; V1=V2;
vect_u[i]=U2;
}
while(r!=0);
if(vect_u[i-1]>0) return vect_u[i-1]%b;
else return b-(-vect_u[i-1])%b;
}
/*-----------definition de la fction pgdc--------------*/
long pgdc (long a,long b)
{long r0,r1,q1,i;
if (a==0 ) return b;
if (b==0 ) return a;
if (a>b)
{r0=a; r1=b;}
else {r0=b; r1=a;}
q1=r0/r1;
i=r0-q1*r1;
if (i==0)
return r1;
else
{
do
{
r0=r1;
r1=i;
q1=r0/r1;
i=r0-q1*r1;
}while (i!=0);
return r1;
}
}
/*-----------definition de l'entete-----------*/
void entete ()
{ int a,b;
textcolor(RED);
gotoxy(10,2);cprintf("++-------------------------------------------------------------++");
gotoxy(10,3);cprintf("|+-------------------------------------------------------------+|"); a=wherex(); b=wherey();
gotoxy(10,4);cprintf("||"); gotoxy(10,5);cprintf("||"); gotoxy(a-2,b+2);cprintf("||");gotoxy(a-2,b+1);cprintf("||");
gotoxy(10,6);cprintf("|+-------------------------------------------------------------+|");
gotoxy(10,7);cprintf("+--------------------------------------------------------------++");
textbackground(WHITE);
textcolor(BLUE);gotoxy(15,4);
cprintf("CE PROGRAMME RESOUD UN SYSTEME DE CONGRUENCE D'ORDRE N"); gotoxy(23,5);
cprintf(" A L'AIDE DU THEOREME CHINOIS"); gotoxy(2,9);
}
Conclusion :
je suis encore débutant et vos suggestions seraient toujours les bienvenus
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.