博客

Problem Description

有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有
多少种走法？

Input

输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数
M（1<=M<=40）,表示楼梯的级数。

Output

对于每个测试实例，请输出不同走法的数量

Sample Input

2
2
3

Sample Output

1
2

这是一道典型的递归题目。由于一次只能踏上一级或两级台阶，所以要到达第M级台阶，只有两种方法可以到达，要么从M-1级踏一级，要么从M-2级踏二级。换句话而言，我不管你如何从第一级走到第M-1、M-2级有多少种走法，分别记为f(M-1)、f(M-2)，我只需要知道，

f(M) = M-1 + M-2  这两种方法。

代入得：

f(M) = f(M-1) + f(M-2)

hanoi塔递推问题也是这个思路，我不管前面要实现n-1级需要多少步完成，我仅需要知道，要完成第n级，一定只有一种方法，即将处在b桩的第n个塔层先放入c桩，再将a桩的n-1个塔层放入c桩。（题意是，从左向右，a,b,c，最终要放到c桩）