Time Limit:    1000MS    Memory Limit:    65536KB
Total Submissions:    217    Accepted:    55
Share
Description:
      校队的里小胖非常的懒，他看农大春晖桥的台阶那么小阶又那么陡，每次只上一阶，那样太费时间了，所以他每次上台阶，每步都要么上两阶，要么上三阶。现在他很好奇，每次都走不一样的走法，在农大的四年里能否走完所有的走法。所以他就去询问会编程的zhu同学。
      为了使问题更简单，现在你只需要编程计算，按小胖的走法，共有n阶的台阶可以有几种不同的走法。
Input:
输入只有一个正整数n（n<10000）。
Output:
输出一个整数，代表共有多少种不同的走法。
Sample Input:
5
Sample Output:
2
Hint:
答案可能很大，会超出__int64范围。

好复杂

刚才抽空写了一个，要的话Q我。

楼上怎么不直接发上去啊...

只有看的份

fn=fn-2+fn-3
高精度计算

好复杂啊
 会的麻烦发出来

/*
注意台阶级数太大会吐核,台阶级数小于等于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;
}

我在想有没有规律呢？

这题原来没什么难点，先赞一下6楼
第n阶可以从第n-2阶上来，也可以从第n-3阶上来，所以 到达第n阶的走法数 = 到达第n-2阶的走法数 + 到达第n-3阶的走法数
公式就是 f(n) = f(n-2) + f(n-3)
如果是Javar的话，它们会直接写个递归函数，一运行死机了，然后理直气壮的告诉你，你的电脑配置太差需要升级^_^
但我们用的C/C++，我用标准C语法写一个，在gcc4.7.2（加编译参数-std=c99）下编译测试通过

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

uintmax_t foo( unsigned n ) // n<10000 但 无符号64bits的整数只能算到160
{
    uintmax_t buf[3] = { 1, 1, 1 }; // f(2), f(3), f(4)
    for( unsigned i=5; i<=n; ++i )
        buf[(i+1)%3] += buf[(i+2)%3];

    return buf[(n+1)%3];
}

#include <stdio.h>

int main()
{
    printf( "%"PRIuMAX"\n", foo(5) );
    printf( "%"PRIuMAX"\n", foo(9) );
    printf( "%"PRIuMAX"\n", foo(160) );
    printf( "%"PRIuMAX"\n", foo(99999) );

    return 0;
}

代码简单，但仍然不符合题意，因为题目要求n<10000，而uint64_t只能算到n==160的时候，再多就溢出了。
要想完成这道题，得自己定义个长整数运行函数，用数组或链表等等来分段存储整数。这个也很简单，我下午再写