catalan.txt

catalan大数的计算

#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
void add1(string& a, const string& s)
{
  int temp=0;           //进位
  for(int ai=0,si=s.length()-1; si>=0||temp; ++ai,--si)
  {
    temp += a[ai]-'0'+(si>=0)*(s[si]-'0');
    a[ai] = temp%10+'0';
    temp /= 10;
  }
}
void add2(string &a,string &s)
{
	reverse(s.begin(),s.end());
	int temp=0;
	for(int i=0;i<s.length();i++)
	{
		temp+=a[i]-'0'+s[i]-'0';
		a[i]=temp%10+'0';
		temp/=10;
	}
}
void comple(string& s){
	int i;
  for(i=0; i<s.length(); ++i)
    s[i] = '9' - s[i]+'0';
  for(i=s.length()-1; i>=0; i--){
    if(s[i]=='9') s[i]='0';
    else{ s[i]++; break; }
  }
}

const int bitNum = 205;

string ma[220][220];
int main()
{
	int i,j;
	for(i=0;i<220;i++)
	{
		ma[i][0]="1";
		ma[0][i]="1";
		ma[i][i]="1";
	}
	for(i=2;i<220;i++)
	{
		string s;
		int num=i;
		while(num>0)
		{
			s+=num%10+'0';
			num/=10;
		}
		reverse(s.begin(),s.end());
		ma[i][1]=s;
	}
	for(i=2;i<220;i++)
	{
		for(j=1;j<i;j++)
		{
			string a(bitNum,'0');
			add1(a, ma[i-1][j]);  // 见上面的代码，结果在a中,倒排
			add1(a, ma[i-1][j-1]);  // 见上面的代码，结果在a中,倒排
			reverse(a.begin(), a.end());
			string ss=a.substr(a.find_first_not_of('0'));  //去掉0再输出
			ma[i][j]=ss;
		}
	}
	int n;
	while(cin>>n)
	{
		string b(bitNum,'0');
		string s1=ma[2*n][n];
		s1 = string(bitNum-s1.length(), '0')+ s1;
		add2(b,s1);
		string s2=ma[2*n][n+1];
		s2 = string(bitNum-s2.length(),'0') + s2;   // 前空补0,然后取补
        comple(s2);
		add2(b,s2);
		reverse(b.begin(), b.end());                   // 对结果做翻转
        if(b[0]=='9'){ comple(b); cout<<'-'; }       // 若大数小于0,则取补
		int pos = b.find_first_not_of('0');           // 去掉前导0
		if(pos==string::npos) cout<<"0\n";
		else cout<<b.substr(pos)<<"\n";
	}
	return 0;
}