遞歸類問題
遞歸類問題指后續(xù)步驟都是有基本步驟疊加而成的問題睬罗。一般問題設(shè)定為做某事有n種方法x，y旭斥。容达。。琉预，每次只能用其中一種董饰，次數(shù)不限，問共有多少種方法排列組合可以造成結(jié)果R圆米？
這類問題思想很經(jīng)典卒暂，可以把問題分解成多個本原問題，變成遞歸問題娄帖，再將遞歸優(yōu)化為非遞歸算法也祠，我們從斐波那契數(shù)列開始講
fibonacci數(shù)列：
可以理解為每次可以從x=0近速， x=1诈嘿， x=2三件事里挑一件做堪旧，其中結(jié)果加0會導(dǎo)致問題閉環(huán)，有無窮解奖亚，故一般問題不會有這種條件淳梦。所以我們的問題x為正整數(shù)。
現(xiàn)在問題就變成了：一共做了q次事昔字，每次從x=1 和x=2里挑一件做爆袍，共有多少種組合？（求f(q))
遞歸算法：
def fibonacci(n):
if n==1 or n==2:
return 1
else:
return fibonacci(n-1)+fibonacci(n-2)
算法分析
只要函數(shù)未到達(dá)遞歸出口（n<=2),就會不斷的在現(xiàn)有函數(shù)棧上開辟新的空間(形參表作郭、靜態(tài)鏈陨囊、動態(tài)鏈、返回地址）夹攒。所以當(dāng)遞歸太深的時候會出現(xiàn)棧溢出(stack overflow)蜘醋。
可以看出n>2后，每算一個數(shù)咏尝，都要遞歸調(diào)用前兩個數(shù)的和压语，而前兩個也要繼續(xù)向前遞歸,每次遞歸相當(dāng)于是重新在原有的函數(shù)棧幀上再次開辟空間來運(yùn)行函數(shù).
二叉樹的高度是 n - 1状土，高度為k的二叉樹最多可以由 個葉子節(jié)點(diǎn)无蜂，即調(diào)用
次，所以時間復(fù)雜度為
蒙谓，而空間復(fù)雜度就是樹的高度
算法指數(shù)級的時間復(fù)雜度斥季，隨著參數(shù)的增長很容易出現(xiàn)棧溢出。
一般我們認(rèn)為常數(shù)累驮、線性酣倾、多項(xiàng)式級別的復(fù)雜度可以忍受，而指數(shù)級的復(fù)雜度隨著規(guī)模增大谤专，計(jì)算效率急劇下降躁锡，無法應(yīng)用到實(shí)際問題中。相應(yīng)地置侍，不存在多項(xiàng)式復(fù)雜度算法的問題映之，被稱作難解的（intractable）問題。
非遞歸算法
每算一個數(shù)都要把前面的所有數(shù)重算一次蜡坊，其實(shí)從頭開始算杠输，保存下末尾的兩個數(shù)就好了，把遞歸變成迭代
優(yōu)化的方法很簡單秕衙，從頭算就行了蠢甲，每次算出的數(shù)存到隊(duì)列尾部，下一個要計(jì)算的數(shù)等于末尾兩個的和嘛据忘，這樣算過的就不用再算了鹦牛。搞糕。÷罚可以直接取到窍仰。。礼殊。
def fib(n):
a=time.time()
for i in range(n):
if i==0:
stack.append(1)
elif i==1:
stack.append(1)
else:
stack.append(stack[-1]+stack[-2])
a=time.time()-a
print('非遞歸結(jié)果??：'+str(stack[-1])+' 用時:'+str(a)+'s\n')
時間復(fù)雜度,空間復(fù)雜度
下面是對比
| n | 遞歸算法 |
非遞歸算法 |
|---|---|---|
| 10 | 計(jì)算109次 用時:5.60e-05s | 計(jì)算10次 用時:9.79e-05s |
| 20 | 計(jì)算13529次 用時:0.0049s | 計(jì)算20次 用時:4.31e-05s |
| 30 | 計(jì)算1664079次 用時:0.27s | 計(jì)算30次 用時:9.51e-05s |
| 40 | 計(jì)算204668309次 用時:32s | 計(jì)算40次 用時:5.19e-05s |
遞歸算法n=50就要等待n=40的倍辈赋，也就是512分鐘，9個小時膏燕，而非遞歸只需要1e5級別的時間，萬分之一秒內(nèi)完成悟民。算法何必為難算法坝辫。。射亏。
漢諾塔也屬于這類問題
例題 HDOJ2041 2044 2045 2046
HDOJ 2041
問題鏈接2041
Problem Description
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 87980 Accepted Submission(s): 45195
有一樓梯共M級近忙，剛開始時你在第一級，若每次只能跨上一級或二級智润，要走上第M級及舍，共有多少種走法？
Input
輸入數(shù)據(jù)首先包含一個整數(shù)N窟绷，表示測試實(shí)例的個數(shù)锯玛，然后是N行數(shù)據(jù)，每行包含一個整數(shù)M（1<=M<=40）,表示樓梯的級數(shù)兼蜈。
Output
對于每個測試實(shí)例攘残，請輸出不同走法的數(shù)量
Sample Input
2
2
3
Sample Output
1
2
問題分析：每次只能向上跨一級或者兩級，那么到M級只有兩種方法为狸，從M-1級跨一級或者從M-2級跨兩級歼郭。那么跨一級次數(shù)加一，跨兩級次數(shù)也是加一辐棒。把樹畫出來就發(fā)現(xiàn)是個遞歸了病曾。
就是一個fibonacci數(shù)列。漾根。泰涂。
要注意三個問題
- 1.類型范圍 這一題int就夠了，如果級數(shù)增加可能就需要long 等等了
- 2.復(fù)雜度 上面我們分析過立叛，遞歸必然超時负敏，需要改成迭代或者棧方法
- 3.輸出記得換行
ACcode
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int fib(int i){
int sum=0,start=0,end=0;
for (int n=1;n<=i;n++){
if (n==1){
end=1;
}
else if(n==2){
start=1;
}
else {
sum=start+end;
start=end;
end=sum;
}
}
return end;
}
int main(){
int num=0,Destination=0;
scanf("%d",&num);
for (int i=0;i<num;i++){
scanf("%d",&Destination);
printf("%d\n",fib(Destination));
}
return 0;
}
hdoj2044
hdoj2044問題鏈接
問題描述
問題分析：小蜜蜂在格子每次只有兩個選擇：1.直接向右走一步，序號加二 2.斜著走一步序號加一
注意問題：
- 1 從a到b相當(dāng)于從1到a-b+1秘蛇。
- 2 b大于40其做，
ACcode
#include <iostream>
long long go(long long n){
long long step1=0,step2=0,sum=0;
for (long long i=1;i<=n;i++){
if(i==1){
step2=1;
}
else if (n==2){
step1=1;
step2=1;
}
else{
sum=step1+step2;
step1=step2;
step2=sum;
}
}
return step2;
}
int main(){
int num=0;
long long start=0,end=0;
scanf("%d",&num);
for (int i=0;i<num;i++){
scanf("%lld %lld",&start,&end);
printf("%lld\n",go(end-start+1));
}
return 0;
}
hdoj2045 RPG難題
hdoj2045地址http://acm.hdu.edu.cn/showproblem.php?pid=2045
問題分析：問題重點(diǎn)在于正確推出遞推公式，推出來就和就是簡單的遞推了妖泄。
ACcode
#include <iostream>
#include <cstdio>
using namespace std;
long long fib(long long n){
long long temp=0,step1=0,step2=0;
for (long long i =1;i<=n;i++){
if (i==1){
step2=3;
}
else if(i==2){
step1=3;
step2=6;
}
else if(i==3){
step1=6;
step2=6;
}
else{
temp=step2;
step2=2*step1+step2;
step1=temp;
}
}
return step2;
}
int main(){
long long num=0;
while(scanf("%lld",&num)!=EOF){
printf("%lld\n",fib(num));
}
return 0;
}
hdoj 2046
骨牌鋪方格http://acm.hdu.edu.cn/showproblem.php?pid=2046
問題分析：看起來問題變成二維的了却汉，其實(shí)不然。骨牌只有兩個并列橫著放和單個豎著放兩種情況荷并。并列橫著放方格長度+2合砂，豎著放長度+1.問題就變成了每次可以走一米或者走兩米，問走n米有多少種走法源织。也是個fibonacci問題翩伪。
問題就變得簡單起來了。
ACcode
#include<iostream>
#include<cstdio>
long long queue[51]={1,2};
long long go(long long n){
if (n==1)
return 1;
if (n==2)
return 2;
for (int i=2;i<n;i++){
queue[i]=queue[i-1]+queue[i-2];
}
return queue[n-1];
}
int main(){
long long n=0;
while(~scanf("%lld",&n)){
printf("%lld\n",go(n));
}
return 0;
}
hdoj2047 EOF牛肉串
http://acm.hdu.edu.cn/showproblem.php?pid=2047
問題分析：每次可以從E谈息、O缘屹、F三個字符串種選一個刻到牛肉串上，長度加1侠仇，兩個o不能連續(xù)轻姿。問刻n個字符有多少種刻法？
ACcode
#include <iostream>
#include <cstdio>
long long chuan[41]={3,8};
long long cow(long long n){
if (n==1)
return 3;
if (n==2)
return 8;
for (int i=2;i<n;i++){
chuan[i]=2*chuan[i-2]+2*chuan[i-1];
}
return chuan[n-1];
}
int main(){
long long n=0;
while(~scanf("%lld",&n)){
printf("%lld\n",cow(n));
}
return 0;
}
fibonacci 測速小腳本
import time
stack=[]
#非遞歸寫法：（棧）
numre=0
numinre=0
def fib(n):
global numinre
a=time.time()
for i in range(n):
if i==0:
stack.append(1)
elif i==1:
stack.append(1)
else:
stack.append(stack[-1]+stack[-2])
numinre+=1
a=time.time()-a
print('非遞歸結(jié)果??：'+str(stack[-1])+' 計(jì)算'+str(numinre)+'次'+' 用時:'+str(a)+'s\n')
#遞歸寫法
def fibonacci(n):
global numre
numre+=1
if n==1 or n==2:
return 1
else:
return fibonacci(n-1)+fibonacci(n-2)
if __name__=='__main__':
print('????fibonacci遞歸與非遞歸算法速度對比\n')
x=int(input('??請輸入n：'))
fib(x)
t=time.time()
re=fibonacci(x)
t=time.time()-t
print('??遞歸結(jié)果??：'+str(re)+' 計(jì)算'+str(numre)+'次'+' 用時:'+str(t)+'s\n')
