[PHP] Jak policzyć największy wspólny dzielnik (NWD)?
Chcesz wyliczyć największy wspólny dzielnik dla podanych liczb.
Aby wyliczyć największy wspólny dzielnik wystarczy zastosować w praktyce algorytm Euklidesa, który jest z założenia algorytmem rekurencyjnym, ale nic nie stoi na przeszkodzie aby zamiast rekurencji użyć metody iteracyjnej. Zobacz jak obliczyć największy wspólny dzielnik:
function nwd($a,$b) {
while ($b<>0) {
$c=$a;
$a=$b;
$b=$c%$b;
}
return $a;
echo nwd(54,69);
Funkcja nwd() po podaniu dwóch liczb wykonuje algorytm Euklidesa w pętli, wyliczając największy wspólny dzielnik dwóch liczb.
Algorytm jest bardzo prosty. Wystarczy sprawdzić czy liczba b=0. Jeżeli tak, to największym wspólnym podzielnikiem jest liczba a i obliczenia są skończone. Jeżeli nie, wtedy za liczbę a trzeba podstawić liczbę b, a w miejsce liczby b trzeba podstawić wynik (a modulo b) i znowu sprawdzić czy b=0.
sliwak