程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [ACM] hdu 1134 Game of Connections(大數+Catalan數)

[ACM] hdu 1134 Game of Connections(大數+Catalan數)

編輯:C++入門知識

Game of Connections

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2923 Accepted Submission(s): 1649


Problem Description

This is a small but ancient game. You are supposed to write down the numbers 1, 2, 3, ... , 2n - 1, 2n consecutively in clockwise order on the ground to form a circle, and then, to draw some straight line segments to connect them into number pairs. Every number must be connected to exactly one another. And, no two segments are allowed to intersect.

It's still a simple game, isn't it? But after you've written down the 2n numbers, can you tell me in how many different ways can you connect the numbers into pairs? Life is harder, right?


Input

Each line of the input file will be a single positive number n, except the last line, which is a number -1. You may assume that 1 <= n <= 100.


Output

For each n, print in a single line the number of ways to connect the 2n numbers into pairs.


Sample Input

2
3
-1


Sample Output

2
5


Source

Asia 2004, Shanghai (Mainland China), Preliminary

解題思路:

Catalan數,遞推公式為h(n)=(4n-2)/(n+1)*h(n-1)(n>1) h(0)=1 ,用到了大數模板。

代碼:

#include
#include
#include
#include
using namespace std;

#define MAXN 9999
#define MAXSIZE 10
#define DLEN 4

class BigNum
{
private:
	int a[500];    //可以控制大數的位數
	int len;       //大數長度
public:
	BigNum(){ len = 1;memset(a,0,sizeof(a)); }   //構造函數
	BigNum(const int);       //將一個int類型的變量轉化為大數
	BigNum(const char*);     //將一個字符串類型的變量轉化為大數
	BigNum(const BigNum &);  //拷貝構造函數
	BigNum &operator=(const BigNum &);   //重載賦值運算符,大數之間進行賦值運算

	friend istream& operator>>(istream&,  BigNum&);   //重載輸入運算符
	friend ostream& operator<<(ostream&,  BigNum&);   //重載輸出運算符

	BigNum operator+(const BigNum &) const;   //重載加法運算符,兩個大數之間的相加運算
	BigNum operator-(const BigNum &) const;   //重載減法運算符,兩個大數之間的相減運算
	BigNum operator*(const BigNum &) const;   //重載乘法運算符,兩個大數之間的相乘運算
	BigNum operator/(const int   &) const;    //重載除法運算符,大數對一個整數進行相除運算

	BigNum operator^(const int  &) const;    //大數的n次方運算
	int    operator%(const int  &) const;    //大數對一個int類型的變量進行取模運算
	bool   operator>(const BigNum & T)const;   //大數和另一個大數的大小比較
	bool   operator>(const int & t)const;      //大數和一個int類型的變量的大小比較

	void print();       //輸出大數
};
BigNum::BigNum(const int b)     //將一個int類型的變量轉化為大數
{
	int c,d = b;
	len = 0;
	memset(a,0,sizeof(a));
	while(d > MAXN)
	{
		c = d - (d / (MAXN + 1)) * (MAXN + 1);
		d = d / (MAXN + 1);
		a[len++] = c;
	}
	a[len++] = d;
}
BigNum::BigNum(const char*s)     //將一個字符串類型的變量轉化為大數
{
	int t,k,index,l,i;
	memset(a,0,sizeof(a));
	l=strlen(s);
	len=l/DLEN;
	if(l%DLEN)
		len++;
	index=0;
	for(i=l-1;i>=0;i-=DLEN)
	{
		t=0;
		k=i-DLEN+1;
		if(k<0)
			k=0;
		for(int j=k;j<=i;j++)
			t=t*10+s[j]-'0';
		a[index++]=t;
	}
}
BigNum::BigNum(const BigNum & T) : len(T.len)  //拷貝構造函數
{
	int i;
	memset(a,0,sizeof(a));
	for(i = 0 ; i < len ; i++)
		a[i] = T.a[i];
}
BigNum & BigNum::operator=(const BigNum & n)   //重載賦值運算符,大數之間進行賦值運算
{
	int i;
	len = n.len;
	memset(a,0,sizeof(a));
	for(i = 0 ; i < len ; i++)
		a[i] = n.a[i];
	return *this;
}
istream& operator>>(istream & in,  BigNum & b)   //重載輸入運算符
{
	char ch[MAXSIZE*4];
	int i = -1;
	in>>ch;
	int l=strlen(ch);
	int count=0,sum=0;
	for(i=l-1;i>=0;)
	{
		sum = 0;
		int t=1;
		for(int j=0;j<4&&i>=0;j++,i--,t*=10)
		{
			sum+=(ch[i]-'0')*t;
		}
		b.a[count]=sum;
		count++;
	}
	b.len =count++;
	return in;

}
ostream& operator<<(ostream& out,  BigNum& b)   //重載輸出運算符
{
	int i;
	cout << b.a[b.len - 1];
	for(i = b.len - 2 ; i >= 0 ; i--)
	{
		cout.width(DLEN);
		cout.fill('0');
		cout << b.a[i];
	}
	return out;
}

