Fibonacci數列C語言算法問題

mcmay

    請各問各位前輩，用C語言編一個程序計算出斐波那契數列的第N位數，如果不用遞歸算法而是用循環(huá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的循環(huán)程序

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 發(fā)表于 2013-03-28 18:37
搞個數組，把每個算過的值都存起來。
貼個python的循環(huán)程序

謝謝你，豐衣足食。用數組來存儲有其可取之處，不過很難確定數組的大小，因為不知程序的使用者想制定斐波那契數列中的哪一位，所以最好能夠避免使用數組。
請各位繼續(xù)不吝賜教！多謝！

mcmay

pmerofc 發(fā)表于 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)復雜度的算法；其次，算不了多少個你就會發(fā)現用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”是什么，我有些看不明白。好像是將數組元素個數往后延展，不過不知如何達到這個功能的，看起來有點像匯編的樣子。