Accueil > > > RECHERCHE DES COEFFICIENTS DE BÉZOUT
RECHERCHE DES COEFFICIENTS DE BÉZOUT
Information sur la source
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
- #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;
- }
#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;
}
Historique
- 19 juin 2008 21:01:08 :
- J'ai utilisé le modulo à la place du calcul de la partie entiere... J'avais betement oublié l'usage du modulo % qui donne le reste de la division euclidienne !
Sources du même auteur
Sources de la même categorie
Commentaires et avis
Discussions en rapport avec ce code source dans le forum
Probleme sur un programme qui calcule un pgcd [ par El loco ]
Voila j ai un probleme sur le programme suivant, il marche correctement avec une grande serie de nombres mais quand je tape 15 et 32 il me donne un pg
Format de données [ par leskritiques ]
Voici le programme que je veux modofier :#include "chaine.h"#include "entreeSortie.h"#include "chaine.cpp"#include "entreeSortie.cpp"int pgcd (const i
PGCD? [ par bethoring ]
Tout d'abord bonsoir, je voulais savoir si dans math.h yavé une fonction pour faire un pgcd ( jai regarder dedans et il me semble pas menfin on sai ja
algorithme d'euclide [ par dOsSpr0uTosS ]
salut à tous, je debute en C++(mais alors vraiment c'est à dire que j'ai commencer y'a une semaine et j'ai pas appris grand chose ...) et donc pour m'
PROGRAMME en lige de commande C++ ( ou C... ) [ par tekila_bandita ]
Bonjourje pense connaitre la reponse, mais existe-t-il un moyen de faire des programmes en lignes de commandes du style foncion?? Quand je dis fonctio
calcule de coefficients de corrélation et corélation partielle [ par mohamedabid ]
mohamedabidBonjours Je cherche une implémentation sur java ou c++ des fonctions de corrélations d'une série temporelleExiste-il une fonction prédéfini
Programmation langage C [ par Ligorin ]
Bonjour, je souhaiterai avoir votre aide,en langage C ,sur le problème de monnaie,en générale. Soit a+4b+6c=8. Objectif : Min a+b+c La solution e
pgcd [ par cherif2009 ]
salut j'essais de faire un programme de calcul de pgcd avec la soustraction mais il y a un truc qui cloche quand j'essais de compiler j'aimerai un pe
pgcd [ par cherif2009 ]
excusez moi voici le code #include #include #include void pgcd(); main() { pgcd(); } void pgcd() { int a,b,pg; printf("enter le premier entier"); scan
|
Derniers Blogs
ETENDRE LE TEAM WEB ACCESS DE TFS 2012 - STEP 0ETENDRE LE TEAM WEB ACCESS DE TFS 2012 - STEP 0 par Philess
L'extensibilité du Team Web Access
Le Web Access (site d'équipe) de Team Foundation Server a été complètement réécrit dans la version 2012 avec pas moins de 400.000 lignes de JavaScript. Ce nouveau modèle a été pensé pour offrir de grandes...
Cliquez pour lire la suite de l'article par Philess SIMULER FACILEMENT L'ENVOI DE MAILSIMULER FACILEMENT L'ENVOI DE MAIL par JeremyJeanson
il m'a été demandé, à plusieurs reprises, comment je faisais pour simuler l'envoi de mail lors de mes démos de Workflow Foundation. Ma solution est plutôt simple : j'utilise la configuration par défaut du SmtpClient et j'oriente les mails vers un dossier ...
Cliquez pour lire la suite de l'article par JeremyJeanson VOTEZ POUR LE TOP 10 DES INFLUENCEURS SHAREPOINT FRANCOPHONES !VOTEZ POUR LE TOP 10 DES INFLUENCEURS SHAREPOINT FRANCOPHONES ! par Patrick Guimonet
Si ce n'est déjà fait (comme plus de 600 personnes déjà), il est encore temps de voter pour le concours TOP 10 des influenceurs SharePoint francophones ! Il est organisé par harmon.ie et accessible ici : http://harmon.ie/top-...
Cliquez pour lire la suite de l'article par Patrick Guimonet [CONF'SHAREPOINT] DERNIER RAPPEL ! :-)[CONF'SHAREPOINT] DERNIER RAPPEL ! :-) par Patrick Guimonet
La Conf'SharePoint en chiffres c'est : 3 jours de SharePoint ! 4 parcours et 60 sessions 17 partenaires représentant toutes les fac...
Cliquez pour lire la suite de l'article par Patrick Guimonet
Forum
PB PACMAN C++PB PACMAN C++ par garfield95
Cliquez pour lire la suite par garfield95
Logiciels
Easy-Planning (4.5.0.11)EASY-PLANNING (4.5.0.11)Easy-Planning permet de créer des plannings sous la représentation de diagrammes et est adapté a... Cliquez pour télécharger Easy-Planning CVEasy (3.1.0.51)CVEASY (3.1.0.51)PHMSD-CVEasy est un logiciel d'aide à la rédaction de CV d'une simplicité déconcertante.
PHMSD-C... Cliquez pour télécharger CVEasy LettresFaciles 2011 (8.6.0.31)LETTRESFACILES 2011 (8.6.0.31)LettresFaciles est un logiciel facilitant la création et la rédaction de lettres types.
Son inte... Cliquez pour télécharger LettresFaciles 2011 sDEVIS-FACTURES vlPRO (8.4.2.62)SDEVIS-FACTURES VLPRO (8.4.2.62)sDEVIS-FACTURES vlPRO a été mis au point pour les particuliers, créateurs, entrepreneurs, artisa... Cliquez pour télécharger sDEVIS-FACTURES vlPRO Devis-Factures PHMSD (2.1.0.11)DEVIS-FACTURES PHMSD (2.1.0.11)Configuration minimale
Nécessite Windows™ 2000, XP, Windows 7, 8, Vista (Service Pack à... Cliquez pour télécharger Devis-Factures PHMSD
|