cata.cpp

FZU 大二 的数据结构与算法 老师出的题目的优秀作业 第2到第5章

            cout<<"the error occur in /"<<endl;
            exit(1);
        }
        data[0]=1;
        n=1;
        resi.p_resi=new int [1];
        resi.p_resi[0]=0;
        resi.len_resi=1;
        return *this;
    }
    else                                             //一定x>y,分两种情况1.len_x==len_y   2.len_x>len_y
    {
        int len_x=length(),len_y=y.length(),cp;
        if(len_x==len_y)                             //len_x==len_y,只要循环减,减的次数为商
        {
            for(int i3=0;;i3++)
            {
                *this-y;
                if((cp=compare_cata(*this,y))==0)
                {
                    break;
                }
            }
            resi.p_resi=data;
            resi.len_resi=length();
            data=new int [1];
            if(NULL==data)
            {
                exit(1);
            }
            data[0]=i3+1;
            n=1;
            return *this;
        }
        else                                         //len_x>len_y,以下为除法的精髓
        {
            cata temp(len_x);
            for(int i=0;i<len_x-len_y;i++)
            {
                temp.data[i]=0;
            }
            for(int j=len_x-len_y;j<len_x;j++)
            {
                temp.data[j]=y.data[j-len_x+len_y];
            }
            temp.n=len_x;
            int *result=new int [len_x-len_y+1];     //result存放商
            if(NULL==result)
            {
                cout<<"the error occur in /"<<endl;
                exit(1);
            }
            for(j=0;j<=(len_x-len_y);j++)
            {
                cp=compare_cata(*this,temp);
                if(1==cp||2==cp)
                {
                    for(int i1=0;;i1++)
                    {
                        *this-temp;
                        if((cp=compare_cata(*this,temp))==0)
                        {
                            break;
                        }
                    }
                    result[len_x-len_y-j]=i1+1;
                }
                else                                //cp==0
                {
                    result[len_x-len_y-j]=0;
                }
                temp.del_first();                   //删去首单元
            }
            resi.p_resi=data;                       //余数最后在this->data中
            resi.len_resi=n;
            this->data=result;
            this->n=len_x-len_y+1;
            int cycle=1;                            //除法有可能在商的高位产生0,用cycle进行回溯,去除无用0
            while(result[n-cycle]==0&&cycle<n) 
            {
                cycle++;
            }
            n=n-cycle+1;
            result=NULL;
            return *this;
        }
    }    
}

inline cata &cata::operator =(const cata &y)
{
    if(this->MaxSize!=y.MaxSize)
    {
        delete [] data;
        data=new int [y.MaxSize];
        if(NULL==data)
        {
            cout<<"the error take palce in operator ="<<endl;
            exit(1);
        }
    }
    for(int i=0;i<y.n;i++)
    {
        data[i]=y.data[i];
    }
    n=y.n;
	MaxSize=y.MaxSize ;
    return *this;
}

int compare_cata(const cata &x,const cata &y)         //x>y return 1;x<y return 0;x==y return 2;
{
    int len_x=x.length(),len_y=y.length();
    int displace=y.displacement;
    if(len_x>len_y)
    {
        return 1;
    }
    else if(len_x<len_y)
    {
        return 0;
    }
    
    else
    {
        for(int i=len_x-1;i>=0;i--)
        {
            if(x.data[i]!=y.data[i+displace])
            {
                break;
            }
        }
        if(-1==i)
        {
            return 2;
        }
        else
        {
            if(x.data[i]>y.data[i+displace])
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }
    }
}
cata & cata::operator *(int y)   
{
	int carry=0;
	int k=y;
	for(int i=0;i<n;i++)
	{
		data[i]*=y;
		data[i]+=carry;
		carry=data[i]/10;
		data[i]%=10;
	}
	while(carry)
	{
		if(n<MaxSize)
		{
			data[n++]=carry%10;
			carry/=10;
		}
		else
		{
			MaxSize+=10;
			int *p=new int[MaxSize];
			for(i=0;i<n;i++)
				p[i]=data[i];
			delete[] data;
			data=p;
			data[n++]=carry%10;
			carry/=10;
		}
	}
	return *this;
}

