JustPaste.it

Liczby pierwsze - algorytm Euklidesa

2f198c5833f3651bcafd3c545530a84a.gif
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.

17d9347d04b9bd4db9f11144dc81afa3.gif

Dane wejściowe

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

Dane wyjściowe

Liczba naturalna równa NWD(a,b)

1c7e6716bfd6906c939af1d07a440f2b.gif

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

3884acf4a0f0612e8bd089539eb167d8.gif

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?


83d646ed92c73b107c3ace182ceadd9c.gif
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>
e4e2299e3856a0ac7e28ffdc92cac115.gif    
   
   

61cfded62dcc78e7826a64b717ef9354.gif

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.

 

Źródło: mgr Jerzy Wałaszek

liczby programy technologia rady programowanie algorytm