Euklids Algorithmus (größter gemeinsamer Teiler)

90289
Fiddling Bits

Laut Donald Knuth in "The Art of Computer Programming" wird im Folgenden beschrieben, wie der größte gemeinsame Teiler zweier positiver Zahlen, m und n, mithilfe des Euclid-Algorithmus ermittelt wird.

  1. Teilen Sie m durch n und lassen Sie r den Rest sein.
  2. Wenn r 0 ist, ist n die Antwort; Wenn r nicht 0 ist, fahren Sie mit Schritt 3 fort.
  3. Setze m = n und n = r . Gehen Sie zurück zu Schritt 1.

Unten ist meine Implementierung dieses Algorithmus.

#include <stdio.h>

int greatestCommonDivisor(int m, int n)
{
    int r;

    /* Check For Proper Input */
    if((m == 0) || (n == 0))
        return 0;
    else if((m < 0) || (n < 0))
        return -1;

    do
    {
        r = m % n;
        if(r == 0)
            break;
        m = n;
        n = r;
    }
    while(true);

    return n;
}

int main(void)
{
    int num1 = 600, num2 = 120;
    int gcd = greatestCommonDivisor(num1, num2); 

    printf("The GCD of %d and %d is %d\n", num1, num2, gcd);

    getchar();
    return 0;
}

Obwohl es gut zu funktionieren scheint, scheint es nicht so elegant zu sein, wie ich es gerne hätte, besonders in der do-whileSchleife. Auch das while(true)scheint gefährlich zu sein, obwohl ich ziemlich zuversichtlich bin, dass rdies auf 0irgendwann reduziert wird und wir breakaus der Schleife herauskommen.

Haben Sie Vorschläge, den Code eleganter oder robuster zu gestalten?

Antworten
16
Wenn "r" niemals 0 ist und die Schleife niemals endet, dann geben Sie Euklid die Schuld. Radiodef vor 6 Jahren 7
Alle ganzen Zahlen sind durch 1 teilbar. Jodrell vor 6 Jahren 1
1. Implementieren Sie einen euklidischen Algorithmus, um die gcd aller N-Zahlen zu finden. [Gcd (a, b), gcd (a, b, c), gcd (a, b, c, d) usw.] vor 6 Jahren 0

7 Antworten auf die Frage

20
Yuushi

Erstens ist Ihre Implementierung (möglicherweise) nicht ganz korrekt:

 else if((m < 0) || (n < 0))
     return -1;

Die GCD von zwei negativen Zahlen ist perfekt definiert. Wenn Sie wirklich nicht möchten, dass der Benutzer negative Zahlen übergibt, machen Sie dies in der Funktionssignatur explizit:

unsigned greatestCommonDivisor(unsigned m, unsigned n)

Der Euklid-Algorithmus ist eines der grundlegendsten Beispiele für die Rekursion:

unsigned greatestCommonDivisor(unsigned m, unsigned n)
{
    if(n == 0) return m;
    return greatestCommonDivisor(n, m % n);
}

Wir prüfen zunächst den Basisfall, der 2 ist: Wenn r 0 ist, ist n die Antwort; Wenn r nicht 0 ist, fahren Sie mit Schritt 3 fort. Der rekursive Aufruf kombiniert tatsächlich die Schritte 1 und 3 hier: m % nSetzt n als Rest r, und wir rufen die Funktion erneut mit auf n = m.

Eine letzte Bemerkung: Viele Leute vermeiden rekursive Funktionen in C / C ++, da die meisten Compiler die Aufrufaufrufe nicht optimieren, um konstanten Stackspeicherplatz zu verwenden. Der Euclid-Algorithmus führt jedoch nur O(log N)Schritte aus. Daher ist er auf jedem Computer mit (vernünftiger) Stapelgröße leicht zu sehen. Dies führt nicht zu einem Stapelüberlauf für Zahlen, deren Größe durch intoder eingeschränkt ist unsigned.

