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)

.