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.