高精度.txt

上次站长没用!今次打包几个ACM的资料在上传

    data=temp_change;
    delete [] result;
    return *this;
}///:p

cata &cata::operator /(const cata &y)
{
    int k=compare_cata(*this,y);                      //注意,以下假设x为除数,y为被除数  x>y  k=1,x<y  k=0,x==y  k=2;
    if(0==k)                                          //当x<y时,so easy^_^
    {
        resi.p_resi=new int [length()];
        if(NULL==resi.p_resi)
        {
            cout<<"the error take place in resi"<<endl;
            exit(1);
        }
        for(int i=0;i<length();i++)
        {
            resi.p_resi[i]=data[i];
        }
        resi.len_resi=length();
        delete [] data;
        data=new int [1];
        data[0]=0;
        n=1;
        return *this;
    }
    else if(2==k)                                    //当x==y时,so easy too^_^
    {

        delete [] data;
        data=new int [1];
        if(NULL==data)
        {
            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;
        }
    }    
}///:p

inline cata &cata::operator =(const cata &y)
{
    if(this->n!=y.n)
    {
        delete [] data;
        data=new int [y.n];
        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;
    return *this;
}///:p

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;
            }
        }
    }
}///:p

void result(cata &m,cata &n,cata &result_combination,cata &result_catalan)          //出结果函数
{
    int cp;
    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((cp=compare_cata(m/temp_2,n))==0)
    {
        m=combination_m;
        n=m-n;
        combination_n=n;    
        m=combination_m;
    }

    else
    {
        m=combination_m;
        combination_n=n;
    }
    int cp_boundary=cp;
    temp_finish=m-n+temp_1;
    temp_n=temp_1;
    temp_n+n;

    m=combination_m;
    while((cp=compare_cata(combination_m,temp_finish))==1)
    {
        combination_m-temp_1;
        m*combination_m;
    }
                                                    
    while((cp=compare_cata(combination_n,temp_1))==1)
    {
        combination_n-temp_1;
        n*combination_n;
    }
  
    cata catalan_div;
    if(cp_boundary!=2)
    {
        catalan_div=temp_finish-temp_1;                            //catalan_div存放这catalan的除数
        while((cp=compare_cata(temp_finish,temp_n))==1)
        {
            temp_finish-temp_1;
            catalan_div*temp_finish;
        }
        catalan_div*m*n;                                            //为提高效率,尽量用到了已知的m,n来算catalan_div,即m!
    }
    else
    {
        catalan_div=temp_1;
        catalan_div*m*n;
    }
    result_combination=m/n;

    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;
    }
    result_catalan=m/catalan_div;
}///:p

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;
}///:p

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");
    string str1,str2;
    in>>str1>>str2;
    cata data1,data2,result_combination,result_catalan;
    data1.getdata(str1);
    data2.getdata(str2);
    bool deal_boundary=dispose_boundary(data1,data2);
    if(!deal_boundary)
    {
        boundary_result(data1,result_combination,result_catalan);
    }
    else
    {
        result(data1,data2,result_combination,result_catalan);
    }
    result_combination.printcata(out);
    result_catalan.printcata(out);
    finish=clock();
    cout<<finish-start<<endl;
    delete [] resi.p_resi;
    return 1;
}