Donald Knuth sagt, der Algorithmus, den ich in meiner Frage erwähnt habe, bezieht sich auf positive Zahlen. Gibt es einen anderen oder erweiterten Algorithmus für positive und negative Zahlen? Fiddling Bits vor 6 Jahren 0
Nicht einverstanden bei der Verwendung von "unsigned" -Parametern für das beschriebene Szenario. Für den angegebenen Code würde ich in Betracht ziehen, nur die absoluten Werte innerhalb der Funktion zu nehmen. Michael Urman vor 6 Jahren 0
@MichaelUrman Sicher, das ist in diesem Fall wahrscheinlich die bessere Idee. Die Verwendung von unsigned war mehr eine Möglichkeit, die Idee zu zeigen, explizit zu sein, welche Parameter tatsächlich für die Funktion zulässig sind. Ich stimme jedoch zu, die Verwendung von abs wäre die bessere Lösung. Yuushi vor 6 Jahren 0
Wenn ich "42, 0" bestanden habe, würde Ihre Implementierung "42" erneut ausführen. Jodrell vor 6 Jahren 0
@Jodrell Ja? 0 ist durch eine beliebige Anzahl teilbar, daher gilt gcd (a, 0) = a für alle a. Wenn Sie [wirklich] (http://math.stackexchange.com/questions/27719/what-is-gcd0-a-where-a-is-a-positive-integer) in die Mathematik davon einsteigen möchten .. . Yuushi vor 6 Jahren 2
@Yuushi, könnten wir auch sagen, dass alle Zahlen durch "0" unendlich teilbar sind und die Funktion vereinfachen, um "0" zurückzugeben; ` Jodrell vor 6 Jahren 0
@ Jodrell Nein. Sie haben es vermischt. Nichts ist durch "0" teilbar, aber "0" ist durch alles teilbar. Yuushi vor 6 Jahren 4
9
Vedran Å ego

Im Gegensatz zu Yuushi mag ich Rekursionen nicht besonders, wenn sie nicht wirklich gebraucht werden. Dies ist einer dieser Fälle.

Erstens die negative Eingabe ... Der größte gemeinsame Teiler der Zahlen -8 und -12 ist 4, würden Sie nicht zustimmen? Also statt

else if((m < 0) || (n < 0))
    return -1;

Ich würde setzen

if (m < 0) m = -m;
if (n < 0) n = -n;

um sicherzustellen, dass beide Zahlen nicht negativ sind. Übrigens macht elseselten (wenn überhaupt) Sinn return.

Zweitens denke ich, dass die Schleife unterbrochen wird

if (r == 0)
    break;

ist irreführend, denn was Sie wirklich tun wollen, ist, die Funktion zu stoppen und das Ergebnis zurückzugeben. Mit anderen Worten,

if (r == 0) return n;

Drittens, da Ihre Schleife technisch unendlich ist, do { ... } while(true);ist sie äquivalent while (1) { ... }. Ich persönlich finde letzteres lesbarer.

Schließlich trueexistiert in Standard C nicht. Wenn Sie es wirklich verwenden möchten, dann schließen Sie ein stdbool.h. Dies gehört zum C99-Standard (funktioniert also nicht in C89 / C90). Ich persönlich bevorzuge 1 und 0, aber das ist wahrscheinlich eine Frage der Gewohnheit.

[Here's] (http://www.galactanet.com/comic/view.php?strip=307) Das Problem mit dem Do-while wurde etwas tiefer erklärt. Shadur vor 6 Jahren 0
Dies wird ungeachtet des Vorzeichens zu Null konvergieren, sodass das Ergebnis einfach abgespielt werden kann: `return n <0? -n: n; '... Ich bin auch eher geneigt,' while ((r = m% n)) 'zu sagen, aber das ist mehr persönliche Präferenz. laindir vor 6 Jahren 0
@laindir Ich arbeite lieber mit den positiven Zahlen, da bei den negativen ein leichter Indeterminismus herrscht: Vor C99 war "%" für die negativen Zahlen nicht eindeutig definiert, und das hängt vom Compiler ab. Ich gebe zu, es ist sehr unwahrscheinlich, dass es so einen alten Compiler gibt, aber einen `?:` Statt zwei `if'-s zu machen, ist IMO es nicht wert. Was Ihr 'while' angeht, mag ich es auch, aber solche Konstrukte sind für den Leser verwirrend (wer `` `leicht mit` == `verwechseln kann). Warum die doppelten Klammern? Vedran Å ego vor 6 Jahren 1
Beim Algorithmus von Euclid (und wahrscheinlich auch bei anderen rein mathematischen Verwendungen der Modulo-Array-Indexierung gibt es keine), ist es unerheblich, ob Ihre Implementierung von modulo auf einer Teilungsrundung in Richtung Null oder in Richtung negativer Unendlichkeit (was, wie Sie richtig feststellen, basiert ist die Implementierung in C89 definiert). Doppelte Klammern ist eine Gewohnheit, die ich durch Aktivieren aller gcc-Warnungen aufgegriffen habe. es macht deutlich, dass der Wert der Zuweisung als Ausdruck verwendet wird (und der Benutzer nicht vorhielt, `while (r == m% n)` zu schreiben). Sie könnten explizit `while ((r = m% n)! = 0)` sagen, aber ich finde das laut. laindir vor 6 Jahren 1
8
ajay

