题目描述
一个楼梯共有 n
级台阶,每次可以走一级或者两级,问从第 0
级台阶走到第 n
级台阶一共有多少种方案。
输入格式
共一行,包含一个整数 n
。
输出格式
共一行,包含一个整数,表示方案数。
数据范围
1≤n≤15
输入样例:
5
输出样例:
8
#include<iostream>
using namespace std;
long long fact(int x)//注意!!求解阶乘时,数字会很大,int类型不够,要用longlong
{
if(x==1) return 1;
return x*fact(x-1);
}
int way(int n)
{
int i,j,k=0;
for(i=0;i<=n;i++)
{
for(j=0;j<=n/2;j++)
{
if(i+j*2==n)
{
if(i==0||j==0) k++;
else k=k+fact(i+j)/(fact(j)*fact(i));
}
}
}
return k;
}
int main()
{
int n;
cin>>n;
cout<<way(n)<<endl;
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla