Visual Basic, VB6, VB.NET, VB 2005, VB CodeS-SourceS

CodeS-SourceS est hébergé par Frontier.fr

Ce site au démarrage

begin process at 2010 02 10 13:22:35

Accueil Codes Tutoriels Forum Livres Emploi Services Connexion

Trouver un code source :

dans

[ Dernières recherches ]

Accueil >

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,50 / 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 :6 987

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

PRIORISATEUR D'AFFICHAGE (PERMET D'AFFICHER EN PREMIER PLAN ...

ANALYSEUR SYNTAXIQUE QUE JE JUGE PUISSANT

TROUVE LES DATE DE DÉBUT ET FIN DE SEMAINE POUR UN SEMAINE E...

TRACER UN CERCLE SANS : SIN() , COS() NI LA PROPRIÉTÉ CIR...

MOUVEMENT (RECTILIGNE) D'UNE PARTICULE, REFLÉTÉE PAR DES SEG...

Toutes les sources de Zeroc00l

Sources de la même categorie

PISH2010-VB2008 par SaintMaur

PI-SH-2010-VB6 par SaintMaur

ET... PI... par us_30

CHIFFRAGE ET DECHIFFRAGE FONCTION AFFINE par tresorsdevie

NB PREMIER : TEST DE FERMAT ET DE MILLER-RABIN par us_30

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

Derniers Blogs

TECHDAYS PARIS 2010 : SHAREPOINT 2010 POUR LES DéVELOPPEURS par ROMELARD Fabrice

TECHDAYS PARIS 2010 : PLEINIèRE DERNIER JOUR par ROMELARD Fabrice

UNE JOLIE-HORLOGE ET PAS QU'UN PEU ! par neodante

TECHDAYS PARIS 2010 : CONNECTEZ VOS DONNéES à SHAREPOINT 2010 AVEC LES BUSINESS CONNECTIVITY SERVICES par ROMELARD Fabrice

[DIVERS] SUIVRE VOS SéRIES PRéFéRéS SUR LA TOILE par orion

Forum

TAILLE par nounuo74

RE : PRENDRE DATE MAX PLUS PETITE QU'UNE DATE DONNéE par Renfield

LANCER UNE APPLICATION EN TANT QUE MDICHILD D'UNE APPLICATION DéJà OUVERTE par tcourbet

AFFICHER PLUSIEURS IMAGES par powerwave

RE : PRENDRE DATE MAX PLUS PETITE QU'UNE DATE DONNéE par Fabien75008

Côté IT

Offres d'emploi

Formations Video

Appels d'offres

Cherche formation complete en GIMP
Budget : 750€
Module sur Prestashop
Budget : 700€
Redaction d-une page de vente pour un ebook
Budget : 300€

Logiciels

DB-MAIN (9.1.0)
DB-MAIN (9.1.0)

DB-MAIN is a data-modeling and data-architecture tool. It is designed to help developers and anal...

Cliquez pour télécharger DB-MAIN
Xilisoft DPG Convertisseur (5.1.37.0120)
XILISOFT DPG CONVERTISSEUR (5.1.37.0120)

Xilisoft DPG Convertisseur offre aux fans de Nintendo DS une bonne solution leur permettant de dé...

Cliquez pour télécharger Xilisoft DPG Convertisseur
GraphicsGale (2.01.01)
GRAPHICSGALE (2.01.01)

GraphicsGale est un logiciel de PixelArt avec de nombreuse fonctionnalités permettant de réalisé ...

Cliquez pour télécharger GraphicsGale
Architecte 3D (Platinum 2010)
ARCHITECTE 3D (PLATINUM 2010)

Architecte 3D Platinium vous permet de concevoir facilement les plans votre future maison, de l'é...

Cliquez pour télécharger Architecte 3D
TeamViewer 5 (TeamViewer 5)
TEAMVIEWER 5 (TEAMVIEWER 5)

Dépanner un ami,expliquer une manipulation devient un jeu d'enfant. Prise en main d'un autre ord...

Cliquez pour télécharger TeamViewer 5