Login lub e-mail Hasło   

Liczby pierwsze - algorytm Euklidesa

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/pr(...)ex.html
Największy Wspólny Dzielnik (NWD) dwóch liczb jest największą liczbą naturalną spośród tych, które dzielą obie te liczby bez reszty. N...
Wyświetlenia: 17.571 Zamieszczono 03/11/2006

Największy Wspólny Dzielnik (NWD) dwóch liczb jest największą liczbą naturalną spośród tych, które dzielą obie te liczby bez reszty.

Np. NWD(24,18) = 6.

W codziennej praktyce NWD służy nam do skracania ułamków do postaci właściwej:

12
18
 =  2
3

Ponieważ największą liczbą naturalną dzielącą bez reszty liczby 12 oraz 18 jest 6, więc po podzieleniu licznika i mianownika ułamka przez NWD otrzymujemy jego postać właściwą, której dalej już nie można uprościć. Dwie liczby nie posiadające wspólnego dzielnika różnego od 1 są względnie pierwsze.

Algorytm wyznaczania NWD podał i udowodnił jego poprawność już w starożytności grecki uczony Euklides w swoim dziele "Elementy". Okazuje się, iż jest on bardzo prosty:

Znajdowanie NWD przy pomocy algorytmu Euklidesa
Jeśli chcesz znaleźć Największy Wspólny Dzielnik dwóch liczb, to od większej odejmuj mniejszą dotąd, aż obie liczby będą sobie równe. Wynik jest ich największym wspólnym podzielnikiem.

Przykład

Obliczmy tym sposobem NWD liczb 24 i 15.

24 - 15 = 9 Od większej liczby odejmujemy mniejszą. Liczby 24 i 15 przechodzą w 15 i 9. Ponieważ nie są one równe, wykonujemy dalej odejmowanie
15 - 9 = 6  Teraz otrzymujemy parę 9 i 6, która dalej nie składa się z liczb sobie równych, więc kontynuujemy odejmowanie.
9 - 6 = 3 Para 6 i 3 - odejmujemy dalej
6 - 3 = 3 Para 3 i 3 - otrzymaliśmy równość, więc liczba 3 jest największym wspólnym podzielnikiem liczb 24 i 15.

Dane wejściowe

a,b - liczby, dla których wyznaczamy NWD, a,b N

Dane wyjściowe

Liczba naturalna równa NWD(a,b)

krok 1: Czytaj a,b
krok 2: Dopóki a b, wykonuj krok 3. Inaczej pisz a i zakończ algorytm.
krok 3:     Jeżeli a > b, to a a - b. Inaczej b b - a

Po odczytaniu wartości liczb a i b rozpoczynamy pętlę, która przerwie się, gdy w wyniku działania algorytmu liczba a będzie równa liczbie b. W takim przypadku dowolna z tych liczb jest największym wspólnym dzielnikiem pierwotnych wartości i wyprowadzamy ją. W przeciwnym wypadku jedna z liczb a lub b jest większa od drugiej. Odejmujemy więc liczbę mniejszą od większej i kontynuujemy pętlę, aż do zrównania wartości a i b.

Zastanów się, czy podany algorytm jest bezpieczny dla wszystkich możliwych wartości a i b? Co się stanie jeśli a lub b będzie równe 0? Jak zmodyfikowałbyś algorytm, aby uwzględniał takie przypadki?


Wydruk z uruchomionego programu
Obliczanie  NWD  algorytmem  Euklidesa
--------------------------------------
(C)2005 mgr Jerzy Wałaszek I LO Tarnów

Podaj a = 18

Podaj b = 24

NWD(18,24) = 6

Koniec, naciśnij klawisz ENTER...
Microsoft Visual Basic 2005 Express Edition

 

Borland
Delphi 7.0
Personal
Edition
// Program znajdowania NWD algorytmem Euklidesa
// (C)2004 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//---------------------------------------------

program Euclide;

{$APPTYPE CONSOLE}

// Funkcja NWD oblicza NWD swoich argumentów
// wykorzystując algorytm Euklidesa
//-------------------------------------------------

function NWD(a,b : cardinal) : cardinal;
begin
while a <> b do
if
a > b then a := a - b else b := b - a;
NWD := a;
end;

//------------------------------------
// Tutaj rozpoczyna się program główny
//------------------------------------

var
a,b : cardinal;
begin
writeln('Obliczanie NWD algorytmem Euklidesa');
writeln('--------------------------------------');
writeln('(C)2004 mgr Jerzy Walaszek I LO Tarnow');
writeln;
write('Podaj a = '); readln(a);
writeln;
write('Podaj b = '); readln(b);
writeln;
if (a <= 0) or (b <= 0) then
writeln('Zle dane!')
else
writeln('NWD(',a,',',b,') = ',NWD(a,b));
writeln;
writeln('Nacisnij klawisz Enter...');
readln; writeln;
end.
Borland
C++ Builder
6.0
Personal
Edition
// Program znajdowania NWD algorytmem Euklidesa
// (C)2004 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//---------------------------------------------

#include <iostream>

using namespace std;

// Funkcja NWD oblicza NWD swoich argumentów
// wykorzystując algorytm Euklidesa
//-------------------------------------------------

unsigned NWD(unsigned a, unsigned b)
{
while(a != b) if(a > b) a -= b; else b -= a;
return(a);
}

//------------------------------------
// Tutaj rozpoczyna się program główny
//------------------------------------

