begin process at 2012 02 13 12:00:50
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Maths

 > ALGORITHME DE BEZOUT : TROUVER U, V ET PGCD(A,B) TEL QUE U.A + V.B = PGCD(A,B)

ALGORITHME DE BEZOUT : TROUVER U, V ET PGCD(A,B) TEL QUE U.A + V.B = PGCD(A,B)


 Information sur la source

Note :
7,5 / 10 - par 4 personnes
7,50 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Catégorie :Maths Niveau :Débutant Date de création :08/02/2004 Date de mise à jour :08/02/2004 21:57:18 Vu :9 578
Auteur : Zeroc00l

Ecrire un message privé
Ce membre participe au partage de revenus publicitaires
Commentaire sur cette source (10)
Ajouter un commentaire et/ou une note

 Description

l'algo de Bézout renvoit des valeurs suivant ce principe :

Soit A et B entiers (positifs ou négatifs)
   Soit D leur PGCD

But de Bezout : Trouver U et V deux entiers (positifs ou négatifs) tel que :
   U*A + V*B = D

Je met cette source parce qu'en tapant "Bezout" dans le moteur de recherche de codes-sources, j'ai rien trouvé !

Source

  • ' Appel :
  • '
  • 'Dim A as integer, B as integer
  • 'Dim D as integer, U as integer, V as integer
  • ' A = Val(Text1.Text)
  • ' B = Val(Text2.Text)
  • 'Note : Il n'est pas nécessaire d'initialiser U et V à zéro avant l'appel.
  • 'Call Bezout(A, B, D, U, V)
  • 'Text3.Text = U
  • 'Text4.Text = V
  • 'Text5.Text = "PGCD( A , B ) = " & D
  • Private Sub Bezout(a As Integer, b As Integer,Byref d as integer, ByRef u As Integer, ByRef v As Integer)
  • If b = 0 Then
  • If a < 0 Then
  • d = -a
  • u = -1
  • v = 0
  • Else
  • d = a
  • u = 1
  • v = 0
  • End If
  • Else
  • If b < 0 Then
  • Call Bezout(a, -b, d, u, v)
  • v = -v
  • Else
  • Call Bezout(b, a Mod b, d, u, v)
  • u = u + v ' En gros la ca fait :
  • v = u - v ' U2 = -v et V2 = u - v * (a\b)
  • u = u - v ' Renvoyer U2 et V2 ( u=U2 : v=V2 )
  • v = v - u * (a \ b)
  • End If
  • End If
  • End Sub
' Appel :
'
'Dim A as integer, B as integer 
'Dim D as integer, U as integer, V as integer 
' A = Val(Text1.Text)
' B = Val(Text2.Text) 

'Note : Il n'est pas nécessaire d'initialiser U et V à zéro avant l'appel.

'Call Bezout(A, B, D, U, V)

'Text3.Text = U
'Text4.Text = V
'Text5.Text = "PGCD( A , B ) = " & D

Private Sub Bezout(a As Integer, b As Integer,Byref d as integer, ByRef u As Integer, ByRef v As Integer)
 If b = 0 Then
    If a < 0 Then
       d = -a
       u = -1
       v = 0
    Else
       d = a
       u = 1
       v = 0
    End If
 Else
    If b < 0 Then
       Call Bezout(a, -b, d, u, v)
       v = -v
    Else
       Call Bezout(b, a Mod b, d, u, v)
       u = u + v '  En gros la ca fait :           
       v = u - v    '  U2 = -v      et      V2 = u - v * (a\b)         
       u = u - v    '  Renvoyer U2 et V2 ( u=U2 :  v=V2 )
       v = v - u * (a \ b)
    End If
 End If
End Sub

 Conclusion

Vive la récursivité !


 Sources du même auteur

Source avec Zip Source avec une capture PRIORISATEUR D'AFFICHAGE (PERMET D'AFFICHER EN PREMIER PLAN ...
Source avec Zip ANALYSEUR SYNTAXIQUE QUE JE JUGE PUISSANT
TROUVE LES DATE DE DÉBUT ET FIN DE SEMAINE POUR UN SEMAINE E...
Source avec Zip TRACER UN CERCLE SANS : SIN() , COS() NI LA PROPRIÉTÉ CIR...
Source avec Zip Source avec une capture MOUVEMENT (RECTILIGNE) D'UNE PARTICULE, REFLÉTÉE PAR DES SEG...
Toutes les sources de Zeroc00l

 Sources de la même categorie

Source avec Zip Source avec une capture CONVERTISSEUR HEXAVIGÉSIMAL par shaeks
Source avec Zip Source avec une capture Source .NET (Dotnet) CRYPTOGRAPHIE AFFINE par Tigrou66
Source avec Zip Source avec une capture SCANNER FLEX par lajouad
Source avec Zip EQUATIONSECONDDEGRÉ,MATH,DEGRÉ par shadkitenge
Source avec Zip Source .NET (Dotnet) SOMME DE CHIFFRES CONTENUE DANS UN NOMBRE par alpha5
Toutes les sources de la catégorie Maths

Commentaires et avis

Commentaire de jesusonline le 08/02/2004 21:56:29 administrateur CS