Anstelle der Verwendung des while(true)Konstrukts ist es klarer und lesbarer, eine Bedingung anzugeben, die für die Fortsetzung der Schleife erforderlich ist. Es gcdist auch für negative Ganzzahlen definiert und sie können leicht verarbeitet werden.

Die Grundbedingung ist:

gcd(m, n) = gcd(n, m % n)   when n != 0
          = m             when n = 0

Wenn beide mund nNull sind, gcdwird nicht definiert und wir geben -1 zurück.

#include <stdio.h>

int gcd(int m, int n) {
    if (m == 0 && n == 0)
        return -1;

    if (m < 0) m = -m;
    if (n < 0) n = -n;

    int r;
    while (n) {
        r = m % n;
        m = n;
        n = r;
    }
    return m;
}
5
syb0rg

Sie fügen nicht <stdbool.h>am Anfang Ihres Codes ein, obwohl Sie einen trueWert in einer Anweisung verwenden.


Sie prüfen nie, ob mund nsind für einen vorzeitigen Austritt gleich.


Ihre Bedingungsanweisungen sind aus Sicht der Lesbarkeit gut, können aber auf Wunsch vereinfacht werden

if((m == 0) || (n == 0))
        return 0;

if(!m || !n) 
        return 0;

Anstelle von Hardcoding-Werten würde ich die Eingabe von Werten durch die Benutzer zur Laufzeit zulassen.

int num1 = 600, num2 = 120; // not dynamic
int num1, num2;
printf("%s\n", "Input two numbers: ");
scanf("%d%d", &num1, &num2);
if(!isdigit(num1) || !isdigit(num2)) return -1; // check if input data are integers
...

Einige Leute argumentieren möglicherweise, keine breakAussage in Ihrem Code zu haben und nur zurückzukehren.

if(r == 0)
     return n;

Ich bin eigentlich ein Fan der breakAussage, denn ansonsten muss man einen anderen Ort verfolgen, von dem man zurückkehrt, was mir nicht gefällt.


Verwenden Sie tatsächliche Variablennamen anstelle von nur Buchstaben.

int greatestCommonDivisor(int m, int n) // confusing in
int r;                                  // later algorithms

int greatestCommonDivisor(int num1, int num2) // less
int remainder;                                // confusing

Ich mag es, einfache ifAnweisungen in einer Zeile zusammenzufassen. Das hilft mir zu wissen, dass die ifBedingung nur eine Anweisung und keine Klammern hat.

if((m == 0) || (n == 0)) return 0;
Ich stimme den Variablennamen nicht zu. Hier sind "m" und "n" in Ordnung; Die Verwendung von "num1" und "num2" ist nicht mehr lesbar. Yuushi vor 6 Jahren 5
@Yuushi Hier vielleicht. An anderen Orten wahrscheinlich nicht. Es war nur ein Beispiel, das ich gegeben habe. Ich werde in mehr nützliche Namen bearbeiten. syb0rg vor 6 Jahren 0
5
Michael Urman

