Algorytm Euklidesa - wyznaczanie NWD

 

 

1/1 

Algorytm Euklidesa - wyznaczanie NWD.  
 
Algorytm Euklides polega na sprawdzeniu, czy dwie liczby naturalne są sobie równe. Jeżeli 
tak, to za wartość NWD przyjmuje się wartość jednej z tych liczb, jeżeli nie, to dalej algorytm 
polega  na  odejmowaniu  większej  liczby  od  mniejszej  i  przypisaniu  wyniku  zmiennej 
reprezentowanej przez odjemną. Czynność tę wykonuje się tak długo, dopóki nie otrzyma się 
dwóch liczb sobie równych. Wtedy jest to wspólny dzielnik, czyli NWD.  
 

 

 
Dane na wejściu: a, b - liczby naturalne, których NWD poszukujemy, a, b ∈ N.  
Szukane: NWD liczb a i b. 
 
Lista kroków: 
K1: 

Dopóki a ≠ b wykonuj krok K2;

   

K2: 

Jeśli a < b, to b := b - a

 

         

inaczej a := a - b; {

od większej liczby odejmujemy mniejszą aż się    

                               zrównają}

 

K3: 

Pisz a;

 

{wtedy dowolna z nich jest NWD}

 

K4: 

Zakończ

 

 
Zadanie: 
Przekształć powyższy algorytm na zapis w języku Pascal.