Recherche des coefficients de bézout

Télécharger le projet
Commenter

Description

C'est un tout petit programme avec une fonction récursive qui permet de rechercher les coefficients de Bézout.
Le théorème de Bézout dit que, si d=pgcd(a;b), alors il existe deux entiers relatifs u et v tels que a*u+b*v=d.
Par exemple, pgcd(45;8)=1, donc il existe deux entiers relatifs u et v tels que 45*u+8*v=1. Le programme en trouve deux :
u=-3 et v=17.
Il en existe d'autres, mais le programme détermine ceux qu'on obtient en remontant l'algorithme d'euclide.

Source / Exemple : 


#include <iostream>

void Bezout(int rkm2,int rkm1,int ukm1=0,int vkm1=1,int ukm2=1,int vkm2=0){
/*r(k-4)=r(k-3)*q(k-2)+r(k-2) <=> r(k-2)=a*u(k-2)+b*v(k-2)


     
  • r(k-3)=r(k-2)*q(k-1)+r(k-1) <=> r(k-1)=a*u(k-1)+b*v(k-1)

    •  
  • r(k-2)=r(k-1)*q(k)+r(k)     <=> r(k)=a*u(k)+b*v(k) avec u(k)=u(k-2)-qk*u(k-1) et v(k)=v(k-2)-qk*v(k-1)*/

    int rk=rkm2%rkm1;
    int qk=(rkm2-rk)/rkm1;
    if(rk==0) 
        std::cout<<rkm1<<"=a*"<<ukm1<<"+b*"<<vkm1<<std::endl;
    else 
        Bezout(rkm1,rk,ukm2-qk*ukm1,vkm2-qk*vkm1,ukm1,vkm1);
    return;
}

int main(int argc,char* argv[]){
    int a,b;
    std::cout<<"a=";std::cin>>a;
    std::cout<<"b=";std::cin>>b;
    if(a<=0 || b<=0)
        std::cout<<"On suppose a et b strictement positifs."<<std::endl;
    else
        Bezout(a,b);
    return 0;
}
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (cs_BCedric)