cata2.cpp

设计一个算法

#include<iostream>
#include<fstream>
#include<string>
using namespace std;

class cstring
{
private:
	string str;
	string resi;
public:
	cstring(){}
	cstring(string x)
	{
		str=x;
	}
	~cstring()
	{
		str="0";
	}
	int length();
	void change_int(int *a,int len);//将字符串转化为整形
	void change_str(int *a,int len);//将整形转化为字符串
	cstring add(cstring x,cstring y);//实现两个cstring类的相加,结果在z中
	cstring sub(cstring x,cstring y);//实现两个cstring类的相减,结果在z中
	cstring multi(cstring x,cstring y);//实现两个cstring类的相乘,结果在z中
	cstring factorial(cstring x);//实现cstring类的阶乘
	int compare(cstring x,cstring y);//比较两个cstring类对象的str的大小
	cstring div(cstring x,cstring y);//实现两个cstring类的相除,结果在z中
	cstring combination(cstring x,cstring y);//实现两个cstring类对象的组合
	void print()
	{
		cout<<str<<endl;
	}
	void print_div()
	{
		cout<<"the quotient is:"<<str<<endl<<"the residue is:"<<resi<<endl;
	}
	void print_files(ofstream&) const;
};///:p
void cstring::print_files(ofstream& out) const
{
	out<<str<<endl;
}///;p

inline int cstring::length()
{
	int i=0;
	while(str[i])
		i++;
	return i;
}///:p
int cstring::compare(cstring x,cstring y)
{
	int len_x=x.length(),len_y=y.length();
	if(len_x>len_y) return 1;
	else if(len_x<len_y) return 0;
	else
	{
		int *xx=new int[len_x];
		int *yy=new int[len_y];
		x.change_int(xx,len_x);
		y.change_int(yy,len_y);
		for(int i=len_x-1;i>=0;i--)
		{
			if(xx[i]!=yy[i])
			   break;
		}
		if(i==-1) return 2;
		else 
		{
		   if(xx[i]>yy[i]) return 1;
		   else return 0;
		}
	}
}
inline void cstring::change_int(int *a,int len)//使用前要先建立动态数组	len=s.length();int *a=new int[len];s.change(a,len);
{
    for(int j=0;j<len;j++)                 //已经对数组进行了逆置
		a[len-1-j]=(int)(str[j]-48);
}///:P
inline void cstring::change_str(int *a,int len)//整形数组转化为字符串,
{
	int i=1;
	while(a[len-i]==0&&i<len) i++;
	for(int j=0;j<=len-i;j++)
       str+=(char)(a[len-i-j]+48);	
}///:p
inline cstring cstring::add(cstring x,cstring y)//x被加数,y加数,z结果,
{
	cstring z;
	int len_x=x.length(),len_y=y.length();
	int len_max=len_x>len_y? len_x:len_y;
	int zz[10001]={0};
    int xx[10000]={0};
	x.change_int(xx,len_x);
	int yy[10000]={0};
	y.change_int(yy,len_y);
	int carry=0,temp1,temp2;
    for(int i=0;i<len_max;i++)
	{
		temp2=temp1=xx[i]+yy[i]+carry;
		carry=temp1/10;
        if(carry)
			zz[i]=temp2%10;
		else zz[i]=temp2;
	}
    zz[len_max]=carry;
	z.change_str(zz,len_max+1);
	return z;
}///:p
inline cstring cstring::sub(cstring x,cstring y)//x为被减数,y为减数,要保证被减数大于减数即x>y,z为结果
{
	cstring z;
	int len_max=x.length(),len_y=y.length();
	int zz[10000]={0},xx[10000]={0},yy[10000]={0};
	x.change_int(xx,len_max);
	y.change_int(yy,len_y);
	int borrow=0,temp1;//borrow为借位
    for(int i=0;i<len_max;i++)
	{
        temp1=xx[i]+10-yy[i]-borrow;
        if(temp1>=10) 
		{
			temp1=temp1-10;
			borrow=0;
		}
		else
		    borrow=1;
		zz[i]=temp1;
	}
   z.change_str(zz,len_max);  
   return z;
}///:p
inline cstring cstring::multi(cstring x,cstring y)//x是被乘数,y是乘数
{
	cstring z;
	int len_x=x.length(),len_y=y.length();
	int len_z=len_x+len_y;
    int zz1[20000]={0},xx1[10000]={0},yy1[10000]={0};
    x.change_int(xx1,len_x);
	y.change_int(yy1,len_y);
	int carry,temp1,temp2;
    cstring temp("0");
//	temp.~cstring();
    for(int j=0;j<len_y;j++)
	{
		for(int t=0;t<len_z;t++)//初始化数组zz为0
		     zz1[t]=0;
		carry=0;
		z.~cstring();
		for(int i=0;i<len_x;i++)
		{
             temp2=temp1=yy1[j]*xx1[i]+carry;
			 carry=temp1/10;
			 if(carry)
	    		zz1[i+j]=temp2%10;
	         else zz1[i+j]=temp2;
		}
		if(carry) 
			zz1[len_x+j]=carry;
	    z.change_str(zz1,len_z);
        z=z.add(z,temp);
		temp.str=z.str;	
	}
    return z;
}///:p
inline cstring cstring::factorial(cstring x)//定义对对象进行的阶乘函数
{
	cstring s("1"),temp_1;
	temp_1.str=x.str;
	if(x.str=="1"||x.str=="0")
	{
	    x.str="1";
	    return x;
	}
	else
	{
	    temp_1=temp_1.sub(temp_1,s);
        while(temp_1.str!=s.str)
		{
		    x=x.multi(x,temp_1);
		    temp_1=temp_1.sub(temp_1,s);
		}
	return x;
	}
}///:p
inline cstring cstring::div(cstring x,cstring y)//定义大数除法,x为被除数,y为除数
{
	cstring r;//cout("1");
	int k=x.compare(x,y);//k=0表示x<y,k=1表示x>y;k=2表示x=y;
	if(k==0)
	{
		r.str="0";
		r.resi=x.str;//r.resi存余数
		return r;
	}
	else if(k==2)
	{
		r.str="1";
		r.resi="0";
		return r;
	}
	else//一定x>y
	{
		int len_x=x.length(),len_y=y.length(),cp;
		if(len_x==len_y)
		{		
			for(int i3=0;;i3++)
				{
				    x=x.sub(x,y);
					if((cp=x.compare(x,y))==0) break;
				}
			r.str=(char)(i3+1+48);
			r.resi=x.str;
			return r;
		}///
		else//len_x>len_y
		{
		cstring temp;
		for(int i=0;i<len_y;i++)
			temp.str+=x.str[i];
		for(int j=0;j<=(len_x-len_y);j++)
		{
			cp=x.compare(temp,y);
			if(cp==1||cp==2)
			{
			    for(int i1=0;;i1++)
				{//i1<=9
                    temp=temp.sub(temp,y);
                    if((cp=temp.compare(temp,y))==0) break;
				}
			    r.str+=(char)(i1+1+48);
			    r.resi=temp.str;
				temp.str+=x.str[len_y+j];
			}
			else
			{
				if(j!=0)
				    r.str+='0';
				r.resi=temp.str;
				temp.str+=x.str[len_y+j];
			}
		}
		return r;
		}
	}
}///:p
    
