- 总时间限制: 1000ms
- 内存限制:
- 65536kB
- 描述
-
树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数
例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一级，第二次走两级
也可以第一次走两级，第二次走一级，一共3种方法。
- 输入
- 输入包含若干行，每行包含一个正整数N，代表楼梯级数，1 <= N <= 30
- 输出
- 不同的走法数，每一行输入对应一行输出
- 样例输入
- 5
- 8
- 10
- 样例输出
- 8
- 34
- 89
- 好吧，我还是简单说一下吧。这道题属于递归题中最为基础的一道关于拆分可能性的题，因此我们只要找到递归通式并确定出口就可以了。例如：爬到顶楼有两种情况，即爬一层和爬两层，因此可以得到递归通式f（n）=f（n-1）+f（n-2）。递归出口则是f（1）=1，f（2）=2 。由此，这道题就解完了。
- 那么，终于到了要讲的重点了：
- 有人可能会发现一个问题：为什么我敢用cin，cout？
- 其实我也不想用。。。
- 但是，由于这道题没有给出数据组数，因此只能用循环读入的方法，而这里便用到了cin的最大的好处也是最大的缺点：cin读入时不识别空格，即刚开始遇到空格便跳过，读入中遇到空格便中断，由此我们就可以有效的避免scanf读入数据爆时间的尴尬境况。
-
- 其实，cin和scanf各有各的优点，各有各的缺陷，例如：cin和scanf相比就无法读入大量数据。因此，只有合理使用，扬长避短，才能最大化优化代码。
- 最后，附上本题代码
#include<iostream>
using namespace std;
int a[35];
int pa(int x)
{
if(x==1)
{
return 1;
}
else if(x==2)
{
return 2;
}
else
{
return pa(x-1)+pa(x-2);
}
}
int main()
{
int n;
while(cin >>n)
{
cout << pa(n) <<endl;
}
return 0;
}
