1759418586 发表于 2016-3-23 22:07
class Test_1_test {

        /**

答案是一亿六千万。

看到了这道题，多人第一个思路估计都是：
全部只迈1阶，最多40步；全部只迈2阶，最少20步。
然后算38步迈一阶，1步迈2阶总共有多少种组合；19步迈2阶，2步迈1阶有多少种组合…………。把所有组合都一一算出来，最后加起来，得到答案。

这样算其实也可以。但是这是道编程题啊。上述的算法终究还是大部分的逻辑判断都是人脑完成的，最后计算机不过是担任了一个高级计算器的角色。有点太过于委屈如今这个时代计算机的计算速度了
用编程解决数学问题，就应该人脑动的越少越好，就靠计算机恐怖的计算速度暴力的穷举出来才叫做程序员的道嘛。
那么，现在我们来看看该如何穷举出所有的可能迈步的组合。
我们不用去考虑第一步该怎么走，第二步该迈2阶还是1阶。把这些可能性全部试一遍。
也就写代码来模拟爬这个40级台阶。
第一步开始，就是两个分支：先迈2阶和先迈1阶。那么就分开来搞定。先迈2阶，等爬到顶了，再下来，再走先迈1阶的路线。
到了第二步，又是分两支——第二步是迈1阶还是迈2阶？还是先走迈一阶的走法，走到顶了，再下拉，走迈2阶的走法。
………………
可是这么一直走下去，什么时候是头呢？这就要有个变量来显示还剩多少台阶，初始值为40，每走一步，就根据迈一阶还是两阶，减去1或2.当变成0了就可以return了。
具体代码实现就是

1. public class Steps {
   
2.         private int totalSteps;                 //总共多少级台阶
   
3.         private int ways;                        //总共有多少种走法
   
4.         public Steps() {
   
5.                 totalSteps = 40; //40级台阶
   
6.                 ways = 0;                   //初始化总走法
   
7.         }
   
8.         public void  go() { //运用了递归算法。先算第一步迈一级的分支；再算第一步迈两级的分支
   
9.                 oneStep(totalSteps);
   
10.                 twoStep(totalSteps);
    
11.         }
    
12.         private boolean oneStep(int remainSteps){//参数的意义：还剩下多少级台阶。
    
13.                 remainSteps -= 1;        //走了一级
    
14.                 if(remainSteps == 0) {//剩下的台阶为0，返回true，ways加1.
    
15.                         ways++;
    
16.                         return true;
    
17.                 }
    
18.                 else if(remainSteps < 0) {//冒了，返回false
    
19.                         return false;
    
20.                 }
    
21.                 else if(remainSteps > 0) {//还剩有台阶没走完，继续走。还是先算走一级的分支，再算走两级的分支。
    
22.                         oneStep(remainSteps);
    
23.                         twoStep(remainSteps);
    
24.                 }
    
25.                 return false;
    
26.         }
    
27.         private boolean  twoStep(int remainSteps){
    
28.                 remainSteps -= 2;        //走了两级
    
29.                 if(remainSteps == 0) {//剩下的台阶为0，返回true，ways加1.
    
30.                         ways++;
    
31.                         return true;
    
32.                 }
    
33.                 else if(remainSteps < 0) {//冒了，返回false
    
34.                         return false;
    
35.                 }
    
36.                 else if(remainSteps > 0) {//还剩有台阶没走完，继续走。还是先算走一级的分支，再算走两级的分支。
    
37.                         oneStep(remainSteps);
    
38.                         twoStep(remainSteps);
    
39.                 }
    
40.                 return false;
    
41.         }
    
42.         public void show() {
    
43.                 System.out.println(ways);
    
44.         }        
    
45. }
    

复制代码

代码写得匆忙。oneStep（）和twoSteps（）方法似乎不需要返回值。为程序健壮性就留着吧。没有接触过递归算法的同学，可以找时间学习一下。这是一个虽然抽象，但是却非常强大的数据结构。
这个结构非常像二叉树。大家可以试试，用TreeSet的结构来做这道题。

1759418586 发表于 2016-3-22 08:48
假设迈2阶的次数为i,i的范围是0-20,   j是迈1阶的次数  j= 40-2i  ,利用for循环,i从0开始.到20,
将  i  插 ...

算法终究还是大部分的逻辑判断都是人脑完成的，最后计算机不过是担任了一个高级计算器的角色。有点太过于委屈如今这个时代计算机的计算速度了。
正确思路因该用递归结构，穷举出来。

little_bear123 发表于 2016-3-22 09:54
递归找规律

看了这么多层。就这么一个思路对的。

yijincheng 发表于 2016-3-24 22:31
看了这么多层。就这么一个思路对的。

毕竟新手,只记得初中时候数学上学的插入元素的方法,,就拿来用了...
如果结合数学上的公式的话应该能更快得出结果,为啥非得用穷举,.......

这是个经典的二叉树算法题，明天搬代码过来

好题，收藏了

1759418586 发表于 2016-3-25 00:41
毕竟新手,只记得初中时候数学上学的插入元素的方法,,就拿来用了...
如果结合数学上的公式的话应该能更快 ...

结果上来看，你也算错了啊。当然，你当思路是正确的，不过计算过程不对。排列组合的公式是：C(n,m) = m!/n!*(m - n) !，你再改改看。不过从解决问题效率角度看，并不推荐。现在家用机CPU的处理速度都是每秒几十亿次。真心不必替电脑担心穷举所花费的时间，大概会慢个几微秒吧。再者，要理解递归结构、回溯算法的难度也不比这个纯数学问题低。

yijincheng 发表于 2016-3-24 22:22
看到了这道题，多人第一个思路估计都是：
全部只迈1阶，最多40步；全部只迈2阶，最少20步。
然后算38步迈一 ...

受教了,递归和二叉树,看完层主分析后,才知道这果然是道有趣的题.二叉树结构本身有递归特性,其操作可以用递归描述.原问题只要能分解为相同形式且更简单的子问题,并且有结束条件,就可以用递归解决.