Euclidienne algorithme utilisant uniquement Soustraction
Euclidienne algorithme utilisant uniquement Soustraction
Explications de l'algorithme d'Euclide pour trouver le plus grand commun diviseur de deux entiers semblent souvent long et alambiqué. L'idée est, en fait, très bien simple. Tout ce qu'il est est un processus de soustraction répétée, portant le résultat vers l'avant chaque fois jusqu'à ce que le résultat est égal à la somme étant soustrait. Si la réponse est supérieur à 1, il y a un GCD (en plus 1). Si la réponse est 1, il n'y a pas grand commun diviseur (en plus 1), et ainsi les deux chiffres sont coprime. ou le premier par rapport à l'autre.
L'algorithme soustractive est simple, où vous rincer et répéter "les boucles internes aussi longtemps que n'est pas égal à b.
Do While une <> b
Do While a> b
c = a - b
a = c
Boucle
Do While b> a
c = b - a
b = c
Boucle
Boucle
Qu'est-ce que vous vous retrouvez avec un ou b est égal à 1, pas GCD, ou a ou b est supérieur à 1, un GCD.
Peut-être la simplicité de l'algorithme est obscurci par la pratique habituelle de l'utilisation de la division modulaire. En fait, la division modulaire n'est pas nécessaire - et les Grecs n'a certainement pas l'utiliser! Cependant, l'algorithme d'Euclide est aussi une grande démonstration de la puissance de l'arithmétique modulaire.
Testez l'exemple suivant VBA / VB6 avec, par exemple, un numéro à 10 chiffres et un numéro à 3 chiffres. La méthode de soustraction prendra des milliers d'itérations pour produire un résultat. (Si vous obtenez un trop-plein, il est probablement parce que vous avez dépassé la limite listbox.) Puis essayez de remplacer la soustraction avec le couple de lignes de division modulaire dans le code ci-dessous et voir comment est réalisé le résultat en quelques itérations et un fraction de seconde.