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 odejmowaniem

Przykładowe obliczenia

NWD(25,35) = 5

NWD(39,12) = 3

Koduj sam, ale z filmem dowiesz się więcej :)

Podstawowy kod programu z filmu:

#include <iostream>
using namespace std;
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;
    //dopóki a!=b 
    while(a!=b){
    	if(a>b) a=a-b;
	else b=b-a;
	}
    //wyświetlanie wyniku
    cout<<"NWD(" << start_a << "," << start_b << ") = "<< a;
    return 0;
}

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

Dlaczego wersja z odejmowaniem nie jest optymalna?

#include <iostream>
using namespace std;
//funkcja zwracająca wartość
int NWD(int a, int b){
	while(a!=b){
		if(a>b) a=a-b;
		else b=b-a;
	}
	return a;
}
//funkcja niezwracająca wartości
void NWD1(int a, int b){
	int ile=0;
	while(a!=b){
		if(a>b){
			cout << "a=" << a << "-" << b << "=" << a-b << "  b=" << b << endl;
			a=a-b;
			ile++;
		} 
		else {
			cout << "b=" << b << "-" << a << "=" << b-a << "  a=" << a << endl;
			b=b-a;
			ile++;
		}
	}
	cout << "\nIlosc operacji: " << ile;
}
//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;
	//funkcja INT
	cout << "\nwersja 1" << endl;
	cout << "NWD(" << start_a << "," << start_b << ")=" << NWD(a, b);
	// funkcja VOID
	cout << "\nwersja 2" << endl;
	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