Algorytm

Algorytm Euklidesa służy do wyznaczania największego wspólnego dzielnika dwóch liczb całkowitych. Największy wspólny dzielnik dwóch liczb a i b, to taka liczba, która dzieli te liczby bez reszty i jest ona możliwie największa. Można go zastosować do skracania ułamków lub wyznaczenia najmniejszej wspólnej wielokrotności NWW.

Podstawowy kod programu w C++ z wykorzystaniem funkcji zwracających wartości z dwoma parametrami.

//algorytm Euklidea w wersji z dzielenim i odejmowaniem
// za pomocą funkcji
#include<iostream>
using namespace std;

int NWDodejmowanie(int x, int y){
	while(x!=y){
    	if(x>y) x=x-y;
		else y=y-x;
	}
	return x;
}

int NWDdzielenie(int x, int y){
	int pom;
	while(y!=0){
	    	pom = y;
	    	y = x%y;
	    	x = pom;    	
	}
	return x;
}

int main() {
    int a, b; //liczby do NWD(a,b)
    int start_a, start_b; //wartości początkowe liczb a i b 
    cout<<"Podaj dwie liczby naturalne:\n";
    cout << "a="; cin >>a; 
    cout << "b="; cin >>b;
    //początkową wartość a przechowamy w start_a
    start_a=a;
    //początkową wartość b przechowamy w start_b
    start_b=b;
    
    cout << "\nwersja z odejmowniem\n";
    cout<<"NWD(" << start_a << "," << start_b << ") = "<< NWDodejmowanie(a, b);
    cout << "\nwersja z dzieleniem\n";
    cout<<"NWD(" << start_a << "," << start_b << ") = "<< NWDdzielenie(a, b);
    return 0;
}

Wykorzystanie kodu

• Powyższy kod można wykorzystać w środowisku Dev C++ lub innym. Wystarczy utworzyć nowy projekt i wkleić ten kod zamiast istniejącego.
• Można też użyć kodu na jednej ze stron WWW z kompilatorami on-line, na przykład na stronie: www.cpp.sh