algorytm.org

Algorytm Euklidesa



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Euklidesa
Ocena użytkowników:***** / 140
SłabyŚwietny 
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:
abmax{a,b} - min{a,b}
24624-6 = 18
18618-6 = 12
12612-6 = 6
66NWD = 6
abmax{a,b}-min{a,b}
31010-3 = 7
377-3 = 4
344-3 = 1
313-1 = 2
212-1 = 1
11NWD = 1


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

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiAda
.ada
.ada
***** / 7
Tomasz LubińskiC#MS Visual Studio .net
.cs
.cs
***** / 21
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 6
MarianC/C++C++
.cpp
.cpp
***** / 76
Nikodem SolarzC/C++C++ z wyświetlaniem obliczeń
.cpp
.cpp
***** / 3
Michał KnasieckiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 3
Adam ChrapkowskiHaskellwersja rekurencyjna z operatorem modulo
.hs
.hs
***** / 5
Tomasz LubińskiJava
.java
.java
***** / 22
gchlebusJavagotowa klasa do użycia
.java
.java
***** / 8
Jakub KoniecznyJava_Block
.jbf
.jbf
***** / 4
_marass_Php
.php
.php
***** / 6
Tobiasz SiemińskiPythonwersja z operatorem modulo
.py
.py
***** / 9
Łukasz MargielaPython
.py
.py
***** / 8
Nikodem SolarzRubyFunkcje wyliczające
.rb
.rb
***** / 2
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 14 stycznia 2020 14:06
Komentarze
photo
+1 # piter 2009-10-01 14:01
bardzo dobry tekst
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-2 # Tomek 2009-10-09 14:03
bardzo dobry tekst i pomocny


Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-2 # Madzik: 2009-10-14 19:13
bardzo dobrze i zrozumiale napisany tekst

oby takich więcej
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+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ć
photo
-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ć
photo
-3 # Nyarlar 2010-10-10 12:30
Bardzo przejrzyste i łatwe do zrozumienia. Dzięki wielkie
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-2 # jola 2010-12-07 11:06
ale ja potrzebuję to w logo komeniusz...pomóżcie!!
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-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ć
photo
-2 # Termos 2011-10-27 19:50
Swietny ! naprawde przydal mi sie :)
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz