Μέγιστος κοινός διαιρέτης, με τον αλγόριθμο του Ευκλείδη, στη C++

Η πλήρης προβολή του βίντεο απαιτεί σύνδεση

Το βίντεο έχει διάρκεια 8:12, πιθανά να χρειάζεται λίγος χρόνος για την προβολή του.

cpp if do-while βρόγχος επανάληψη υπό συνθήκη μέγιστος κοινός διαιρέτης αλγόριθμος Ευκλείδη

Ο αλγόριθμος του Ευκλείδη είναι ο πατέρας όλων των αλγορίθμων (Donald Knuth).

Η εφαρμογή του για την εύρεση του μέγιστου κοινού διαιρέτη έχει περάσει αναλλοίωτη στις μέρες μας.

Το παρακάτω πρόγραμμα δέχεται δύο ακεραίους απρόσημους αριθμούς και υπολογίζει το μέγιστο κοινό διαιρέτη. Το πρόγραμμα εκτελείται ταχύτερα (μια επανάληψη λιγότερη) αν a > b, ωστόσο θα δώσει το σωστό αποτέλεσμα έτσι κι αλλιώς.

#include <iostream>

using namespace std;

int main()
{
    unsigned long int a, b; 
    unsigned long int m;
 
    cout << "Give me the first integer, a = ";       
    cin >> a;
    cout << "Give me the second integer, b = ";          
    cin >> b;

    if (b > a)
    {
        m = a;
        a = b;
        b = m;
    }

    if (b != 0)
    {   
        do
        {
            m = a - (a/b)*b;
            if (m == 0) break;
            a = b;
            b = m;
        } while (m > 0);
        cout << "GCD = " << b << endl;
    }
    else
    {
         cout << "GCD = " << a << endl;       
    } 

    return 0;
}

Μεταγλώττιση και δοκιμαστική εκτέλεση:

astavrak@apollonia:~$ g++ program.cpp
astavrak@apollonia:~$ ./a.out 
Give me the first integer, a = 108
Give me the second integer, b = 40
GCD = 4

Συνδεθείτε για περισσότερες δυνατότητες αλληλεπίδρασης,
σχολιασμοί, εξωτερικοί σύνδεσμοι, βοήθεια, ψηφοφορίες, αρχεία, κτλ.

Εκπαιδευτικό υλικό από τον Αθανάσιο Σταυρακούδη σας παρέχετε κάτω από την άδεια Creative Commons Attribution-NonCommercial-ShareAlike 4.0 License.
Σας παρακαλώ να ενημερωθείτε για κάποιους επιπλέον περιορισμούς
http://stavrakoudis.econ.uoi.gr/stavrakoudis/?iid=401.

Athanassios Stavrakoudis, Sat 23 Nov 2024