注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

奕克

爱家人爱工作爱生活

 
 
 

日志

 
 

ACM算法详解之递归(转帖)  

2010-08-07 21:07:08|  分类: 转载 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
         递归在解决一些问题的时候非常直观,但是在是使用递归的时候要注意递归的深度,如果深度太深,可能会造成堆栈溢出。下面通过实例介绍如何使用。
题目:超级楼梯
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 = result[i-1]+result[i-2];
              }
              return result[n-1];
       }
转自:
http://student.csdn.net/space.php?uid=124362&do=blog&id=38379
  评论这张
 
阅读(152)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017