递归在解决一些问题的时候非常直观,但是在是使用递归的时候要注意递归的深度,如果深度太深,可能会造成堆栈溢出。下面通过实例介绍如何使用。
题目:超级楼梯
Problem Description
有一楼梯共M级,刚开始时你在第一级,若每次只能跨上一级或二级,要走上第M级,共有多少种走法?
Input
输入数据首先包含一个整数N,表示测试实例的个数,然后是N行数据,每行包含一个整数M(1<=M<=40),表示楼梯的级数。
Output
对于每个测试实例,请输出不同走法的数量
Sample Input
2
2
3
Sample Output
1
2
解题思路:这类题目首先要找到规律,可以试着写出M比较少的情况,然后从中找规律。例如:
M走法
1
2 1-2
3 1-3(从1走两级)1-2-3(从2走一级)
4 1-2-4(从2走两级) 1-2-3-4 1-3-4(从3走一级)
5 1-2-3-5 1-3-5(从3走两级) 1-2-3-4-5 1-2-4-5 1-3-4-5(从4走一级)
6 1-2-4-6 1-2-3-4-6 1-3-4-6(从4走两级)
1-2-3-5-6 1-3-5-6 1-2-3-4-5-6 1-2-4-5-6 1-3-4-5-6(从5走一级)
…
n n-2层的所有走法走两级可以到达n层,n-1层的所有走法走一级可以到达n层
n层的走法可以表示为f(n),则f(n)=f(n-1)+f(n-2),n>4
这样就可以用递归计算了。参考代码如下:
/*
* 超级楼梯
*/
public static int test7(int n){
switch(n){
case 1:return 0;
case 2:return 1;
case 3:return 2;
default:return test7(n-1)+test7(n-2);
}
}
对于这种题目来说,使用递归速度并不快,并且递归太深的话会溢出,可以采用循环来处理,可以参考下面的代码:
/*
* 超级楼梯
*/
public static int test7(int n){
int[] result = new int[40];
result[0] = 0;
result[1] = 1;
result[2] = 2;
for(int i=3;i<n;i++){
result[i] = result[i-1]+result[i-2];
}
return result[n-1];
}
李绪成 CSDN Blog:http://blog.csdn.net/javaeeteacher
CSDN学生大本营:http://student.csdn.net/space.php?uid=124362
如果喜欢我的文章,就加我为好友:http://student.csdn.net/invite.php?u=124362&c=7be8ba2b6f3b6cc5
分享到:
相关推荐
acm图论.ppt————电子版_ppt版
ACM 模版ACM 模版ACM 模版ACM 模版
几套 ACM题集,对学C或参赛的都由很大的帮助,大家多做题哦!!
这个ppt主要介绍蛮力搜索的相关内容,这是我竞赛培训的资料,欢迎大家来下载
acm递归算法总结acm递归算法总结!!!!!!!!!!!!!!!!!!!!!!!
几道简单的编程题 我没有积分了 我要下东西
适合初学者ACM们,能够让大家提高自己的学习技术与水平,十分实用。
ACM培训基础算法之递归PPT详解 包括递归的一些基础思想和一些经典例题
本次课程论文,针对ACM比赛中的经典算法,动态规划,进行了详细的讲述,并以ZOJ和POJ上的经典题目为例,讲述了动态规划算法的应用。
hdu ACM 高级程序设计习题集——全文 里面有程序的详细解释
蓝桥杯ACM算法比赛模拟题30天每日训练
是一个可执行的文件,需要opencv3.3.0的环境配置。对于研究活动轮廓模型算法的人很有帮助。
acm/icpc 课件 贪心 递归 图论 最大矩阵乘积 acm/icpc 课件 贪心 递归 图论 最大矩阵乘积 acm/icpc 课件 贪心 递归 图论 最大矩阵乘积 acm/icpc 课件 贪心 递归 图论 最大矩阵乘积 acm/icpc 课件 贪心 递归 图论 ...
湖师院ACM算法设计与分析 1.Permutation with Repetition 2.双色Hanoi塔问题 3.Search Number 4.整数划分问题 5.Counting(Extreme) 6.Integer Factorization 7.输油管道问题 8.再次Hanoi塔问题 . .
ACM教材,递归与分治。想参加ACM的可以参考一下
ACM国际大学生程序设计竞赛模拟试题,感兴趣的可以做做~~~
ACM滑雪问题详解(PDF),以及代码和算法介绍!!
一 个报告,新手用 没什么用的 随便看看个报告,新手用 没什么用的 随便看看个报告,新手用 没什么用的 随便看看
中南大学第三届ACM校赛题详解,包括测试数据。
ACM常用搜索算法详解ACM常用搜索算法详解ACM常用搜索算法详解ACM常用搜索算法详解