Bei diesem kleinen Code ist es wichtiger, Unauffälligkeit zu vermeiden, als mehr Eleganz zu zeigen. (Wenn Sie nicht finden, dass die Rekursion elegant ist und Yuushi zeigt, gibt es dafür ein vernünftiges Argument.) Ich konzentriere mich stattdessen auf Nicht-Code-Eleganz.

Betrachten Sie zukünftige Leser Ihrer Funktion: Fügen Sie einige der Dokumentation, die Sie für Ihre Frage vorgelegt haben, in Ihren Code ein. Während GCD hier sicherlich üblich ist und eine wortwörtliche Erklärung zu Ihrem Code passen würde, kann ein Link oder eine Erinnerung einen langen Weg gehen. Nicht alle Algorithmen sind jedem bekannt.

Berücksichtigen Sie auch die Benutzer Ihres Codes: Dokumentieren Sie, welche Arten von Eingaben die Funktion akzeptiert (anscheinend nicht negative Zahlen) und was sie tut, wenn Eingaben nicht akzeptiert werden (anscheinend gibt sie manchmal -1statt einer GCD zurück). Dies kann Ihnen dabei helfen, das Verhalten zu berücksichtigen und zu normalisieren, wenn ein Parameter 0negativ ist und der andere Parameter . Wenn der aufrufende Code nur Zugriff auf eine Header-Datei hat, kann die Implementierung nicht abgeglichen werden. In solchen Fällen sollte der Aufrufer erwähnt werden, damit der Aufrufer eine Fehlerprüfung durchführen kann.

2
edgework

Der gesamte Algorithmus kann in eine einfache Zeile unterteilt werden (ohne Eingabe der Überprüfung der Eingaben). Um die Geschwindigkeit zu erhöhen, kann diese Leitung bei Bedarf in einer Schleife abgelegt werden und den Aufwand eines Funktionsaufrufs vollständig beseitigen.

Dies hilft auch dem Compiler zu optimieren, indem er weiß, wo und wie die Schleife endet.

Ist das lesbar? Äh, wahrscheinlich nicht von weniger erfahrenen Programmierern, aber es ist elegant ...

#include <stdio.h>


unsigned int gcd(unsigned int m, unsigned int n)
{
    if(!m || !n)
        return(0);

    for(unsigned int r = m%n; r; m = n, n = r, r = m%n);

    return(n);
}


int main()
{
    printf("50, 5: %d\n", gcd(50,5));
    printf("5, 50: %d\n", gcd(5,50));
    printf("34534, 567568: %d\n", gcd(34534, 567568));

    return(0);
}
Sehr schlau! Ich mag das! Das ist im Grunde das, was ich getan habe, aber diese Art von "for" -Schleife verwendet. Genial! Fiddling Bits vor 6 Jahren 0
2
nfgallimore

Hier ist eine einfache rekursive Lösung in C, diese ist ziemlich elegant.

Hinweis * Ich habe ternäre Operatoren für die booleschen Anweisungen verwendet. Geben Sie sie in Google ein, um weitere Informationen zu erhalten, und besuchen Sie die Wikipedia-Seite für ternäre Operatoren in C

#include <stdio.h>
#include <stdlib.h>

// recursively computes gcd
int gcd(int a, int b) 
{
    return (b != 0)? gcd(b, a % b): a;
}

int main(int argc, char* argv[]) 
{
    // Specify values a and b or
    int a = 28, b = 7, result;

    // Run program with command line arguments
    result = (argc != 3)? gcd(a, b): gcd( atoi(argv[1]), atoi(argv[2]) );

    // print result
    printf("\n%d", result);
}

* Und schließlich ist es in ungefähr jeder anderen Sprache: http://rosettacode.org/wiki/Greatest_common_divisor *

Da dies in erster Linie eine englische Website ist, können die meisten Leute diese Sprache nicht verstehen. Ihr erster Codeblock und seine Erklärung sind jedoch in Ordnung. Jamal vor 6 Jahren 1
Ja, ich habe es einfach dort eingefügt, als ich es auf rosettacode.org fand nfgallimore vor 6 Jahren 0