看到有一道题：有一个40层阶梯，每次只能迈1阶或者2阶，问有多少种迈法.
哪个大神能提供一种算法？

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

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

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

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

好题，收藏了

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

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

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

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

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

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

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

看到了这道题，多人第一个思路估计都是：
全部只迈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-23 22:07
class Test_1_test {

        /**

答案是一亿六千万。

我不是已经解决过了吗？  

还是想的太简单了

xiaofushen 发表于 2016-3-24 00:45
按层主算法是有重复的,比如一共36个一步,2个二步.第一步和第三步迈二步这种情况就被算了两次.这样可能性 ...

这个我考虑到了有重复性的问题,,,你看看当i= 13的时候不会报错,当i=14的时候就会报错,
你的思路应该是对的,但是数列中插入相同元素的那个公式我也忘了...应该是那个公式有点问题...

补充一下二楼的思路：定义一个求阶乘的函数，再定义一个求组合的函数，比较利于代码的复用。。。
感觉代码的服用性真的特别重要，以前做项目的时候很多代码复制了还要改来改去的，很麻烦

都是大神，来自: iPhone客户端

先定义一个组合类
public class Combination {
        //定义降序阶乘，返回积
        public static int factorial(int start){
                int ji=1;
                for(;start>=1;start--){
                        ji*=start;
                }
                return ji;
        }
        //定义降序number个数阶乘，返回积
        public static int factorial_limit(int start,int number){
                int ji=1;
                while(number>=1){
                        ji*=start;
                        number--;
                        start--;
                }
                return ji;
        }
        //定义组合方法，参数total是指总共迈的步数，select为一次迈一步的次数（也可表示一次迈两部的步数）
        public static int OpCombination(int total,int select){
                int tmp1=factorial_limit(total, select);
                int tmp2=factorial(select);
                return tmp1/tmp2;
        }
}
再用主方法调用它
public class Test {

        public static void main(String[] args) {
                // TODO Auto-generated method stub
                //定义一个变量，记录走法的次数
                int times=0;
                //定义一个循环，局部变量i表示一种走法中，一步2阶出现的次数
                for(int i=0;i<=20;i++){
                        int tmp=0;
                //tmp表示一步1阶出现的次数
                        tmp=40-2*i;
                //tmp表示总共走了多少步
                        tmp+=i;
                //进行组合，统计次数
                        times +=Combination.OpCombination(tmp, i);
                }
                System.out.println(times);
        }

}

xiaofushen 发表于 2016-3-24 00:45
按层主算法是有重复的,比如一共36个一步,2个二步.第一步和第三步迈二步这种情况就被算了两次.这样可能性 ...

....我回头看一下是不是需要除2............

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

        /**

按层主算法是有重复的,比如一共36个一步,2个二步.第一步和第三步迈二步这种情况就被算了两次.这样可能性就降低了,我是先算出每个i对应的组合可能,再求和,见7楼,但是编译没错,运行会出上述问题,层主有时间帮我看看.

果然不简单~~

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

        /**

这个应该没啥问题吧......,数据大的超出预计....