[算法系列]一：递归类问题从斐波那契数列开始

作者: MachinePlay | 来源:发表于2019-05-20 15:29 被阅读0次

递归类问题

递归类问题指后续步骤都是有基本步骤叠加而成的问题。一般问题设定为做某事有n种方法x，y。。。，每次只能用其中一种，次数不限，问共有多少种方法排列组合可以造成结果R？

这类问题思想很经典，可以把问题分解成多个本原问题，变成递归问题，再将递归优化为非递归算法，我们从斐波那契数列开始讲

fibonacci数列：

$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三件事里挑一件做，其中结果加0会导致问题闭环，有无穷解，故一般问题不会有这种条件。所以我们的问题x为正整数。

现在问题就变成了：一共做了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)

算法分析

只要函数未到达递归出口（n<=2),就会不断的在现有函数栈上开辟新的空间(形参表、静态链、动态链、返回地址）。所以当递归太深的时候会出现栈溢出(stack overflow)。
可以看出n>2后，每算一个数，都要递归调用前两个数的和，而前两个也要继续向前递归,每次递归相当于是重新在原有的函数栈帧上再次开辟空间来运行函数.

递归二叉树。

二叉树的高度是 n - 1，高度为k的二叉树最多可以由 $2^k - 1$ 个叶子节点，即调用 $2^n - 1$ 次，所以时间复杂度为 $O(2^n)$ ，而空间复杂度就是树的高度 $O(n)$
算法指数级的时间复杂度，随着参数的增长很容易出现栈溢出。

一般我们认为常数、线性、多项式级别的复杂度可以忍受，而指数级的复杂度随着规模增大，计算效率急剧下降，无法应用到实际问题中。相应地，不存在多项式复杂度算法的问题，被称作难解的（intractable）问题。

非递归算法

每算一个数都要把前面的所有数重算一次，其实从头开始算，保存下末尾的两个数就好了，把递归变成迭代
优化的方法很简单，从头算就行了，每次算出的数存到队列尾部，下一个要计算的数等于末尾两个的和嘛，这样算过的就不用再算了。。。可以直接取到。。。

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('非递归结果🐶：'+str(stack[-1])+' 用时:'+str(a)+'s\n')

时间复杂度 $O(n)$ ,空间复杂度 $O(n)$
下面是对比

n	递归算法 $O(2^n)$ （计算次数/时间）	非递归算法 $O(n)$ （计算次数/时间）
10	计算109次用时:5.60e-05s	计算10次用时:9.79e-05s
20	计算13529次用时:0.0049s	计算20次用时:4.31e-05s
30	计算1664079次用时:0.27s	计算30次用时:9.51e-05s
40	计算204668309次用时:32s	计算40次用时:5.19e-05s

递归算法n=50就要等待n=40的 $2^{10}$ 倍，也就是512分钟，9个小时，而非递归只需要1e5级别的时间，万分之一秒内完成。算法何必为难算法。。。

汉诺塔也属于这类问题

例题 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

输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。

Output

对于每个测试实例，请输出不同走法的数量

Sample Input
2
2
3

Sample Output
1
2

问题分析：每次只能向上跨一级或者两级，那么到M级只有两种方法，从M-1级跨一级或者从M-2级跨两级。那么跨一级次数加一，跨两级次数也是加一。把树画出来就发现是个递归了。
$f(1)=1 跨一步算一次\\ f(2)=1跨两步算一次\\ f(m)=f(m-1)+f(m-2)$
就是一个fibonacci数列。。。
要注意三个问题

1.类型范围这一题int就够了，如果级数增加可能就需要long 等等了
2.复杂度上面我们分析过，递归必然超时，需要改成迭代或者栈方法
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

问题分析：小蜜蜂在格子每次只有两个选择：1.直接向右走一步，序号加二 2.斜着走一步序号加一

$f(1)=1 直接走算一次\\f(2)=1斜着走算一次\\f(M)=f(M-1)+f(M-2)$
注意问题：

1 从a到b相当于从1到a-b+1。
2 b大于40， $2^{40} int会越界，要用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

问题分析：问题重点在于正确推出递推公式，推出来就和就是简单的递推了。

$f(1)=3\\f(2)=6\\f(3)=6\\接下来分析f(4)的时候就发现，f(4)受前一个的结果影响。\\如果第n-1个格子与第1个格子颜色相同，那么第n个格子可以取两个颜色，此时有2*f(n-2)种\\（为什么不是2*f(n-1)？)因为格子n-1此时只能选和第1个一样的一个\\而如果第n-1个格子和第1个格子颜色不同，第n个格子将会只有1种选择此时有f(n)种\\ 所以n>3时有 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

问题分析：看起来问题变成二维的了，其实不然。骨牌只有两个并列横着放和单个竖着放两种情况。并列横着放方格长度+2，竖着放长度+1.问题就变成了每次可以走一米或者走两米，问走n米有多少种走法。也是个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三个字符串种选一个刻到牛肉串上，长度加1，两个o不能连续。问刻n个字符有多少种刻法？

$首先f(1)=3\\f(2)=8\\如果第n个字符为o，那么第n-1就只能取E、F两种，有2*f(n-2)种\\如果第n个字符串不为o，可以取E、F，则第n-1个字符就没有被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('非递归结果🐶：'+str(stack[-1])+' 计算'+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('🐷递归结果🐷：'+str(re)+' 计算'+str(numre)+'次'+' 用时:'+str(t)+'s\n')

[算法系列]一：递归类问题从斐波那契数列开始

递归类问题

fibonacci数列：

递归算法：

算法分析

非递归算法

例题 HDOJ2041 2044 2045 2046

HDOJ 2041

hdoj2044

hdoj2045 RPG难题

hdoj 2046

hdoj2047 EOF牛肉串

fibonacci 测速小脚本

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

[算法系列]一：递归类问题 从斐波那契数列开始

递归类问题

fibonacci数列：

递归算法：

算法分析

非递归算法

例题 HDOJ2041 2044 2045 2046

HDOJ 2041

hdoj2044

hdoj2045 RPG难题

hdoj 2046

hdoj2047 EOF牛肉串

fibonacci 测速小脚本

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

[算法系列]一：递归类问题从斐波那契数列开始