第 201 题  ：  相连游戏
(时间限制为：100毫秒)


问题描述
     这是一个小而古老的游戏，假设你将1~2n个数按顺时针方向写下来组成一个圆环，然后用一些线段将这些数组成一个数对。每个数只仅仅与另一个相连。而且所有线段不能相交。
     请你写一个程序，计算当写下2n个数后，一共有多少种不同的相连方式。
     连接方式数Ai的推导公式如下：
     A1=1    An=（4n-2）/(n+1)*An-1  (n>=2)
输入
    每行输入一个正整数n（1<=n<=100），最后一行是-1，代表结束。
输出
    对于每个n，输出一行数字，表示2n个数相连的可能数目。
样例输入
2
3
-1
样例输出
2
5

#include <iostream>
using namespace std;
int f(int n)
{ unsigned long s;//范围小了，怎么办
    if(n==1)
        s=1;
    else if(n>=2)
    s=(4*n-2)*f(n-1)/(n+1);
      return s;
}
int main()
{
    int x;
   
        while(cin>>x)
        {
        if(x==-1)break;
        cout<<f(x)<<endl;
        }
    return 0;
}

 

把s定义为__int64的看看

我的可以

还是小了
20就超过了。

[ 本帖最后由 风雨123 于 2013-2-27 14:45 编辑 ]

那很明显考大数运算的。。。。

请求高手，为我解答。谢了。

5分。。。

50分如何？

没找到这道题在哪儿提交 所以不一定会AC 主要是用了标准库 时间上不保证会通过
因为是大数运算 所以用容器模拟了一个LargeInt类 时间有限 只提供了 *= /= 和 << 三个运算符 正好够本题用
编程效率太低 又要赶着睡觉
原理是用数组模拟多位数乘除过程 这里数组一个元素值0-9999 正好表示大整数中的4个十进制位 4位一组
由于太复杂 所以先只实现了乘数和除数都是“一位”的情形 即乘除的又操作数要小于10000 但对本题来说足够用了
思路是看的百度知道上的 http://zhidao.baidu.com/question/166472785.html
主函数 用了LargeintInt 很简明

int main()
{
    int n;
    LargeInt An;
    while(cin>>n && n >= 1){
        An = 1;
        for(int i(2); i <= n; i++){
            An *= 4*i-2;
            An /= i+1;
        }
        cout << An << endl;
    }
    return 0;
}

类的定义及实现如下

#include <iostream>
#include <vector>

using namespace std;

class LargeInt
{
    public:
        LargeInt(): n(1,0) {}
        LargeInt(int i): n(1,0) {*n.begin() = i;}
        ~LargeInt() {}
        LargeInt& operator*=(int m);
        LargeInt& operator/=(int m);
        friend ostream& operator<<(ostream &out, LargeInt &Ln);
    
    private:
        vector<long> n;
        int carry(long &i){
            int tmp = i<10000 ? 0 : i/10000; 
            if(tmp) i %=10000;
            return tmp;
        }
};

LargeInt& LargeInt::operator*=(int m)
{
    int carryval = 0;
    for(vector<long>::iterator iter=n.begin();
        iter != n.end(); iter++){
            *iter *=m;
            *iter +=carryval;
            carryval = carry(*iter);  
        }
    if(carryval) n.push_back(carryval);
    
    return *this;
}

LargeInt& LargeInt::operator/=(int m)
{
    int rem = 0;
    if(n.end()-n.begin() > 1 && *n.rbegin()    < m){
        *(++n.rbegin()) += (*n.rbegin())*10000;
        n.pop_back();        
    }
    for(vector<long>::reverse_iterator iter=n.rbegin();
        iter != n.rend(); iter++){
        *iter +=rem;
        rem = (*iter%m)*10000;
        *iter /=m;        
    }
    
    return *this;
}

ostream& operator<<(ostream &out, LargeInt &Ln)
{
    for(vector<long>::reverse_iterator iter=Ln.n.rbegin();
        iter != Ln.n.rend(); iter++){
        if(iter != Ln.n.rbegin()){
            out.fill('0');
            out.width(4);    
        }
        out << *iter;        
    }
    
    return out;
}

程序的运行情况：

现在刚刚在学C++ 借楼主题目练习练习 欢迎批评

谢谢了