Jesteś tutaj: start Dzwonki kat infa Języki programowania NWD algorytm Euklidesa

NWD algorytm Euklidesa

Szczegóły
Kategoria: Języki programowania

 

Algorytm Euklidesa – algorytm wyznaczania największego wspólnego dzielnika dwóch liczb. Został opisany przez greckiego matematyka, Euklidesa w jego dziele "Elementy", w księgach siódmej oraz dziesiątej.
Zoptymalizowany algorytm Euklidesa

W przypadku optymalnego rozwiązania NWD postępujemy następująco: załóżmy, że wyznaczamy NWD dwóch liczb naturalnych a i b. W każdym przejściu pętli wykonujemy dwie operacje


a = b

b = a mod b


Czynności te powtarzamy do momentu, gdy zmienna b osiągnie wartość zero. Zmienna a będzie przechowywać wtedy największy wspólny dzielnik liczb podanych na wejściu.

 

#include <iostream>

using namespace std;

 

int main(){

int a,b,c;

    cout << "Podaj pierwsza liczbe: ";

    cin >> a;

    cout << "Podaj druga liczbe: ";

    cin >> b;

    while (b!=0){

        c = a % b;

        a = b;

        b = c;

    }

    cout << "Najwiekszy wspolny dzielnik: " << a << endl;

}