算法基礎二 遞推法

</pre><pre name="code" class="cpp">/*遞推法*/
/*斐波那契數列 1 1 2 3 5 8 13..... f(n)?*/
//遞推法的特點是由前向後推算，是以注意起始條件，并在推算過程中儲存結果供下一步推算使用~
#include<iostream>
using namespace std;
int f1(int n)
{
  if (n < 3) return 1;
  else
  {
     int t1 = 1; int t2 = 1;
     for (int i = 2; i < n; i++)
     {
       int temp = t1 + t2;
       t2 = t1;
       t1 = temp;
     }
     return t1;
  }
}
//提供遞歸算法對比，相較而言遞歸法更簡單,我們下一次詳細讨論~
int febonacci(int n)
{
   if (n < 3) return 1;
   else return febonacci(n - 2) + febonacci(n - 1);
}
int main()
{
 int n;
 cout << "請輸入f(n)序列n" << endl;cin >> n;
 cout << "遞推法：f(" << n << ")=" << f1(n)<<endl;
 cout << "遞歸法：f(" << n << ")=" << febonacci(n) << endl;
}