BigNum BigNum::operator+(const BigNum & T) const   //兩個大數之間的相加運算
{
	BigNum t(*this);
	int i,big;      //位數
	big = T.len > len ? T.len : len;
	for(i = 0 ; i < big ; i++)
	{
		t.a[i] +=T.a[i];
		if(t.a[i] > MAXN)
		{
			t.a[i + 1]++;
			t.a[i] -=MAXN+1;
		}
	}
	if(t.a[big] != 0)
		t.len = big + 1;
	else
		t.len = big;
	return t;
}
BigNum BigNum::operator-(const BigNum & T) const   //兩個大數之間的相減運算
{
	int i,j,big;
	bool flag;
	BigNum t1,t2;
	if(*this>T)
	{
		t1=*this;
		t2=T;
		flag=0;
	}
	else
	{
		t1=T;
		t2=*this;
		flag=1;
	}
	big=t1.len;
	for(i = 0 ; i < big ; i++)
	{
		if(t1.a[i] < t2.a[i])
		{
			j = i + 1;
			while(t1.a[j] == 0)
				j++;
			t1.a[j--]--;
			while(j > i)
				t1.a[j--] += MAXN;
			t1.a[i] += MAXN + 1 - t2.a[i];
		}
		else
			t1.a[i] -= t2.a[i];
	}
	t1.len = big;
	while(t1.a[len - 1] == 0 && t1.len > 1)
	{
		t1.len--;
		big--;
	}
	if(flag)
		t1.a[big-1]=0-t1.a[big-1];
	return t1;
}

BigNum BigNum::operator*(const BigNum & T) const   //兩個大數之間的相乘運算
{
	BigNum ret;
	int i,j,up;
	int temp,temp1;
	for(i = 0 ; i < len ; i++)
	{
		up = 0;
		for(j = 0 ; j < T.len ; j++)
		{
			temp = a[i] * T.a[j] + ret.a[i + j] + up;
			if(temp > MAXN)
			{
				temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
				up = temp / (MAXN + 1);
				ret.a[i + j] = temp1;
			}
			else
			{
				up = 0;
				ret.a[i + j] = temp;
			}
		}
		if(up != 0)
			ret.a[i + j] = up;
	}
	ret.len = i + j;
	while(ret.a[ret.len - 1] == 0 && ret.len > 1)
		ret.len--;
	return ret;
}
BigNum BigNum::operator/(const int & b) const   //大數對一個整數進行相除運算
{
	BigNum ret;
	int i,down = 0;
	for(i = len - 1 ; i >= 0 ; i--)
	{
		ret.a[i] = (a[i] + down * (MAXN + 1)) / b;
		down = a[i] + down * (MAXN + 1) - ret.a[i] * b;
	}
	ret.len = len;
	while(ret.a[ret.len - 1] == 0 && ret.len > 1)
		ret.len--;
	return ret;
}
int BigNum::operator %(const int & b) const    //大數對一個int類型的變量進行取模運算
{
	int i,d=0;
	for (i = len-1; i>=0; i--)
	{
		d = ((d * (MAXN+1))% b + a[i])% b;
	}
	return d;
}
BigNum BigNum::operator^(const int & n) const    //大數的n次方運算
{
	BigNum t,ret(1);
	int i;
	if(n<0)
		exit(-1);
	if(n==0)
		return 1;
	if(n==1)
		return *this;
	int m=n;
	while(m>1)
	{
		t=*this;
		for( i=1;i<<1<=m;i<<=1)
		{
			t=t*t;
		}
		m-=i;
		ret=ret*t;
		if(m==1)
			ret=ret*(*this);
	}
	return ret;
}
bool BigNum::operator>(const BigNum & T) const   //大數和另一個大數的大小比較
{
	int ln;
	if(len > T.len)
		return true;
	else if(len == T.len)
	{
		ln = len - 1;
		while(a[ln] == T.a[ln] && ln >= 0)
			ln--;
		if(ln >= 0 && a[ln] > T.a[ln])
			return true;
		else
			return false;
	}
	else
		return false;
}
bool BigNum::operator >(const int & t) const    //大數和一個int類型的變量的大小比較
{
	BigNum b(t);
	return *this>b;
}

void BigNum::print()    //輸出大數
{
	int i;
	cout << a[len - 1];
	for(i = len - 2 ; i >= 0 ; i--)
	{
		cout.width(DLEN);
		cout.fill('0');
		cout << a[i];
	}
	cout << endl;
}
int main()
{
	BigNum num[102];
	num[0]=1;
	for(int i=1;i<=100;i++)
    {
        num[i]=num[i-1]*(4*i-2)/(i+1);
    }
	int n;
	while(cin>>n&&n!=-1)
    {
        num[n].print();
    }
    return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved