关于recursive求fibonacci求助

recursive算fibonacci很慢。 于是，我想找个办法改进他。 发现recursive算法有很多重复的运算。 我变用hash来去重。 可是，不知道为什么。 47之前都是正确的，从47往后出现了负数。 这是什么原因呢？ 求大神帮忙看下~

1. int  fib(int n, myhash &h){
   
2.    
   
3.         if(n==0) {
   
4.                 h[0] = 0;
   
5.                 return h[n];
   
6.         }
   
7.         if(n==1) {
   
8.                 h[1] = 1;
   
9.                 return h[n];
   
10.         }
    
11.         if(n==2){
    
12.                 h[2] = 1;
    
13.                 return h[n];
    
14.         }
    
15.    
    
16.         myhash::iterator iter1 = h.find(n-1);
    
17.         myhash::iterator iter2 = h.find(n-2);
    
18.         if(iter1 != h.end()&&iter2 !=h.end()){
    
19.                  h[n] = h[n-1]+h[n-2];
    
20.              return h[n];
    
21.         }else if(iter1 == h.end()&&iter2 !=h.end()){
    
22.                 h[n] = fib(n-1,h) + h[n-2];
    
23.                 return h[n];
    
24.         }else if(iter1 != h.end()&&iter2 ==h.end()){
    
25.                 h[n] = h[n-1] + fib(n-2,h);
    
26.             return h[n];
    
27.         }else if(iter1 == h.end()&&iter2 ==h.end()){
    
28.                 h[n] = fib(n-1,h)+fib(n-2,h);
    
29.                 return h[n];
    
30.         }
    
31. }
    
32. 
    
33. int myfib(int n){
    
34.     myhash h;
    
35.     return fib(n, h);
    
36. }
    

复制代码

LZ贴出来的代码都没问题，能不能把你的myhash类拿出来看看？个人强烈怀疑是因为处理散列冲突的方式有问题。
另外这个东西不适合用递归啊。最简单的for (i=2,i<=n;i++) h=h[i-1]+h[i-2];就可以了吧
另外这个数列是可以直接用公式算的，有兴趣的话可以百度～

lunaughty 发表于 2012-12-7 17:20
LZ贴出来的代码都没问题，能不能把你的myhash类拿出来看看？个人强烈怀疑是因为处理散列冲突的方式有问题。 ...

斐波那契的公式长得太难看了

看看是不是超出整形范围溢出了？

你看看fib(47)有多大就知道了。。就算换成double，也多算不了几个。。

msallk 发表于 2012-12-8 03:19
你看看fib(47)有多大就知道了。。就算换成double，也多算不了几个。。

确实是超出范围了。  谢谢

geniusroger2000 发表于 2012-12-8 03:12
看看是不是超出整形范围溢出了？

谢谢，是超出范围了

lunaughty 发表于 2012-12-7 17:20
LZ贴出来的代码都没问题，能不能把你的myhash类拿出来看看？个人强烈怀疑是因为处理散列冲突的方式有问题。 ...

用的是c++自己的hash

為什麼不用Iterative呢？

int fib(int n)
{
    int a=1;
    int b=1;
    int c;
    if(n<=2) return 1;
   
    for(i=3;i<=n;i++){
        c=a+b;
        a=b;
        b=c;
    }
    return c;

}