返回列表 發帖

遞迴函式 (二) - 費氏數列

費氏數列 - 維基百科

費氏數列規則如下:
第n項 = 第 n-1 項  + 第 n-2 項

即整個費式數列為:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377...

試完成一程式,能推算費氏數列至指定項次:

  1. #include<iostream>
  2. #include<cstdlib>
  3. using namespace std;
  4. int fai(int n)
  5. {
  6.     if(n<2)    //邊界條件
  7.         return n;
  8.     else
  9.         return fai(n-2)+fai(n-1);
  10. }
  11. /*
  12. fai(5)
  13. =fai(3)+fai(4)
  14. =fai(1)+fai(2)+fai(2)+fai(3)
  15. =1+fai(0)+fai(1)+fai(0)+fai(1)+fai(1)+fai(2)
  16. =1+0+1+0+1+1+fai(0)+fai(1)
  17. =1+0+1+0+1+1+0+1
  18. =5
  19. */
  20. int main()
  21. {
  22.     int n;
  23.     cout<<"請問要推算費氏數列到第幾項次? ";
  24.     cin>>n;
  25.     for(int i=0; i<=n; i++)
  26.         cout<<fai(i)<<" ";
  27.     cout<<endl;
  28.     system("pause");
  29.     return 0;
  30. }
複製代碼

  1. #include<iostream>
  2. #include<cstdlib>
  3. using namespace std;

  4. int count(int k)
  5. {
  6.     if(k<2)
  7.         return k;
  8.     else
  9.         k=count(k-1)+count(k-2);
  10. }
  11. int main()
  12. {
  13. int n;
  14. cout<<"計算"<<endl;
  15. cin>>n;
  16.     for(int i=0;i<=n;i++)
  17.     {
  18.         cout<<count(i);
  19.         cout<<"  ";
  20.     }

  21. }
複製代碼

TOP

返回列表