EUKLIDŮV ALGORITMUS PRO VÝPOČET NSD/NSN
NSD
Jsou dána dvě celá čísla. Největší celé číslo, které je dělitelem každého z nich, nazýváme jejich největší společný dělitel (NSD, anglicky GCD, tj. Greatest Common Divisor). Definitoricky NSD(0,0)=0. Následující rovnice ukazují,
NSD(A,B)=NSD(B,A)
NSD(A,B)=NSD(-A,B)
NSD(A,0)=ABS(A)
|
že můžeme uvažovat jen nezáporné hodnoty A a B.
ALGORITMUS
Eukleidos popsal tento algoritmus ve své knize Základy (kolem r. 300 před n. l.). Algoritmus je založen na platnosti rekurzívního vztahu:
NSD(A,B)=NSD(B,A//B)
IMPLEMENTACE
Jednotka:
rekurzívní vnitřní funkce nebo vnější funkce, ale pak bez procedure příkazu
Parametry: nezáporné číslo A, nezáporné číslo B
Vrací: NSD(A,B)
NSD: procedure
parse arg A, B
if B = 0 then return A
else return NSD(B, A // B)
|
NSD: procedure
parse arg A, B
do while B > 0
parse value(B A//B) with A B
end
return A
|
Nejhorší případ nastane, když A a B jsou dvě po sobě následující Fibonacciho čísla. Počet průchodů cyklem ale nikdy nepřevýší
NSN
Nejmenší společný násobek NSN (anglicky LCM - least common multiple) dvou celých čísel A a B je nejmenší kladné celé číslo, které je násobkem jak čísla A tak i čísla B.
ALGORITMUS
Rovnice A*B=NSD(A,B)*NSN(A,B) redukuje výpočet NSN na výpočet NSD.
NSN: procedure
parse arg A, B
return A * B / NSD(A, B)
|
SOUVISLOSTI
Literatura Knuth D. E., Seminumerical Algorithms, vol. 2 of The Art of Computer Programming Addison-Wesley, 1973
Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms The MIT Press, Cambridge, 1990
|
