遞歸類問題

遞歸類問題指后續(xù)步驟都是有基本步驟疊加而成的問題。一般問題設(shè)定為做某事有n種方法x，y。。。，每次只能用其中一種，次數(shù)不限，問共有多少種方法排列組合可以造成結(jié)果R？

這類問題思想很經(jīng)典，可以把問題分解成多個(gè)本原問題，變成遞歸問題，再將遞歸優(yōu)化為非遞歸算法，我們從斐波那契數(shù)列開始講

fibonacci數(shù)列：

$f(x)=\begin{cases}0，& x=0\\1,& 0< x\leq 2\\ f(x-1)+f(x-2),& x>2 \end{cases}$
可以理解為每次可以從x=0， x=1， x=2三件事里挑一件做，其中結(jié)果加0會(huì)導(dǎo)致問題閉環(huán)，有無窮解，故一般問題不會(huì)有這種條件。所以我們的問題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),就會(huì)不斷的在現(xiàn)有函數(shù)棧上開辟新的空間(形參表、靜態(tài)鏈、動(dòng)態(tài)鏈、返回地址）。所以當(dāng)遞歸太深的時(shí)候會(huì)出現(xiàn)棧溢出(stack overflow)。
可以看出n>2后，每算一個(gè)數(shù)，都要遞歸調(diào)用前兩個(gè)數(shù)的和，而前兩個(gè)也要繼續(xù)向前遞歸,每次遞歸相當(dāng)于是重新在原有的函數(shù)棧幀上再次開辟空間來運(yùn)行函數(shù).

遞歸二叉樹

。

二叉樹的高度是 n - 1，高度為k的二叉樹最多可以由 $2^k - 1$ 個(gè)葉子節(jié)點(diǎn)，即調(diào)用 $2^n - 1$ 次，所以時(shí)間復(fù)雜度為 $O(2^n)$ ，而空間復(fù)雜度就是樹的高度 $O(n)$
算法指數(shù)級的時(shí)間復(fù)雜度，隨著參數(shù)的增長很容易出現(xiàn)棧溢出。

一般我們認(rèn)為常數(shù)、線性、多項(xiàng)式級別的復(fù)雜度可以忍受，而指數(shù)級的復(fù)雜度隨著規(guī)模增大，計(jì)算效率急劇下降，無法應(yīng)用到實(shí)際問題中。相應(yīng)地，不存在多項(xiàng)式復(fù)雜度算法的問題，被稱作難解的（intractable）問題。

非遞歸算法

每算一個(gè)數(shù)都要把前面的所有數(shù)重算一次，其實(shí)從頭開始算，保存下末尾的兩個(gè)數(shù)就好了，把遞歸變成迭代
優(yōu)化的方法很簡單，從頭算就行了，每次算出的數(shù)存到隊(duì)列尾部，下一個(gè)要計(jì)算的數(shù)等于末尾兩個(gè)的和嘛，這樣算過的就不用再算了。。?？梢灾苯尤〉?。。。

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])+' 用時(shí):'+str(a)+'s\n')

時(shí)間復(fù)雜度 $O(n)$ ,空間復(fù)雜度 $O(n)$
下面是對比

n	遞歸算法 $O(2^n)$ （計(jì)算次數(shù)/時(shí)間）	非遞歸算法 $O(n)$ （計(jì)算次數(shù)/時(shí)間）
10	計(jì)算109次用時(shí):5.60e-05s	計(jì)算10次用時(shí):9.79e-05s
20	計(jì)算13529次用時(shí):0.0049s	計(jì)算20次用時(shí):4.31e-05s
30	計(jì)算1664079次用時(shí):0.27s	計(jì)算30次用時(shí):9.51e-05s
40	計(jì)算204668309次用時(shí):32s	計(jì)算40次用時(shí):5.19e-05s

