Algorytm NWD

Prezentacja zawiera 

Specyfikację, Schemat 

Blokowy i Opis Słowny NWD

Schemat Blokowy 

Algorytmu NWD

Start

a,b

A =b

?

Druk NWD(a,b)

Stop

a>b

T

N

b:=b-a

a:=a-b

Specyfikacja

Obliczanie 
NWD (a,b) , a,b C
Algorytm Euklidesa
1.Pobierz a,b
2.J. A=b, to NWD=a
3.J. A>b, to za a podstaw a-b i p.2
4.J. A<b , to za b podstaw b-a i p.2
5.Zapisz wynik i zakończ

Opis słowny Algorytmu 

NWD

Po odczytaniu wartości liczb a i b rozpoczyna się pętla 
warunkowa.  Warunek  kontynuacji  jest  spełniony,  gdy 
reszta  z  dzielenia  a  przez  b  jest  różna  od  zera  (w 
pierwszym  obiegu  będzie  on  zawsze  spełniony).  W 
takim  przypadku  nie  osiągnęliśmy  jeszcze  NWD. 
Obliczamy  zatem  resztę  z  dzielenia  a  przez  b.  Wynik 
umieszczamy  w  dzielniku  b,  poprzedni  dzielnik  b 
przenosimy  do  a.  Jest  to  zwykła  operacja  wymiany 
zawartości 

dwóch 

zmiennych, 

zatem 

wymaga 

dodatkowej  zmiennej  pomocniczej  x.  Po  wykonaniu 
tych  działań  pętla  jest  kontynuowana,  aż  do 
osiągnięcia reszty 0.
Gdy  osiągniemy  resztę  0,  algorytm  kończy  działanie 
zwracając  dzielnik 

(zwróć  uwagę,  iż  faktycznie 

zwracana  jest  zawartość  zmiennej  b  -  dzielnika, 
ponieważ  w  poprzednim  obiegu  pętli  zmienne  a  i  b 
zostały zamienione miejscami)

.