我实现了以下版本的扩展Euclid算法:
long gcdex(const long& a, const long& b, long& x, long& y)
{
if (a == 0) {
x = 0; y = 1;
return b;
}
long x1, y1;
long d = gcdex(b % a, a, x1, y1);
x = y1 - (b / a) * x1;
y = x1;
return d;
}
我不知道实现它的非递归版本很热,您能帮我吗?
可以使用迭代和附加堆栈将任何递归算法实现为非递归。尽管如此,这仍将导致某些算法的可读性大大降低,并且可能无法提高效率。
我喜欢您的算法版本-它简短易读(尽管您可能需要重命名一些变量),并且它为您提供了算法的最佳复杂性。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句