Wyznaczenie największego wspólnego dzielnika (NWD) liczb A i B
Istnieją różne algorytmy rozwiązujące niniejszy problem.
Klasykę rozwiązań stanowi opisywany w większości książek algorytm Euklidesa
wykorzystujący kolejne dzielenie całkowite ( dzielenie z resztą ) liczb.
Przedstawiony algorytm jest modyfikacją klasycznego algorytmu Euklidesa.
Polega na szukaniu różnicy dwóch liczb (gdy są różne).
W kolejnym etapie większa liczba zostaje odrzucona i rozpatrywane są uzyskana różnica
i mniejsza liczba. Gdy uzyskana zostanie równość to jako NWD przyjęta zostaje
jedna z ostatecznie porównywanych liczb. Np. NWD (18, 30) = 6, gdyż:
18 - 12 = 6
12 - 6 = 6
6 = 6
Darmowy hosting zapewnia PRV.PL