回 帖 发 新 帖 刷新版面

主题:欧几里德算法的递归深度

我在C算法这本书上看到,欧几里德算法的递归深度由参数的算术性质决定,提示为对数。我想了好久也没想出递归深度怎样通过对数求出来,请懂的人帮忙解答一下,谢了!

回复列表 (共2个回复)

沙发

gcd(F_n,F_{n+1})是n层,其中F_n是fibonacci数

板凳


对不起,没看懂。

参数和斐波那契数有什么关系,两个参数可以都不是斐波那契数呀?

而且我试过了,没发现递归次数和斐波那契数列中元素的个数有什么关系。我试的是书上的例子,314159和271828,递归层次为十。这两个数在斐波那契数列中的位置为:1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811,应该是第二十七位,十和二十七有什么关系?

望讲解的更细致一点,谢了。

我来回复

您尚未登录,请登录后再回复。点此登录或注册