/*
注意台阶级数太大会吐核,台阶级数小于等于99才能得到准确结果;但是级数越大,误差也可能越大;
该程序由c++编写,经过gcc编译;
*/
#include<iostream>
#include<vector>
using namespace std;
typedef struct{//用来保存符合情况的组合
int i2;//连上2级台阶的次数
int i3;//连上3级台阶的次数
}SHL;
typedef long long int INT;
//求m到k的积
INT jiechen(int m,int k){
if(m<=k){
INT res=1;
int i=m;
for(;i<=k;i++){
res*=i;
}
return res;
}
}
//算i个2连上,j个3连上的情况下,有多少种组合
INT fa(int i,int j){
if(0==i || 0==j) return 1;
int n=i<j?i:j;//找出i,j中的较小值
int m=i>j?i:j;//找出i,j中的较大值
INT res=jiechen(m+1,i+j)/jiechen(1,n);//排列组合优化后的公式,以保证级数级数尽可能大而不吐核
return res;
}
int main()
{
vector<SHL> vs;
cout<<"输入台阶数:";
int n;
cin>>n;
if(n>=2){
int i,j;
int k2=n/2+1;
int k3=n/3+1;
//得到上2级和3级台阶的次数组合
for(i=0;i<=k2;i++){
for(j=0;j<=k3;j++){
if(2*i+3*j==n){
SHL shl;
shl.i2=i;
shl.i3=j;
vs.push_back(shl);
}
}
}
vector<SHL>::iterator it=vs.begin();
INT sum=0;
while(it!=vs.end()){
sum+=fa(it->i2,it->i3);//累加各种情况下的排列组合
it++;
}
cout<<"可以有"<<sum<<"种上台阶的方法"<<endl;
}
else cout<<"输入不合法!"<<endl;
return 0;
}