遞歸算法n=50就要等待n=40的 $2^{10}$ 倍，也就是512分鐘，9個(gè)小時(shí)，而非遞歸只需要1e5級別的時(shí)間，萬分之一秒內(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級，剛開始時(shí)你在第一級，若每次只能跨上一級或二級，要走上第M級，共有多少種走法？

Input

輸入數(shù)據(jù)首先包含一個(gè)整數(shù)N，表示測試實(shí)例的個(gè)數(shù)，然后是N行數(shù)據(jù)，每行包含一個(gè)整數(shù)M（1<=M<=40）,表示樓梯的級數(shù)。

Output

對于每個(gè)測試實(shí)例，請輸出不同走法的數(shù)量

Sample Input
2
2
3

Sample Output
1
2

問題分析：每次只能向上跨一級或者兩級，那么到M級只有兩種方法，從M-1級跨一級或者從M-2級跨兩級。那么跨一級次數(shù)加一，跨兩級次數(shù)也是加一。把樹畫出來就發(fā)現(xiàn)是個(gè)遞歸了。
$f(1)=1 跨一步算一次\\ f(2)=1跨兩步算一次\\ f(m)=f(m-1)+f(m-2)$
就是一個(gè)fibonacci數(shù)列。。。
要注意三個(gè)問題

1.類型范圍這一題int就夠了，如果級數(shù)增加可能就需要long 等等了
2.復(fù)雜度上面我們分析過，遞歸必然超時(shí)，需要改成迭代或者棧方法
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問題鏈接

問題描述

image.png

問題分析：小蜜蜂在格子每次只有兩個(gè)選擇：1.直接向右走一步，序號加二 2.斜著走一步序號加一

$f(1)=1 直接走算一次\\f(2)=1斜著走算一次\\f(M)=f(M-1)+f(M-2)$
注意問題：

1 從a到b相當(dāng)于從1到a-b+1。
2 b大于40， $2^{40} int會(huì)越界，要用long long$

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

image.png

問題分析：問題重點(diǎn)在于正確推出遞推公式，推出來就和就是簡單的遞推了。

$f(1)=3\\f(2)=6\\f(3)=6\\接下來分析f(4)的時(shí)候就發(fā)現(xiàn)，f(4)受前一個(gè)的結(jié)果影響。\\如果第n-1個(gè)格子與第1個(gè)格子顏色相同，那么第n個(gè)格子可以取兩個(gè)顏色，此時(shí)有2*f(n-2)種\\（為什么不是2*f(n-1)？)因?yàn)楦褡觧-1此時(shí)只能選和第1個(gè)一樣的一個(gè)\\而如果第n-1個(gè)格子和第1個(gè)格子顏色不同，第n個(gè)格子將會(huì)只有1種選擇此時(shí)有f(n)種\\ 所以n>3時(shí)有 f(n)=2*f(n-2)+f(n-1)$
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í)不然。骨牌只有兩個(gè)并列橫著放和單個(gè)豎著放兩種情況。并列橫著放方格長度+2，豎著放長度+1.問題就變成了每次可以走一米或者走兩米，問走n米有多少種走法。也是個(gè)fibonacci問題。

$f(1)=1一塊骨牌豎著擺\\f(2)=2 兩塊骨牌橫著放\\f(m)=f(m-1)+f(m+1)$
問題就變得簡單起來了。
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三個(gè)字符串種選一個(gè)刻到牛肉串上，長度加1，兩個(gè)o不能連續(xù)。問刻n個(gè)字符有多少種刻法？

$首先f(1)=3\\f(2)=8\\如果第n個(gè)字符為o，那么第n-1就只能取E、F兩種，有2*f(n-2)種\\如果第n個(gè)字符串不為o，可以取E、F，則第n-1個(gè)字符就沒有被n限制，有2*f(n-1)種\\所以f(n)=f(n-1)+f(n-2)$
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)+'次'+' 用時(shí):'+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)+'次'+' 用時(shí):'+str(t)+'s\n')

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

[算法系列]一：遞歸類問題從斐波那契數(shù)列開始

[算法系列]一：遞歸類問題從斐波那契數(shù)列開始

遞歸類問題

fibonacci數(shù)列：

遞歸算法：

算法分析

非遞歸算法

例題 HDOJ2041 2044 2045 2046

HDOJ 2041

hdoj2044

hdoj2045 RPG難題

hdoj 2046

hdoj2047 EOF牛肉串

fibonacci 測速小腳本

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

[算法系列]一：遞歸類問題 從斐波那契數(shù)列開始

遞歸類問題

fibonacci數(shù)列：

遞歸算法：

算法分析

非遞歸算法

例題 HDOJ2041 2044 2045 2046

HDOJ 2041

hdoj2044

hdoj2045 RPG難題

hdoj 2046

hdoj2047 EOF牛肉串

fibonacci 測速小腳本

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

[算法系列]一：遞歸類問題從斐波那契數(shù)列開始