题目
段誉身具凌波微波，动无常则，若危若安，一次能走一级台阶或者两级台阶，他要爬一段30级的山路，问有多少种走法？分析如何计算，然后编程解答。
进阶问题：当他轻功熟练度提升，一次最多可以走三级，那就结果有什么变化？后来走火入魔了，不能走一级，只能走二或三级，又有什么变化？
输入描述:
输入一个数n（1<=n<=30），代表段誉要爬一段n级的山路。
输出描述:
输出三个整数a,b,c（以空格相间）。其中a为段誉一次能走一级或两级台阶的走法；b为段誉一次能走一级、二级或三级台阶的走法；c为段誉一次能走二级或三级台阶的走法。
输入例子1:
3
输出例子1:
3 4 1
解题思路
分析每次走一步或者两步，一个台阶，1种走法；二个台阶，2（1+1,2）种走法；三个台阶，3（1+1+1,2+1,1+2）种走法。通过三个台阶的分析，走一步剩余台阶的走法数+走两步剩余台阶的走法数，即f(3)=f(2)+f(1),这就很容易让人想到斐波那契数列了，所以有n个台阶，就有f(n)=f(n-1)+f(n-2);那么剩下的进阶的问题也是一样的思路。
代码
递归版本
#include <bits/stdc++.h>
using namespace std;
int fun1(int n){
if(n==1){
return 1;
}else if(n==2){
return 2;
}else{
return fun1(n-1)+fun1(n-2);
}
}
int fun2(int n){
if(n==1){
return 1;
}else if(n==2){
return 2;
}else if(n==3){
return 4;
}else {
return fun2(n-1)+fun2(n-2)+fun2(n-3);
}
}
int fun3(int n){
if(n==1){
return 0;
}else if(n==2){
return 1;
}else if(n==3){
return 1;
}else {
return fun3(n-2)+fun3(n-3);
}
}
int main(){
int n;
cin>>n;
cout<<fun1(n);
cout<<" "<<fun2(n);
cout<<" "<<fun3(n);
return 0;
}
循环版本
int fun1(int n){
if(n==1){
return 1;
}else if(n==2){
return 2;
}else{
int a=1;
int b=2;
int c;
for(int i =3;i<n;i++){
c=a+b;
a=b;
b=c;
}
return a+b;
}
}
int fun2(int n){
if(n==1){
return 1;
}else if(n==2){
return 2;
}else if(n==3){
return 4;
}else {
int a=1;
int b=2;
int c=4;
int d;
for(int i =4;i<n;i++){
d=a+b+c;
a=b;
b=c;
c=d;
}
return a+b+c;
}
}
int fun3(int n){
if(n==1){
return 0;
}else if(n==2){
return 1;
}else if(n==3){
return 1;
}else {
int a=0;
int b=1;
int c=1;
int d;
for(int i =4;i<n;i++){
d=a+b;
a=b;
b=c;
c=d;
}
return a+b;
}
}