腳本之家服務(wù)器常用軟件

快捷導(dǎo)航

軟件下載

android MAC 驅(qū)動(dòng)下載字體下載 DLL

源碼下載

PHP ASP.NET ASP JSP

軟件編程

C# JAVA C 語(yǔ)言 Delphi Android

網(wǎng)絡(luò)編程

PHP ASP.NET ASP JavaScript

在線工具

CSS格式化 JS格式化 Html轉(zhuǎn)化為Js

數(shù)據(jù)庫(kù)

MYSQL MSSQL oracle DB2 MARIADB

CMS

PHPCMS DEDECMS 帝國(guó)CMS WordPress

常用工具

PHP開(kāi)發(fā)工具 python Photoshop 必備軟件

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

更新時(shí)間：2013年10月14日 08:56:49 作者：

遞推算法需要用戶知道答案和問(wèn)題之間的邏輯關(guān)系。在許多數(shù)學(xué)問(wèn)題中，都有明確的計(jì)算公式可以遵循，因此可以采用遞推算法來(lái)實(shí)現(xiàn)

遞推算法是非常常用的算法思想，在數(shù)學(xué)計(jì)算等場(chǎng)合有著廣泛的應(yīng)用。遞推算法適合有明顯公式規(guī)律的場(chǎng)合。

遞推算法基本思想
遞推算法是一種理性思維莫斯的代表，根據(jù)已有的數(shù)據(jù)和關(guān)系，逐步推到而得到結(jié)果。遞推算法的執(zhí)行過(guò)程如下：

（1）根據(jù)已知結(jié)果和關(guān)系，求解中間結(jié)果。

（2）判斷是否達(dá)到要求，如果沒(méi)有達(dá)到，則繼續(xù)根據(jù)已知結(jié)果和關(guān)系求解中間結(jié)果。如果滿足要求，則表示尋找到一個(gè)正確答案。

遞推算法需要用戶知道答案和問(wèn)題之間的邏輯關(guān)系。在許多數(shù)學(xué)問(wèn)題中，都有明確的計(jì)算公式可以遵循，因此可以采用遞推算法來(lái)實(shí)現(xiàn)。

遞推算法示例
數(shù)學(xué)里面的斐波那契數(shù)列是一個(gè)使用遞推算法的經(jīng)典例子。

13世紀(jì)意大利數(shù)學(xué)家斐波那契的《算盤書(shū)》中記載了典型的兔子產(chǎn)仔問(wèn)題，其大意如下：

如果一對(duì)一個(gè)月大的兔子以后每一個(gè)月都可以生一對(duì)小兔子，而一對(duì)新生的兔子出生兩個(gè)月才可以生出小兔子。也就是，1月份出生，3月份開(kāi)始產(chǎn)仔。那么假定一年內(nèi)沒(méi)有產(chǎn)生兔子死亡事件，那么1年之后共有多少對(duì)兔子呢？

1.遞歸算法
我們來(lái)分析一下兔子產(chǎn)仔問(wèn)題。我們先逐月看每月兔子的對(duì)數(shù)。

第一個(gè)月：1對(duì)兔子；

第二個(gè)月：1對(duì)兔子；

第三個(gè)月：2對(duì)兔子；

第四個(gè)月：3對(duì)兔子；

第五個(gè)月：5對(duì)兔子；

第六個(gè)月：8對(duì)兔子；

………………

從上面可以看出，從第三個(gè)月開(kāi)始，每個(gè)月的兔子總對(duì)數(shù)等于前兩個(gè)月兔子數(shù)的總和。相應(yīng)的計(jì)算公式如下：

第n個(gè)月兔子總數(shù)Fn=Fn-1+Fn-2。

這里初始第一個(gè)月的兔子數(shù)F1=1，第二個(gè)月的兔子數(shù)F2=1。

可以用遞歸公式來(lái)求解。為了通用型的方便，我們可以編寫(xiě)一個(gè)算法，用于計(jì)算斐波那契數(shù)列問(wèn)題，按照這個(gè)思慮來(lái)編寫(xiě)相應(yīng)的兔子產(chǎn)仔問(wèn)題的求解算法，示例代碼如下：

復(fù)制代碼代碼如下:

/*
輸入?yún)?shù)n為經(jīng)歷的時(shí)間（單位是月），程序中通過(guò)遞歸調(diào)用來(lái)實(shí)現(xiàn)斐波那契數(shù)列的計(jì)算。
*/ 
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;
 }
}

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

復(fù)制代碼代碼如下:

#include<iostream>
using namespace std;
/*
輸入?yún)?shù)n為經(jīng)歷的時(shí)間（單位是月），程序中通過(guò)遞歸調(diào)用來(lái)實(shí)現(xiàn)斐波那契數(shù)列的計(jì)算。
*/ 
int Fibonacci(int n)
{
 int t1,t2;
 if(n>0)
 {
  if(n==1||n==2)
  {
   return 1;
  }
  else
  {
   t1=Fibonacci(n-1);   //遞歸調(diào)用獲取F(n-1) 
   t2=Fibonacci(n-2);   //遞歸調(diào)用獲取F(n-2) 
   return t1+t2;
  } 
 }
 else
 {
  return 0;
 }
}
int main()
{
 int n,num;
 cout<<"遞推算法求解兔子產(chǎn)仔問(wèn)題："<<endl;
 cout<<"請(qǐng)輸入時(shí)間："<<endl;
 cin>>n;
 num=Fibonacci(n);
 cout<<"經(jīng)過(guò)"<<n<<"個(gè)月之后"<<endl;
 cout<<"兔子的數(shù)量為："<<num<<"對(duì)"<<endl;
 return 0; 
}