/ programowanie

Algorytm Euklidesa

Spróbuję tutaj opisać algorytm Euklidesa. Nie jest to trudne... więc zaczynamy. Do czego służy ten algorytm? Dzięki niemu można obliczyć największy wspólny dzielnik dwóch lub więcej liczb. W skrócie nazywa się to NWD. Algorytm ten został opisany przez Euklidesa około 300 roku p.n.e. Algorytm Euklidesa jest algorytmem rekurencyjnym. Ok, teraz przejdźmy do przykładów. Jeżeli mamy do policzenia NWD(a,b) (czyli nasz algorytm gdzie a i b to jakieś liczby) to sprawdzamy czy b jest równe 0. Jeżeli tak to NWD(a,b)=a. Jeżeli b jest różne od zera to wywołujemy rekurencyjnie algorytm dla liczb b i (a % b). Znakiem % oznaczam tutaj modulo, czyli reszte z dzielenia liczby a przez b czyli np. 19 % 3 = 1 bo 19 dzielone przez 3 to 6 i reszty 1. ;-] Ok, teraz przykład. Rozwiążemy NWD dla liczb 43 i 58 czyli NWD (43,58). I teraz, nasza liczba b, czyli 58 nie jest równa zero czyli obliczamy algorytm dla liczb 58 i (43 % 58) czyli NWD(58,43). Jak widać liczby się odwróciły z czego można wywnioskować, że nie muszą one być podawane w odpowiedniej kolejności. Następnie znowu patrzymy czy nasze b jest równe zero, a nie jest bo b wynosi 43. Wykonujemy znowu rekurencyjnie algorytm dla liczb 43 i (58 % 43) czyli NWD(43,15). Znowu b nie jest równe zero więc mamy teraz 15 i (43 % 15) czyli NWD(15,13). I znowu b jest różne od zera więc 13 i (15 % 13), NWD(13,2). Heh, i znowu b nie równa się zero wykonujemy algorytm dla liczb 2 i (13 % 2) czyli NWD(2,1). Jeden to nie zero więc dalej dla liczb 1 i (2 % 1), NWD(1,0). Teraz b jest równe zero, więc według wcześniej podanego wzoru NWD = 1. Heh dziwny przykład wziąłem ale już mi się nie chce liczyć więc niech będzie ;-) Mam nadzieje, że każdy wie o co chodzi. Czyli podsumowanie. Jeżeli dla NWD(a,b), b=0 to NWD=a. A gdy b nie jest zerem to liczymy NWD(b(a%b)). ;-) Prawda, że proste? ;-) A, jeszcze jedno, jak obliczyć NWD dla większej ilości liczb? Jeżeli mamy np. 24, 34, 56, 32 to liczymy NWD dla pierwszych dwóch liczb, następnie dla otrzymanego wyniku i liczby trzeciej, i znowu NWD z otrzymanego wyniku dla liczby czwartej itd ;-) Hm, mimo tego, że dopiero uczę się programowania w C++ spróbuję napisać ten algorytm ;-) Może komuś się przyda... Oto on:

#include <iostream>
main()
{
	int a, b, c;
	cout << "* Witam w programie do obliczania "
     	     << "największego wspólnego dzielnika dwóch liczb. *\n\n";
	cout << "Podaj pierwszą liczbę: ";
	cin >> a;
	cout << "\nPodaj drugą liczbę: ";
	cin >> b;
	cout << "\nNo to liczę NWD dla liczb: " << a << " i " << b << " ... \n\n";
	if(a != 0)
	{

		switch(b)
		{

			case 0:
			cout << "Dla podanych liczb NWD wynosi: " << a << "\n\n" ;
			break ;

			default:
			do
			{
				c = (a % b);
				a = b;
				b = c;
			}
			while(b != 0);
			cout << "Dla podanych liczb NWD wynosi: " << a << "\n\n";
		}
	}
	else
	{
		cout << "Dla podanych liczb NWD wynosi: " << b << "\n\n";
	}
}

Napisałem ;-] Może da się prościej ale po pierwsze nie chce mi się myśleć bo już 2 minuty po północy jest, po drugie działa i jest dobrze ;-) Oczywiście można by było to if z a !=0 i switch z tym b = 0 wyrzucić bo nie jest aż tak bardzo potrzebne ale jak już napisałem to niech będzie ;-) Jak widać nie jest to trudne, prawda ? ;-] Ok, idę spać bo nudy ;-P