主题:欧几里德算法的递归深度
khejing
[专家分:0] 发布于 2009-04-06 23:51:00
我在C算法这本书上看到,欧几里德算法的递归深度由参数的算术性质决定,提示为对数。我想了好久也没想出递归深度怎样通过对数求出来,请懂的人帮忙解答一下,谢了!
回复列表 (共2个回复)
沙发
FancyMouse [专家分:13680] 发布于 2009-04-07 05:32:00
gcd(F_n,F_{n+1})是n层,其中F_n是fibonacci数
板凳
khejing [专家分:0] 发布于 2009-04-09 23:43:00
对不起,没看懂。
参数和斐波那契数有什么关系,两个参数可以都不是斐波那契数呀?
而且我试过了,没发现递归次数和斐波那契数列中元素的个数有什么关系。我试的是书上的例子,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,应该是第二十七位,十和二十七有什么关系?
望讲解的更细致一点,谢了。
我来回复