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.

Schemat algorytmu w wersji z dzieleniem

Przykładowe obliczenia

NWD(64,18) = 2

NWD(128,36) = 4

Z filmem możesz więcej ...

Podstawowy kod programu w C++

#include <iostream>
using namespace std;
int main(){
	int a, b; //liczby do NWD(a,b)
	int pom; //zmienna pomocnicza
	int start_a, start_b; //zapamiętanie początkowych wartości a i b
	cout<<"Podaj dwie liczby naturalne:\n";
	cout << "a="; cin >>a; 
	cout << "b="; cin >>b;
	start_a=a;
	start_b=b;
	while(b!=0){
		pom=b;
		b=a%b;
		a=pom;
	}
	cout << "NWD(" << start_a << "," << start_b << ")=" << a;
	return 0;
}

Kod z wykorzystaniem funkcji zwracającej i niezwracającej wartości

#include <iostream>
using namespace std;
//funkcja zwracająca wartość typu int
int NWD(int aa, int bb){
	int pom;
	while(bb!=0){
		pom=bb;
		bb=aa%bb;
		aa=pom;
	}
	return aa;
}
//funkcja niezwracająca wartości z wyświetlaniem wartości zmiennych
void NWD1(int aa, int bb){
	int pom;
	while(bb!=0){
		pom=bb; cout << "pom=" << pom;
		bb=aa%bb; cout << " b=" << bb;
		aa=pom; cout << " a=" << aa << endl;
	}
	cout << "NWD=" << aa;
}
//program główny
int main(){
	int a, b; //liczby do NWD(a,b)
	int start_a, start_b;
	cout<<"Podaj dwie liczby naturalne:\n";
	cout << "a="; cin >>a; 
	cout << "b="; cin >>b;
	start_a=a;
	start_b=b;
	cout << "wersja 1\n"; //funkcja zwracająca wartość
	cout << "NWD(" << start_a << "," << start_b << ")=" << NWD(a, b);
	cout << "\nwersja 2\n"; //funkcja niezwracająca wartości
	NWD1(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