- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
递归式 Fibonacci 与循环式 Fibonacci 之间是否存在明显的计算时间差异?我一直使用递归将 Fibonacci 运行到 40 个位置,然后直接使用循环。似乎计算时间差异只是学术。
用 C 语言编写
递归解决方案:
int main(int argc, const char * argv[]) {
int n, i = 0, c;
printf("Please enter an integer:\n");
scanf("%d", &n);
for ( c = 1 ; c <= n ; c++ )
{
printf("%lu ", fibonacci(i));
i++;
}
return 0;
}
long fibonacci(long n)
{
if ( n == 0 )
return 0;
else if ( n == 1 )
return 1;
else
return ( fibonacci(n-1) + fibonacci(n-2) );
};
For循环解决方案:
int main(int argc, const char * argv[]) {
int n, first = 0, second = 1, next, c;
printf("Please enter an integer:\n");
scanf("%d", &n);
for ( c = 0 ; c < n ; c++ )
{
if ( c <= 1 )
next = c;
else
{
next = first + second;
first = second;
second = next;
}
printf("%d ",next);
}
return 0;
};
最佳答案
与尾递归和迭代版本相比,传统的递归方法非常慢。在下面的示例代码中,迭代版本使用展开循环和 Duff's Device进入循环。对于 32 位无符号整数,限制为 fib(47),对于 64 位无符号整数,限制为 fib(93)。
计时是使用 Intel 2600K 3.4ghz、XP X64、64 位模式完成的。 XP或XP X64高性能计数器频率与cpu时钟相同,3.4ghz,但操作系统开销(如中断),如果持续时间较小,会影响时序。
fib(40) 的时间:
fibr() # of microseconds 485468.8
fibt() # of microseconds 0.2
fibi() # of microseconds 0.2
94 次循环的计时,n = 0 到 93:
fibt() # of microseconds 7
fibi() # of microseconds 5
示例代码:
typedef unsigned long long UI64;
UI64 fibr(UI64 n)
{
if(n < 2)
return n;
return fibr(n-1) + fibr(n-2);
}
// call with fibt(n, 0, 1)
UI64 fibt(UI64 n, UI64 res, UI64 next)
{
if (n == 0)
return res;
return fibt(n - 1, next, res + next);
}
UI64 fibi(UI64 n)
{
UI64 f0, f1, i;
if(n < 2)
return n;
n -= 2;
f1 = f0 = 1;
i = 0;
switch(n%8){
do{
f1 += f0;
case 7:
f0 += f1;
case 6:
f1 += f0;
case 5:
f0 += f1;
case 4:
f1 += f0;
case 3:
f0 += f1;
case 2:
f1 += f0;
case 1:
f0 += f1;
case 0:
continue;
}while(n >= (i += 8));
}
return f0;
}
fibi() 的替代版本,没有 n<2 检查。 f0 和 f1 代表循环中的变化,旨在以 f0 中的最终和结束,因此 f0 和 f1 代表的初始状态取决于 n 是偶数还是奇数。如果 n 是偶数,则 f0 = fib(0) = 0, f1 = fib(-1) = 1,如果 n 是奇数,则 f1 = fib(0) = 0, f0 = fib(-1) = 1 。 (如果你好奇的话,fib(-1) = 1, fib(-2) = -1, fib(-3) = 2, fib(-4) = -3, fib(-5) = 5, fib(-6) = -8, ... ).
这里解释一下逻辑,对于n偶数情况,fib(-1) = f1 = 1, fib(0) = f0 = 0, 那么fib(1) = (f1 += f0), fib(2 ) = (f0 += f1), fib(3) = (f1 += f0), fib(4) = (f0 += f1), ...。
UI64 fibi(UI64 n)
{
UI64 f0, f1, i;
f0 = n & 1; // if n even, f0=0, f1=1
f1 = 1 - f0; // else f1=0, f0=1
i = 0;
switch(n%8){
do{
f1 += f0;
case 7:
f0 += f1;
case 6:
f1 += f0;
case 5:
f0 += f1;
case 4:
f1 += f0;
case 3:
f0 += f1;
case 2:
f1 += f0;
case 1:
f0 += f1;
case 0:
continue;
}while(n >= (i += 8));
}
return f0;
}
关于c - 斐波那契计算时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29087951/
我是一名优秀的程序员,十分优秀!