void result(int m,int n,cata &result_combination,cata &result_catalan)           //出结果函数
{
    int cp;
	int *a,i,j;
	a = new int[m];
    cata temp_1(1),temp_2(1),temp_1_1;
    temp_1.data[0]=1,temp_2.data[0]=2;
    temp_1.n=1,temp_2.n=1;
    temp_1_1=temp_1;
    cata combination_m,combination_n,temp_n,catalan_m,temp_finish;
    catalan_m=combination_m=m;
	if(n> m - n)
		n = m - n;
	result_combination = result_catalan = temp_1;
	if(n)
	{
		for(i = 1;i < n;i++)
			a[i] = n - i + 1;
		for(j = m;j>m-n;j--)
		{
			cp = j;
			for(i= 1;i<n&&cp>a[i];i++)
				if(a[i]!=1&&cp%a[i]==0)
				{
					cp/=a[i];
					a[i]=1;
				}
			for(i = 1;i<n &&cp>1;i++)
				if(a[i]>=cp&&a[i]%cp==0)
				{
					a[i]/=cp;
					cp=1;
					break;
				}
			if(cp>1)
				result_combination*cp;
		}
		for(i=1;i<n;i++)
			if(a[i]!=1)
				temp_2*a[i];
		result_combination*2;
		result_combination/temp_2;
	}
	for(i=1;i<m;i++)
		a[i]=m-i+1;
	for(j=2*m;j>m+1;j--)
	{
		cp=j;
		for(i=1;i<m&&cp>a[i];i++)
			if(a[i]!=1&&cp%a[i]==0)
			{
				cp/=a[i];
				a[i]=1;
			}
		for(i=1;i<m&&cp>1;i++)
			if(a[i]>=cp&&a[i]%cp==0)
			{
				a[i]/=cp;
				cp=1;
				break;
			}
		if(cp>1)
			result_catalan*cp;
	}
	for(i=1;i<m;i++)
		if(a[i]>1)
			temp_1*a[i];
	result_catalan/temp_1;
	delete[] a;
}
void boundary_result(cata &m,cata &result_combination,cata &result_catalan)
{
    int cp;
    cata temp_1(1),temp_2(1),temp_1_1,catalan_m,catalan_div;
    temp_1.data[0]=1,temp_2.data[0]=2;
    temp_1.n=1,temp_2.n=1;
    result_combination=temp_1;
    temp_1_1=temp_1;
    catalan_div=catalan_m=m;

    temp_1+catalan_m+temp_1_1;
    m=catalan_m*temp_2;
    while((cp=compare_cata(catalan_m,temp_1))==1)
    {
        catalan_m-temp_1_1;
        m*catalan_m;
    }

    catalan_m=catalan_div;
    while((cp=compare_cata(catalan_m,temp_1_1))==1)
    {
        catalan_m-temp_1_1;
        catalan_div*catalan_m;
    }

    result_catalan=m/catalan_div;
}

inline void cata::printcata(ofstream &out) const
{
    for(int i=n-1;i>=0;i--)
    {
        out<<data[i];
    }
    out<<endl;
}


clock_t finish,start;

int main()
{
    start=clock();
    ifstream in("input.txt");
    if(in.fail())
    {
        exit(1);
    }
    ofstream out("output.txt");
	int m,n;
	in>>m>>n;
    cata result_combination,result_catalan;
    result(m,n,result_combination,result_catalan);
    result_combination.printcata(out);
    result_catalan.printcata(out);
    finish=clock();
    cout<<finish-start<<endl;
    delete [] resi.p_resi;
    return 1;
}

//程序不足之处分析  编程任务与输入输出说明