//////终于成功了^_^^_^^_^^_^^_^ 
inline cstring cstring::combination(cstring m,cstring n)//组合函数
{    
	cstring m_temp("2");
	m_temp=m_temp.div(m,m_temp);
	int k=m.compare(m_temp,n);
	if(k==0)
		n=n.sub(m,n);
	cstring result_1,temp_1,temp_2;
	temp_1=temp_1.sub(m,n);
	temp_2=temp_1.factorial(temp_1);
	temp_1=temp_1.factorial(n);
	temp_1=temp_2.multi(temp_2,temp_1);
	temp_2=temp_2.factorial(m);
	result_1=result_1.div(temp_2,temp_1);
	return result_1;
}///:p
int main()
{
	ifstream in("input.txt");
	if(in.fail())
    {
		cout<<"error!"<<endl;
		exit(1);
	}
	ofstream out("output.txt");
	string s1,s2;
	in>>s1;
	in>>s2;
    cstring m(s1),n(s2),result_1,result_2,temp_2("1"),temp_3("2");
	result_1=result_1.combination(m,n);
    temp_2=temp_2.add(m,temp_2);
    temp_3=temp_3.multi(temp_3,m);
	temp_3=temp_3.combination(temp_3,m);
	result_2=result_2.div(temp_3,temp_2);
	result_1.print_files(out);
	result_2.print_files(out);
	return 0;
}///:p