递归类问题
递归类问题指后续步骤都是有基本步骤叠加而成的问题。一般问题设定为做某事有n种方法x，y。。。，每次只能用其中一种，次数不限，问共有多少种方法排列组合可以造成结果R？
这类问题思想很经典，可以把问题分解成多个本原问题，变成递归问题，再将递归优化为非递归算法，我们从斐波那契数列开始讲
fibonacci数列：
可以理解为每次可以从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的二叉树最多可以由 个叶子节点，即调用
次，所以时间复杂度为
，而空间复杂度就是树的高度
算法指数级的时间复杂度，随着参数的增长很容易出现栈溢出。
一般我们认为常数、线性、多项式级别的复杂度可以忍受，而指数级的复杂度随着规模增大，计算效率急剧下降，无法应用到实际问题中。相应地，不存在多项式复杂度算法的问题，被称作难解的（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')
时间复杂度,空间复杂度
下面是对比
| 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的倍，也就是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级跨两级。那么跨一级次数加一，跨两级次数也是加一。把树画出来就发现是个递归了。
就是一个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.斜着走一步序号加一
注意问题：
- 1 从a到b相当于从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
image.png
问题分析：问题重点在于正确推出递推公式，推出来就和就是简单的递推了。
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问题。
问题就变得简单起来了。
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个字符有多少种刻法？
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')
网友评论