Algorithme de bezout : trouver u, v et pgcd(a,b) tel que u.a + v.b = pgcd(a,b)

Commenter

Contenu du snippet

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 / Exemple : 


' 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é !

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_Zeroc00l)