题目描述
小乐乐上课需要走n阶台阶，因为他腿比较长，所以每次可以选择走一阶或者走两阶，那么他一共有多少种走法？
输入描述: 输入包含一个整数n (1 ≤ n ≤ 30)
输出描述: 输出一个整数，即小乐乐可以走的方法数。
我的解答
想了很久，题意不太理解，以为是 排列组合问题，写出的代码仅部分通过
看了题解发现是斐波那锲数列问题
# include<bits/stdc++.h> using namespace std; //阶乘递归 int JieCheng(int n){ int r = 0; if(n == 1) return 1; else if(n>1){ r = n * JieCheng(n-1); return r; } } int main() { int n,count = 0; cin>>n; for(int i = 1;i<n;i++){ for(int j = 1;2*j<n;j++){ if(i + j * 2 == n){ count += JieCheng(i + j) / (JieCheng(i) * JieCheng(j)); } } } if(n % 2 == 0){ cout<<count + 2<<endl; } else cout<<count + 1<<endl; }错误：非全部通过
解答因为走到第三个楼梯的时候可以从第一阶和第二阶直接走上来；（开始走1 或者 2，第一步在递归中单独列出 ，然后在讨论 往上的情况）
同理，第四个楼梯的时候可以从第二阶和第三阶直接走上来；
第五个楼梯的时候可以从第三阶和第四阶直接走上来；
… …
所以可以得出公式
a[i]=a[i-1]+a[i-2] 其中有a[0]=0，a[1]=1,a[2]=2；
大致思想就是，从第3节楼梯开始，及后面的台阶 都有两种情况
可以带入数值，可以明显的看出，如 n = 5;
f(5) = f(4) + f(3)--->第5节楼梯可以从第4、3到达，有8种可能
f(4) = f(3) + f(2)--->第4节楼梯可以从第3、2到达,有5种可能
f(3) = f(2) + f(1)---->…f(3) = 2 + 1有3种可能情况
f(2) = f(1) + f(0)---->…f(2) = 1 + 1 有2种可能
f(1) = 1 = f(0)
# include<bits/stdc++.h> using namespace std; //递归 int f(int n){ if(n == 1 || n == 0) return 1; else return f(n -1) + f(n - 2); } int main() { int n; cin>>n; cout<<f(n)<<endl; return 0; }