Je voulais posté à peu pres la meme source (en .net) en meme temps que toi [:)]
Ta source est bien :) pensé et assez simple

Commentaire de Urgo le 08/02/2004 22:16:29

J'ai justement taffé la dessus en spé maths y'a un mois héhé

Commentaire de cyberlulu le 09/02/2004 19:08:35

salut zerocool ! alors d'abord encore merci pour cette source !
et ensuite, j'ai bien essayer de comprendre comment il marche ton programme mais pas moyen de comprendre la fin..... tu mets d'abord u= puis v= et ensuite de nouveau u=.... et là je capte plus rien... si tu pourais juste expliquer ca vite fait, ca serait sympa... :-)

Commentaire de Zeroc00l le 23/02/2004 02:04:36

ok j'explique...
Pour inverser les valeurs que contiennent deux variables il y a la technique bourrin :
Celle que tout le monde connait : On crée une troisième variable temporaire :

Dim a as integer , b as integer
a = 2
b = 3
Dim tmp as integer
tmp = a
a = b
b = tmp
...

Mais pour des valeurs numériques on peut procéder autrement :

a = a + b
b = a - b
a = a - b

exemple a = 3 et b = 7 :

a = a + b =  3 + 7 = 10
b = a - b = 10 - 7 = 3
a = a - b = 10 - 3 = 7

On comprend vite que les valeurs de départ sont sauvegardés.
Mais le but de l'algo n'est pas de faire a = b et b = a
mais :

U = V
V = U - V * (A\B)    

J'ai donc adapté...

Commentaire de kimmelf2 le 25/02/2004 00:02:22

Plus rapide je crois (en exec)
a=(a xor (b= b xor ( a = a xor b)))
ou si vous preferez :
a = a xor b
b = b xor a
a = a xor b

ou en asm (pour montrer le peu d'instruction processeur necessaires)
xor eax,ebx
xor ebx,eax
xor eax,ebx
le xor est normallement une instruction + rapide qu'une somme ou une difference

ex :
a=3 , b= 7
a = a xor b = 3 xor 7 = 4
b = b xor a = 7 xor 4 = 3
a = a xor b = 4 xor 3 = 7

Commentaire de Zeroc00l le 26/02/2004 01:56:55

Ohhhhhhhhhhhh !
Que c'est jolie !
J'avais oublié les propriétés du XOR qui justement permettent ça ...
En tout cas, là, plus de problème de dépassement possible...
j'ai testé et c'est effectivement plus rapide ...
Merci ! je m'en souviendrai ... :)

-~=[{ ZeroCool }]=~-

P.S : Vive l'algo !

Commentaire de kimmelf2 le 28/02/2004 22:53:59

dis plutot merci a notre bon vieil Amiga (pour ceux qui s'en souviennent) qui mettai
#define SWAP(a,b) ((a)= (a) ^ ((b) = (b)^ ((a) = (a) ^ (b))))

souvenirs ....
regrets .... ze vzux mon amiga !!!!!!!!!!!!!!!!!!! ouinnnnnnnnnnnnnnnnnnnn

:-)

Commentaire de kimmelf2 le 29/02/2004 23:36:53

au fait, c'est quoi l'algo de bezout ???

ca sert a quoi ?

Commentaire de Zeroc00l le 08/07/2004 02:02:45

Si tu as A et B, deux nombres entiers positifs ou négatifs,
trouver le PGCD de deux nombres revient à trouver le plus grand nombre qui divise à la fois A et B.

Exemple : 63 et 27
PGCD (63, 27) [également noté : 63 ^ 27] = 9
63 = 7 * 9
27 = 3 * 9

Conséquence directe, si on appelle d le PGCD de  A et B :
A/d  et   B/d sont premiers entre eux.
PGCD(A/d , B/d) = 1
Effectivement 3 et 7 sont premier entre eux.

L'algorithme de Bezout permet de trouver deux nombres que l'on appelera U et V qui, pour deux nombres donné A et B, nous permet d'obtenir la relation suivante :

A*U+B*V = PGCD(A, B)
donc
(9).3 * U   +   (9).7 * V = (9).1    une petite simplification... par 9

L'algo nous donnerait U = -2 et V = 1

Dans notre cas cet algorithme prendrait en paramètre A et B, ainsi que trois variables (initialisées ou non) pour stocker le résultat de la fonction : les d, U et V de notre exemple.

Commentaire de sylvanox le 09/02/2009 21:10:38 10/10

Merci ca m'est bien util pour vérifier mes calculs =) +10

 Ajouter un commentaire

Nos sponsors


Sondage...

Comparez les prix


Acer Liquid (noir) (XP.H480Q.013)
Entre 300€ et 346€

Visiter le guide achat

CalendriCode

Février 2012
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
272829    

Consulter la suite du CalendriCode

Photothèque

Photo Green Energy Solutions With Light Bulb Morphed Into LandscapePhoto Beautiful woman in a bikini meditating on the beach
Photo Pêche au Carrelet, la Barre-de-Monts, vendée (85), Pays de loire 

Visiter la photothèque
 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 1,061 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)