main()
{
unsigned a,b;
char s[1];

cout << "Obliczanie NWD algorytmem Euklidesa\n"
"--------------------------------------\n"
"(C)2004 mgr Jerzy Walaszek I LO Tarnow\n\n"
"Podaj a = "
;
cin >> a;
cout << "\nPodaj b = ";
cin >> b;
cout << endl;
if((a <= 0) || (b <= 0))
cout << "Zle dane!\n";
else
cout << "NWD(" << a << "," << b << ") = " << NWD(a,b);
cout << "\n\nKlawisz Enter = KONIEC";
cin.getline(s,1);
cin.getline(s,1);
}
Microsoft
Visual
Basic 2005
Express
Edition
' Program znajdowania NWD algorytmem Euklidesa
' (C)2005 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' im. K. Brodzińskiego
' w Tarnowie
'---------------------------------------------


Option Explicit On

Module
Module1

' Funkcja NWD oblicza NWD swoich argumentów
' wykorzystując algorytm Euklidesa
'-------------------------------------------------

Public Function NWD(ByVal a As UInteger, _
ByVal b As UInteger) As UInteger
While
a <> b
If a > b Then
a = a - b
Else
b = b - a
End If
End While
Return
a
End Function

Sub
main()

Dim a, b As UInteger

Console.WriteLine("Obliczanie NWD algorytmem Euklidesa")
Console.WriteLine("--------------------------------------")
Console.WriteLine("(C)2005 mgr Jerzy Wałaszek I LO Tarnów")
Console.WriteLine()
Console.Write("Podaj a = ")
a = Val(Console.ReadLine)
Console.WriteLine()
Console.Write("Podaj b = ")
b = Val(Console.ReadLine)
Console.WriteLine()
If (a <= 0) Or (b <= 0) Then
Console.WriteLine("Złe dane!")
Else
Console.WriteLine("NWD({0},{1}) = {2}", a, b, NWD(a, b))
End If
Console.WriteLine()
Console.WriteLine("Koniec, naciśnij klawisz ENTER...")
Console.ReadLine()

End Sub

End Module
Python
# -*- coding: cp1250 -*-
# Program znajdowania NWD algorytmem Euklidesa
# (C)2005 mgr Jerzy Wałaszek
# I Liceum Ogólnokształcące
# im. K. Brodzińskiego
# w Tarnowie
#---------------------------------------------

# Funkcja NWD oblicza NWD swoich argumentów
# wykorzystując algorytm Euklidesa
#-------------------------------------------------

def NWD(a, b):
while a != b:
if a > b: a = a - b
else: b = b - a
return a

#------------------------------------
# Tutaj rozpoczyna się program główny
#------------------------------------

print "Obliczanie NWD algorytmem Euklidesa"
print "--------------------------------------"
print "(C)2005 mgr Jerzy Walaszek I LO Tarnow"
print
a = int(raw_input("Podaj a = "))
print
b = int(raw_input("Podaj b = "))
print
if
(a <= 0) or (b <= 0): print "Zle dane!"
else: print "NWD(", a, ",", b, ") =", NWD(a, b)
print
raw_input
("Nacisnij klawisz Enter...")
JavaScript
<html>
<head>
</head>
<body>
<div align=
"center">
<form name="frmeuklides"
style="border: 1px outset #FF9933; padding-left: 4px;
padding-right: 4px; padding-top: 1px;
padding-bottom: 1px; background-color: #FFCC66"
>
<h3 id=
"data_out" style="text-align: center">
Obliczanie NWD algorytmem Euklidesa
</h3>
<p style=
"text-align: center">
(C)2004 mgr Jerzy Wałaszek&nbsp;&nbsp; I LO w Tarnowie
</p>
<hr>
<p style=
"text-align: center">
a = <input type="text" name="inp_a" size="20" value="18">
b = <input type="text" name="inp_b" size="20" value="24">
</p>
<p style=
"text-align: center">
<input type=
"button" value="Oblicz NWD(a,b)" name="B1" onclick="main();">
</p>
<p style=
"text-align: center" id="out_nwd">...</p>
</form>

<script language=javascript>

// Program znajdowania NWD algorytmem Euklidesa
// (C)2004 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//---------------------------------------------

// Funkcja NWD oblicza NWD swoich argumentów
// wykorzystując algorytm Euklidesa
//-------------------------------------------------

function NWD(a,b)
{
while(a != b) if(a > b) a -= b; else b -= a;
return(a);
}

//------------------------------------
// Tutaj rozpoczyna się program główny
//------------------------------------

function main()
{
var a,b,s;

a = parseInt(document.frmeuklides.inp_a.value);
b = parseInt(document.frmeuklides.inp_b.value);
if(isNaN(a) || isNaN(b) || (a <= 0) || (b <= 0))
s = "<font color=Red><b>ZŁE DANE</b></font>";
else
s = "NWD(" + a + "," + b + ") = " + NWD(a,b);
document.getElementById("out_nwd").innerHTML = s;
}
</script>
</div>
</body>
</html>
   
   
   

Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.

 
       

 

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Podobne artykuły


23
komentarze: 5 | wyświetlenia: 19520
49
komentarze: 18 | wyświetlenia: 64970
12
komentarze: 3 | wyświetlenia: 29777
50
komentarze: 27 | wyświetlenia: 63515
13
komentarze: 3 | wyświetlenia: 49040
11
komentarze: 13 | wyświetlenia: 13549
37
komentarze: 9 | wyświetlenia: 28511
8
komentarze: 4 | wyświetlenia: 32452
18
komentarze: 9 | wyświetlenia: 55028
17
komentarze: 4 | wyświetlenia: 14160
15
komentarze: 3 | wyświetlenia: 6804
15
komentarze: 5 | wyświetlenia: 32754
14
komentarze: 1 | wyświetlenia: 10970
 
Autor
Artykuł




Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska