C++基本算法思想之遞推算法思想
遞推算法是非常常用的算法思想,在數(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)題的求解算法,示例代碼如下:
/*
輸入?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)題求解代碼:
#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;
}
執(zhí)行該程序,用戶輸入12,得到如圖結(jié)果:
- C++實(shí)現(xiàn)順序排序算法簡(jiǎn)單示例代碼
- VC++實(shí)現(xiàn)選擇排序算法簡(jiǎn)單示例
- 采用C++實(shí)現(xiàn)區(qū)間圖著色問(wèn)題(貪心算法)實(shí)例詳解
- C++實(shí)現(xiàn)迷宮算法實(shí)例解析
- C++實(shí)現(xiàn)漢諾塔算法經(jīng)典實(shí)例
- C++實(shí)現(xiàn)各種排序算法類匯總
- c++實(shí)現(xiàn)MD5算法實(shí)現(xiàn)代碼
- k均值算法c++語(yǔ)言實(shí)現(xiàn)代碼
- C++泛型算法的一些總結(jié)
- C++算法之海量數(shù)據(jù)處理方法的總結(jié)分析
- C++遺傳算法類文件實(shí)例分析
相關(guān)文章
vs2022?qt環(huán)境搭建調(diào)試的方法步驟
最近net6和vs2022發(fā)布,本文就詳細(xì)的介紹一下vs2022?qt環(huán)境搭建調(diào)試的方法步驟,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-12-12StretchBlt函數(shù)和BitBlt函數(shù)用法案例詳解
這篇文章主要介紹了StretchBlt函數(shù)和BitBlt函數(shù)用法案例詳解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08C++ Easylogging++日志庫(kù)配置使用超詳細(xì)講解
這篇文章主要介紹了C++ Easylogging++日志庫(kù)配置使用,Easylogging++是用于C++應(yīng)用程序的單頭高效日志庫(kù)。它非常強(qiáng)大,高度可擴(kuò)展并且可以根據(jù)用戶的要求進(jìn)行配置2022-11-11C語(yǔ)言實(shí)現(xiàn)文件讀寫(xiě)操作的幾種常用方法
C語(yǔ)言提供了一系列文件操作函數(shù),使得我們可以通過(guò)程序?qū)ξ募M(jìn)行讀寫(xiě)操作,本文主要介紹了C語(yǔ)言實(shí)現(xiàn)文件讀寫(xiě)操作的幾種常用方法,具有一定的參考價(jià)值,感興趣的可以了解一下2024-03-03c語(yǔ)言float類型小數(shù)點(diǎn)后位數(shù)
在本篇文章里小編給大家整理了關(guān)于c語(yǔ)言float類型小數(shù)點(diǎn)后面有幾位的相關(guān)知識(shí)點(diǎn),需要的朋友們可以學(xué)習(xí)下。2020-02-02c++ 對(duì)數(shù)器實(shí)現(xiàn)示例
對(duì)數(shù)器用于在自己的本地平臺(tái)驗(yàn)證算法正確性,本文詳細(xì)的介紹了c++ 對(duì)數(shù)器實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-08-08C語(yǔ)言實(shí)現(xiàn)三子棋游戲簡(jiǎn)易版
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)三子棋游戲簡(jiǎn)易版,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-07-07C++中inet_pton、inet_ntop函數(shù)的用法
這篇文章主要介紹了C++中inet_pton、inet_ntop函數(shù)的用法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-08-08