Fibonacci数列C语言算法问题

mcmay

    请各问各位前辈，用C语言编一个程序计算出斐波那契数列的第N位数，如果不用递归算法而是用循环的话，应该如何实现呢（最好也不用数组）？我想了一个下午都没有任何进展，请各位帮忙看看。感激不尽！
   下面我做了个函数调用的测试，但关键部位还是想不出来。

1. #include <stdio.h>
   
2. 
   
3. unsigned long test_fibonacci(int n);
   
4. 
   
5. 
   
6. int main(void)
   
7. {
   
8.     int n;
   
9.    
   
10.     printf("Enter a positive integer (q to quit): ");
    
11.     while(scanf("%d", &n) == 1)
    
12.     {
    
13.         printf("\nThe %dth number in the fibonacci numbers is %lu",
    
14.                n, test_fibonacci(n));
    
15.         printf("\nEnter a positive integer (q to quit): ");
    
16.     }
    
17.     puts("\nDone!");
    
18. 
    
19.     return 0;
    
20. }
    
21. 
    
22. unsigned long test_fibonacci(int n)
    
23. {
    
24.     int i, sum = 0;
    
25. 
    
26.     if(n <= 2)
    
27.         sum = 1;
    
28.     else
    
29.         for(i = 2; i <= n; i++)
    
30.         {
    
31.         }
    
32. 
    
33.     return sum;
    
34. }

复制代码

windoze

搞个数组，把每个算过的值都存起来。
贴个python的循环程序

1. f=[0,1]
   
2. for n in range(2, 10):
   
3.         f.append(f[n-1]+f[n-2])
   
4. print f[-1]
   

复制代码

mcmay

windoze 发表于 2013-03-28 18:37
搞个数组，把每个算过的值都存起来。
贴个python的循环程序

谢谢你，丰衣足食。用数组来存储有其可取之处，不过很难确定数组的大小，因为不知程序的使用者想制定斐波那契数列中的哪一位，所以最好能够避免使用数组。
请各位继续不吝赐教！多谢！

mcmay

pmerofc 发表于 2013-03-28 18:43
回复 1# mcmay

你好，pmerofc。就是说，比如：1 1 2 3 5 8 13 21 ...，如果N = 3就是2，N = 6就是8，等等。谢谢！

windoze

回复 3# mcmay

其实这个问题远比你想象的麻烦，首先，只要你用的是递推公式，把N之前的所有项都算一遍是不可避免的，如果你不存中间结果，那将会是一个O(2^n)复杂度的算法；其次，算不了多少个你就会发现用int之类的类型存不下了，还得搞个大整数的库神马的。

folklore

这个很简单吧

1. #include <stdio.h>
   
2. 
   
3. unsigned long fibonacci(unsigned long N){
   
4.         unsigned long ar[] ={0UL,1UL,1UL,2UL};
   
5.         unsigned long iAnswer =0;
   
6.         for(iAnswer =1UL;iAnswer <N;iAnswer++){
   
7.                 ar[(iAnswer +1)&0x03UL] =ar[(iAnswer -1)&0x03UL] +ar[iAnswer&0x03UL];       
   
8.         }
   
9.         return ar[iAnswer&0x03UL];
   
10. }
    
11. 
    
12. int main(void){
    
13.         for(unsigned long iN =1;iN <20; iN++){
    
14.                 printf("%ld ",fibonacci(iN));
    
15.         }
    
16.         return 0;
    
17. }

复制代码

mcmay

听君一席话，胜读十年书。楼上几位的点拨让我茅塞顿开！尤其是pmerofc和folklore两位仁兄的代码解析，迭代法在此又展神威。还请folklore说一下代码中“&0x03UL”是什么，我有些看不明白。好像是将数组元素个数往后延展，不过不知如何达到这个功能的，看起来有点像汇编的样子。