ROZŠÍŘENÝ EUCLIDŮV ALGORITMUS
V průběhu výpočtu největšího společného dělitele můžeme vypočítat celá čísla X a Y tak, aby platilo
IMPLEMENTACE
Jednotka: rekurzívní vnitřní funkce nebo vnější funkce, ale pak bez procedure příkazu
Parametry: nezáporné celé číslo A, přirozené číslo B
Vazba: funkce MOD
Vrací: řetězec tří čísel D X Y oddělených mezerami. Tato trojice splňuje výše uvedenou rovnici
EXEUCLID: procedure
parse arg A, B
if B = 0 then return A 1 0
parse value EXEUCLID(B, MOD(A, B)) with D X Y
return D Y (X - (A % B) * Y)
|
PŘÍKLAD
EXEUCLID(786, 311) vrací 1 55 -139
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
