啊哈磊_编程从这里起步
标题:
挑战4
[打印本页]
作者:
rosynirvana
时间:
2013-11-4 14:56
标题:
挑战4
很经典的问题,经常被用来演示DP
首先是一种很糟糕的递归解法
我不知道第45项有没有超过int32的范围,但是记得90多项才超过int64,所以这里姑且先用long long int
递归是一种计算科学中很重要的方法,如果你不熟悉而又对计算科学有兴趣,那么就请多花点时间去熟悉它
#include <stdio.h>
long long int fib(int);
int main()
{
printf("%lld", fib(45));
return 0;
}
long long int fib(int n)
{
if(n == 1)
return 1;
if(n == 2)
return 1;
return fib(n-1) + fib(n-2);
}
复制代码
这段代码在我的机器上用了将近11秒,因为存在大量的重复计算,例如计算第五项,那么要重新计算第四项和第三项,计算第四项又要计算第三项和第二项
但是之前第四项和第三项都已经计算过了,为了除掉这些重复计算,用一个数组把之前计算过的都保存起来:
因为已经知道不会溢出,所以这里就改用int了
去掉重复运算后,运行时间可以忽略
这是我比较喜欢的解法,代码的含义一眼就能看出来,如果问题还要求小于45的其他项,可以直接在这个数组中查询
#include <stdio.h>
int main()
{
int i;
int fib[45 + 1];
fib[1] = 1;
fib[2] = 1;
for(i = 3; i != 45+1; ++i)
fib[i] = fib[i-1] + fib[i-2];
printf("%d\n", fib[45]);
return 0;
}
复制代码
当然,递归也是可以的,用函数的参数来保存前两项,从而避免重复运算
但是对于C和其他命令式语言而言,递归的写法没有那么自然,运行效率也必然低一些(这个问题上看不出)
#include <stdio.h>
int fib(int);
int _fib(int, int, int, int);
int main()
{
printf("%d\n", fib(45));
return 0;
}
int fib(int n)
{
if(n == 1 || n == 2)
return 1;
return _fib(1, 1, 1, n-2);
}
int _fib(int a, int b, int n, int des)
{
if(n == des)
return a+b;
else
return _fib(b, a+b, n+1, des);
}
复制代码
最后,如果要尽可能地节省内存,而且只要求45项这一个解,可以这么写
#include <stdio.h>
int main()
{
int a = 1;
int b = 1;
int pos = 3;
while(pos <= 45){
b = a + b;
a = b - a;
pos += 1;
}
printf("%d\n", b);
return 0;
}
复制代码
为什么?因为计算第n项,只需要第n-1项和第n-2项,所以无论何时保存两项就够了
最后,求斐波那契数列的第n项可以转化为矩阵乘法,((0 1) (1 1)) ^( n - 2 )
因为乘方可以二分计算,对于大数来说是最理想的方法
但对于这道题目中的小数字,矩阵乘法反而会慢一点,而且代码也会复杂很多
对于这个问题,代码4是最佳解法
欢迎光临 啊哈磊_编程从这里起步 (https://bbs.codeaha.com/)
Powered by Discuz! X3.2