黑马程序员技术交流社区

标题: 求阶梯问题编程 [打印本页]

---

作者: wchwsh123    时间: 2016-3-21 00:31
标题: 求阶梯问题编程
问：有一个40层阶梯，每次只能迈1阶或者2阶，问有多少种迈法.
编程求大神解答

---

作者: little_bear123    时间: 2016-3-21 09:23
这个问题好像有点难度啊

---

作者: lgdbest    时间: 2016-3-21 12:34
仿佛想到了排列组合。。。

---

作者: 韩文通    时间: 2016-3-21 23:05
不知道啊啊啊

---

作者: zhengxiaomin    时间: 2016-3-21 23:34
这个可以通过循环来计算了，首先定义一个整数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:44
用不着考虑简便算法。既然要编程解决，就要用计算机的运算速度暴力解决就行了。把所有符合要求的组合全部筛 ...

那你怎么编程解决的？

---

作者: yijincheng    时间: 2016-3-21 23:52

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

稍等一会儿

---

作者: 赵国政    时间: 2016-3-22 00:04
我向来看解答的 还没有···

---

作者: Gqg    时间: 2016-3-22 00:09

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

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

---

作者: yijincheng    时间: 2016-3-22 00:36


算出来了 答案是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.

forty.zip

2016-3-22 00:54 上传

点击文件名下载附件

947 Bytes, 下载次数: 383

---

作者: yijincheng    时间: 2016-3-22 01:11

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

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

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2