问：有一个40层阶梯，每次只能迈1阶或者2阶，问有多少种迈法.
编程求大神解答

这个问题好像有点难度啊

仿佛想到了排列组合。。。

不知道啊啊啊

这个可以通过循环来计算了，首先定义一个整数x代表40层阶梯，用y（初始值 = x）表示剩下的阶梯数，用idea（初始为1）表示能使用的迈法，现在我要先跨出一步（用step表示），这一步可以是1也可以是2，就有2种迈法，迈完这步后剩下的阶梯数位y = y -step ； 可用的迈法  idea = idea * 2； 然后就是进行下一次循环，我下一步又可以走1阶或者2阶。这是解题的思路。

用不着考虑简便算法。既然要编程解决，就要用计算机的运算速度暴力解决就行了。把所有符合要求的组合全部筛选出来。

yijincheng 发表于 2016-3-21 23:44
用不着考虑简便算法。既然要编程解决，就要用计算机的运算速度暴力解决就行了。把所有符合要求的组合全部筛 ...

那你怎么编程解决的？

Gqg 发表于 2016-3-21 23:51
那你怎么编程解决的？

稍等一会儿

我向来看解答的 还没有···

yijincheng 发表于 2016-3-21 23:52
稍等一会儿

可以这样考虑，最少多少步，最多多少步，其中每种步数都对应不同的方法，求出每种步数对应的种数，相加就可以了

算出来了 答案是165580141 一亿六千万多种组合。这个涉及了数据结构的知识。楼主听说过递归算法吗？先去了解一下递归算法的思想，这题的解法是相当容易的。
代码写得有点赶，算法肯定还有优化的空间，只不过懒着改了。
大致思路是：
写两个方法，一个方法走一步oneStep；另一个方法走两步twoSteps。
然后先算第一步迈一级台阶的分支，再算第一步迈两级台阶的分支。
oneStep();
twoSteps();
两个方法内部仍然分为两个分支，算第二步迈一级或者第二步迈两级：

1. oneStep(){
   
2.     oneStep();
   
3.     twpSteps();
   
4. }
   
5. twoSteps(){
   
6.     oneStep();
   
7.     twpSteps();
   
8. }

复制代码

以此类推，算第三步、第四部……
当然，每调用一次oneStep twoSteps，就要有个还剩下几级台阶的变量remainSteps自减1或者2.当remainSteps小于等于0了，方法就要return。然后再全局变量总共有多少种走法的变量total上加1.

Gqg 发表于 2016-3-22 00:09
可以这样考虑，最少多少步，最多多少步，其中每种步数都对应不同的方法，求出每种步数对应的种数，相加就 ...

每走一步都有两个分支。
大概2^20 ~ 2^40 之间。最少也要有100万种走法。用加法不行的。