黑马程序员技术交流社区

标题: n阶台阶，可以一步走1阶，也可以一步走2阶。问共多少种走法。 [打印本页]

---

作者: DaoDao2    时间: 2016-8-28 22:55
标题: n阶台阶，可以一步走1阶，也可以一步走2阶。问共多少种走法。
问题：n阶台阶，可以一步走1阶，也可以一步走2阶。问共多少种走法。
要求：用递归


思路： 设n阶台阶走法为f(n)，则有
n=1: f(n)=1   只有一种走法(1)
n=2: f(n)=2   两种(1+1或者2)
n>2: 第一步有两种走法：1步或2步。所以n阶台阶为走1阶后剩下的种数，与走2阶后剩下的种数之和。也就是f(n)=f(n-1)+f(n-2)
以此写出递归函数

又：此递归效率太低。归其原因，是重复计算了f(3)、f(4)……f(8)。所以我们可以先定义一个数组，将已经算出的值存起来。需要时可以直接用。方法是：
a[0]不用。因为已知f(1)和f(2),所以直接赋值为1,2。后边自动初始化为0。其相应的值第一次调用时求出，再调用时直接从数组中取。
a[0]永远用不到。

---

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

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