Euklidische Algorithmus Subtraction Nur
Euklidische Algorithmus Subtraction Nur
Erklärungen des euklidischen Algorithmus für den größten gemeinsamen Teiler zweier ganzer Zahlen zu finden, scheinen oft lang und gewunden. Die Idee ist in der Tat schön einfach. es ist alles ist ein Prozess der Wiederholung Subtraktion, das Ergebnis vorwärts jedes Mal trägt, bis das Ergebnis auf die Menge gleich abgezogen wird. Wenn die Antwort größer als 1 ist, gibt es eine GCD (außer 1). Wenn die Antwort 1 ist, gibt es keinen gemeinsamen Teiler (außer 1), und so sind beide Zahlen coprime. oder relative Primzahl ist, zueinander.
Der subtraktiven Algorithmus ist einfach dies, wo Sie ‚spülen und wiederholen‘, um die inneren Schleifen solange ein nicht gleich b.
Do While ein <> b
Do While a> b
c = a - b
a = c
Schleife
Do While b> a
c = b - a
b = c
Schleife
Schleife
Was Sie links mit einem oder b gleich 1 ist, keinen GCD, oder a oder b größer als 1 ist, ein GCD.
Vielleicht ist die Einfachheit des Algorithmus wird durch die übliche Praxis der Verwendung von modularen Aufteilung verdeckt. In der Tat ist modular Teilung nicht erforderlich - und die Griechen sicherlich nicht genutzt! Allerdings ist der euklidische Algorithmus auch eine große Demonstration der Macht der modularen Arithmetik.
Testen Sie das folgende VBA / VB6 Beispiel mit, sagen wir, eine 10-stellige Nummer und eine 3-stellige Zahl. Die Subtraktion Methode wird Tausende von Iterationen nimmt ein Ergebnis zu erzeugen. (Wenn Sie einen Überlauf zu bekommen, ist es wahrscheinlich, weil Sie die Listbox Grenze überschritten haben.) Versuchen dann Subtraktion ersetzt mit den paar Zeilen von modularen Aufteilung in dem folgenden Code, und sehen, wie das Ergebnis innerhalb von nur wenigen Iterationen und ein erreicht Bruchteil einer Sekunde.