Algorytm Euklidesa - Algorytmy i Struktury Danych

Wpisany przez Michał Knasiecki, 26 lipca 2005 23:21

Euklides opracował prosty i efektywny algorytm wyznaczania największego wspólnego dzielnika (NWD, ang. GCD - Greatest Common Divisor).
Dla danych dwóch liczb a i b polega on na odejmowaniu od większej mniejszej. Gdy liczby są równe otrzymamy NWD - największy wspólny dzielnik.
max{a,b}:=max{a,b}-min{a,b} gdzie max{a,b}, min{a,b} oznaczają odpowiednio największy i najmniejszą liczbę ze zbioru {a,b}.
Najlepiej zrozumieć to na przykładach:

a	b	max{a,b} - min{a,b}
24	6	24-6 = 18
18	6	18-6 = 12
12	6	12-6 = 6
6	6	NWD = 6

a	b	max{a,b}-min{a,b}
3	10	10-3 = 7
3	7	7-3 = 4
3	4	4-3 = 1
3	1	3-1 = 2
2	1	2-1 = 1
1	1	NWD = 1

Schemat blokowy tego algorytmu można przedstawić następująco: schemat blokowy - algorytm Euklidesa

Implementacje

Autor	Język programowania	Komentarz	Otwórz	Pobierz	Ocena
Tomasz Lubiński	Ada		.ada	.ada	***** / 7
Tomasz Lubiński	C#	MS Visual Studio .net	.cs	.cs	***** / 21
Tomasz Lubiński	C/C++		.cpp	.cpp	***** / 6
Marian	C/C++	C++	.cpp	.cpp	***** / 76
Nikodem Solarz	C/C++	C++ z wyświetlaniem obliczeń	.cpp	.cpp	***** / 3
Michał Knasiecki	Delphi/Pascal	Borland Delphi 5	.pas	.pas	***** / 3
Adam Chrapkowski	Haskell	wersja rekurencyjna z operatorem modulo	.hs	.hs	***** / 5
Tomasz Lubiński	Java		.java	.java	***** / 22
gchlebus	Java	gotowa klasa do użycia	.java	.java	***** / 8
Jakub Konieczny	Java_Block		.jbf	.jbf	***** / 4
_marass_	Php		.php	.php	***** / 6
Tobiasz Siemiński	Python	wersja z operatorem modulo	.py	.py	***** / 9
Łukasz Margiela	Python		.py	.py	***** / 8
Nikodem Solarz	Ruby	Funkcje wyliczające	.rb	.rb	***** / 2

Poprawiony: 14 stycznia 2020 14:06

Komentarze

+1 # piter 2009-10-01 14:01

bardzo dobry tekst

Odpowiedz | Odpowiedz z cytatem | Cytować

-2 # Tomek 2009-10-09 14:03

bardzo dobry tekst i pomocny

Odpowiedz | Odpowiedz z cytatem | Cytować

-2 # Madzik: 2009-10-14 19:13

bardzo dobrze i zrozumiale napisany tekst

oby takich więcej

Odpowiedz | Odpowiedz z cytatem | Cytować

+4 # Tedi 2009-11-02 19:40

Tekst, a schemat jeszcze bardziej logiczny i klarownie przedstawiający problem od kuchni. W przykladowych plikach wybór spory, jako nowicjuszowi brakuje mi przykładu w LOGO. Widzę też literówkę w przykładowych wynikach w tabelkach - powinno być NWD.

Odpowiedz | Odpowiedz z cytatem | Cytować

-5 # Szopen 2010-02-24 17:51

Siemka
Jak dla mnie wypasik róbcie więcej algorytmów z grafami łatwiej się połapać ale ogólnie super stronka

Odpowiedz | Odpowiedz z cytatem | Cytować

-3 # Nyarlar 2010-10-10 12:30

Bardzo przejrzyste i łatwe do zrozumienia. Dzięki wielkie

Odpowiedz | Odpowiedz z cytatem | Cytować

-2 # jola 2010-12-07 11:06

ale ja potrzebuję to w logo komeniusz...pomóżcie!!

Odpowiedz | Odpowiedz z cytatem | Cytować

-1 # Ann... 2011-02-22 11:08

dość zrozumiale, latwo można zrozumieć i zapamiętać ;d oby więcej takich algorytmów a raczej schematów do algorytmów tak zrozumialych i prostych jak ten xd ;] pozdrawiam...:)

Odpowiedz | Odpowiedz z cytatem | Cytować

-2 # Termos 2011-10-27 19:50

Swietny ! naprawde przydal mi sie :)

Odpowiedz | Odpowiedz z cytatem | Cytować

Dodaj komentarz

JComments


Dodaj własną implementację tego algorytmu
Zaloguj się na stronie
Plik:
Język programowania:
Komentarz:
	By móc dodać implementacje zaloguj się na stronie