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

D=NSD(A,B)=A*X+B*Y

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


Obálka Obsah Index Hlavní stránka

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