Recherche des coefficients de bézout

Soyez le premier à donner votre avis sur cette source.

Vue 11 911 fois - Téléchargée 408 fois

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; }

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
100
Date d'inscription
mardi 29 novembre 2005
Statut
Membre
Dernière intervention
8 mai 2009

Il est aussi en Python et en code casio 35+ pour ceux qui sont intéressés...
http://www.pythonfrance.com/codes/BEZOUT-ALGORITHME-EUCLIDE-ETENDU_45696.aspx
Messages postés
341
Date d'inscription
jeudi 3 avril 2003
Statut
Membre
Dernière intervention
17 juin 2008
2
Il y a déjà une source avec plein de commentaires sur comment le coder plus proprement:
http://www.cppfrance.com/codes/ALGORITHME-EUCLIDE-ETENDU_36400.aspx
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
41
salut

http://www.codyx.org/snippet_coefs-bezout-equations-diophantiennes_607.aspx

c'est plus un snippet qu'une source...

Sinon, tu devrais renvoyer les coeficients, plutot que de les afficher, car la, si tu dois faire une autre fonction qui utilise ces coefs, bah tu ne peux pas.

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.