题目描述
一个楼梯共有n级台阶,每次可以走一级或者两级,问从第0级台阶走到第n级台阶一共有多少种方案。
输入格式
共一行,包含一个整数n。
输出格式
共一行,包含一个整数,表示方案数。
数据范围
1≤n≤15
样例
输入样例:
5
输出样例:
8
深度优先搜索:遍历每种可能性。
C++ 代码
#include <iostream>
using namespace std;
int n,ans;
void f(int k);
int main(){
cin>>n;
f(0);
cout<<ans<<endl;
return 0;
}
void f(int k){
if(k==n){
ans++;
}
else if(k<n){
f(k+1);
f(k+2);
}
}
递推公式。可以写出递推公式f(n)=f(n-1)+f(n-2)(从0开始可以走一步或者两步,走一步后问题转化为从0到n-1,走两步同理),f(0)=f(1)=1;
C++ 代码
#include <iostream>
using namespace std;
int Fibonacci(int n);
int main(){
int n;
cin>>n;
cout<<Fibonacci(n)<<endl;
return 0;
}
int Fibonacci(int n){
int ret;
if(n==0||n==1)
ret=1;
else
ret=Fibonacci(n-1)+Fibonacci(n-2);
return ret;
}
斐波那契数列模板