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)

 

Funkci můžeme snadno přepsat do iterativní formy, podívejte se na kapitolu Technika: Odstranění rekurze.

 

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ýší

FORMAT(4.8*LN(B)/LN10(),,0)

 

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


Obálka Obsah Index Hlavní stránka

změněno 8. srpna 2001
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.