Euklids Algorithmus (größter gemeinsamer Teiler)

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.

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.

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;
}

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;

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.

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);
}

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 *