C++基本算法思想之遞推算法思想

2020-01-26 15:45:07

字體：大中小

來源：轉載

供稿：網友

遞推算法是非常常用的算法思想，在數學計算等場合有著廣泛的應用。遞推算法適合有明顯公式規律的場合。

遞推算法基本思想
遞推算法是一種理性思維莫斯的代表，根據已有的數據和關系，逐步推到而得到結果。遞推算法的執行過程如下：

（1）根據已知結果和關系，求解中間結果。

（2）判斷是否達到要求，如果沒有達到，則繼續根據已知結果和關系求解中間結果。如果滿足要求，則表示尋找到一個正確答案。

遞推算法需要用戶知道答案和問題之間的邏輯關系。在許多數學問題中，都有明確的計算公式可以遵循，因此可以采用遞推算法來實現。

遞推算法示例
數學里面的斐波那契數列是一個使用遞推算法的經典例子。

13世紀意大利數學家斐波那契的《算盤書》中記載了典型的兔子產仔問題，其大意如下：

如果一對一個月大的兔子以后每一個月都可以生一對小兔子，而一對新生的兔子出生兩個月才可以生出小兔子。也就是，1月份出生，3月份開始產仔。那么假定一年內沒有產生兔子死亡事件，那么1年之后共有多少對兔子呢？

1.遞歸算法
我們來分析一下兔子產仔問題。我們先逐月看每月兔子的對數。

第一個月：1對兔子；

第二個月：1對兔子；

第三個月：2對兔子；

第四個月：3對兔子；

第五個月：5對兔子；

第六個月：8對兔子；

………………

從上面可以看出，從第三個月開始，每個月的兔子總對數等于前兩個月兔子數的總和。相應的計算公式如下：

第n個月兔子總數Fn=Fn-1+Fn-2。

這里初始第一個月的兔子數F1=1，第二個月的兔子數F2=1。

可以用遞歸公式來求解。為了通用型的方便，我們可以編寫一個算法，用于計算斐波那契數列問題，按照這個思慮來編寫相應的兔子產仔問題的求解算法，示例代碼如下：

復制代碼代碼如下:

/*
輸入參數n為經歷的時間（單位是月），程序中通過遞歸調用來實現斐波那契數列的計算。
*/ 
int Fibonacci(n)
{
 int t1,t2;
 if(n>0)
 {
  if(n==1||n==2)
  {
   return 1;
  }
  else
  {
   t1=Fibonacci(n-1);
   t2=Fibonacci(n-2);
   return t1+t2;
  } 
 }
 else
 {
  return 0;
 }
}

遞歸算法求解兔子產仔問題
有了上述通過的兔子產仔問題算法后，我們可以求解任意的此類問題。這里給出完整的兔子產仔問題求解代碼：

復制代碼代碼如下:

#include<iostream>
using namespace std;
/*
輸入參數n為經歷的時間（單位是月），程序中通過遞歸調用來實現斐波那契數列的計算。
*/ 
int Fibonacci(int n)
{
 int t1,t2;
 if(n>0)
 {
  if(n==1||n==2)
  {
   return 1;
  }
  else
  {
   t1=Fibonacci(n-1);   //遞歸調用獲取F(n-1) 
   t2=Fibonacci(n-2);   //遞歸調用獲取F(n-2) 
   return t1+t2;
  } 
 }
 else
 {
  return 0;
 }
}
int main()
{
 int n,num;
 cout<<"遞推算法求解兔子產仔問題："<<endl;
 cout<<"請輸入時間："<<endl;
 cin>>n;
 num=Fibonacci(n);
 cout<<"經過"<<n<<"個月之后"<<endl;
 cout<<"兔子的數量為："<<num<<"對"<<endl;
 return 0; 
}