计算机算法设计与分析作业01：分治法求解大数乘法+L型骨牌的棋盘覆盖问题

小鱼儿 2022-09-26 02:16 116阅读 0赞

1.分治法求解大数乘法：

代码实现：

有bug版，主要是add()和sub()函数写的有问题，大数分治的思路是正确的。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    void out(int ppp[],int pppn)
    {
        for(int i=0; i<pppn+2; i++)
        {
            cout<<ppp[i]<<" ";
        }
        cout<<endl;
    }
    
    void yiwei(int ppp[],int posn)
    {
        for(int i=ppp[0]+1; i>=2; i--)
        {
            ppp[i+posn]=ppp[i];
        }
        for(int i=2; i<2+posn; i++)
        {
            ppp[i]=0;
        }
        for(int i=2+ppp[0]+posn; i>=2; i--)
        {
            if(ppp[i]!=0)
            {
                ppp[0]=i-2+1;
                break;
            }
        }
    }
    
    void sub(int a1[],int b1[],int c1[])
    {
        memset(c1,0,sizeof(c1));
        if(a1[1]==1&&b1[1]==-1)///正数减负数，相当于两个正数相加
        {
            c1[1]=1;
            int i;
            int nnn=min(a1[0],b1[0]);
            for(i=2; i<nnn+2; i++)
            {
                int tmp=a1[i]+b1[i];
                c1[i]+=tmp%10;
                c1[i+1]=tmp/10;
            }
            if(nnn<a1[0])
            {
                int j;
                for(j=i;j<a1[0]+2;j++)
                {
                    int tmp=a1[j]+c1[j];
                    c1[j]=tmp%10;
                    c1[j+1]=tmp/10;
                }
                if(c1[j]>0)
                {
                    c1[0]=a1[0]+1;
                }
                else
                {
                    c1[0]=a1[0];
                }
                //out(c1,c1[0]);
            }
            else
            {
                int j;
                for(j=i;j<b1[0]+2;j++)
                {
                    int tmp=b1[j]+c1[j];
                    c1[j]=tmp%10;
                    c1[j+1]=tmp/10;
                }
                if(c1[j]>0)
                {
                    c1[0]=b1[0]+1;
                }
                else
                {
                    c1[0]=b1[0];
                }
                //out(c1,c1[0]);
            }
        }
        else if(a1[1]==-1&&b1[1]==1)///负数减正数，相当于两个负数相加
        {
            c1[1]=-1;
            int i;
            int nnn=min(a1[0],b1[0]);
            for(i=2; i<nnn+2; i++)
            {
                int tmp=a1[i]+b1[i];
                c1[i]+=tmp%10;
                c1[i+1]=tmp/10;
            }
            if(nnn<a1[0])
            {
                int j;
                for(j=i;j<a1[0]+2;j++)
                {
                    int tmp=a1[j]+c1[j];
                    c1[j]=tmp%10;
                    c1[j+1]=tmp/10;
                }
                if(c1[j]>0)
                {
                    c1[0]=a1[0]+1;
                }
                else
                {
                    c1[0]=a1[0];
                }
                //out(c1,c1[0]);
            }
            else
            {
                int j;
                for(j=i;j<b1[0]+2;j++)
                {
                    int tmp=b1[j]+c1[j];
                    c1[j]=tmp%10;
                    c1[j+1]=tmp/10;
                }
                if(c1[j]>0)
                {
                    c1[0]=b1[0]+1;
                }
                else
                {
                    c1[0]=b1[0];
                }
                //out(c1,c1[0]);
            }
        }
        else if(a1[1]==1 && b1[1]==1) ///正数减正数，先减一次判断一下符号，若为大数减小数，
        {///则直接减，若为小数减大数，则要重新减一次；负数减负数同样，但需要注意符号
            int aa1[210];
            int bb1[210];
            memset(aa1,0,sizeof(aa1));
            memset(bb1,0,sizeof(bb1));
            for(int i=0; i<a1[0]+2; i++)
            {
                aa1[i]=a1[i];
            }
            for(int i=0; i<b1[0]+2; i++)
            {
                bb1[i]=b1[i];
            }
            /*out(aa1,aa1[0]);
            out(bb1,bb1[0]);
            out(c1,c1[0]);*/
            for(int i=2; i<aa1[0]+2; i++)
            {
                if(aa1[i]>=bb1[i])
                {
                    c1[i]=aa1[i]-bb1[i];
                }
                else
                {
                    c1[i]=aa1[i]+10-bb1[i];
                    aa1[i+1]--;
                }
            }
            if(aa1[aa1[0]+2]==-1)
            {
                c1[1]=-1;
                memset(aa1,0,sizeof(aa1));
                for(int i=0; i<a1[0]+2; i++)
                {
                    aa1[i]=a1[i];
                }
                for(int i=0; i<b1[0]+2; i++)
                {
                    bb1[i]=b1[i];
                }
                for(int i=2; i<aa1[0]+2; i++)
                {
                    if(bb1[i]>=aa1[i])
                    {
                        c1[i]=bb1[i]-aa1[i];
                    }
                    else
                    {
                        c1[i]=bb1[i]+10-aa1[i];
                        bb1[i+1]--;
                    }
                }
            }
            else
            {
                c1[1]=1;
            }
            for(int i=aa1[0]+5; i>=2; i--)
            {
                if(c1[i]!=0)
                {
                    c1[0]=i-2+1;
                    break;
                }
            }
        }
        else if(a1[1]==-1 && b1[1]==-1)
        {
            int aa1[210];
            int bb1[210];
            memset(aa1,0,sizeof(aa1));
            memset(bb1,0,sizeof(bb1));
            for(int i=0; i<a1[0]+2; i++)
            {
                aa1[i]=a1[i];
            }
            for(int i=0; i<b1[0]+2; i++)
            {
                bb1[i]=b1[i];
            }
            for(int i=2; i<bb1[0]+2; i++)
            {
                if(bb1[i]>=aa1[i])
                {
                    c1[i]=bb1[i]-aa1[i];
                }
                else
                {
                    c1[i]=bb1[i]+10-aa1[i];
                    bb1[i+1]--;
                }
            }
            if(bb1[bb1[0]+2]==-1)
            {
                c1[1]=-1;
                memset(aa1,0,sizeof(aa1));
                for(int i=0; i<a1[0]+2; i++)
                {
                    aa1[i]=a1[i];
                }
                memset(bb1,0,sizeof(bb1));
                for(int i=0; i<b1[0]+2; i++)
                {
                    bb1[i]=b1[i];
                }
                for(int i=2; i<bb1[0]+2; i++)
                {
                    if(aa1[i]>=bb1[i])
                    {
                        c1[i]=aa1[i]-bb1[i];
                    }
                    else
                    {
                        c1[i]=aa1[i]+10-bb1[i];
                        aa1[i+1]--;
                    }
                }
            }
            else
            {
                c1[1]=-1;
            }
            for(int i=aa1[0]+5; i>=2; i--)
            {
                if(c1[i]!=0)
                {
                    c1[0]=i-2+1;
                    break;
                }
            }
        }
    }
    
    void add(int a1[],int b1[],int c1[])
    {
        if(a1[1]==b1[1])
        {
            c1[1]=a1[1];
            int i;
            int nnn=min(a1[0],b1[0]);
            for(i=2; i<nnn+2; i++)
            {
                int tmp=a1[i]+b1[i];
                c1[i]+=tmp%10;
                c1[i+1]=tmp/10;
            }
            if(nnn<a1[0])
            {
                int j;
                for(j=i;j<a1[0]+2;j++)
                {
                    int tmp=a1[j]+c1[j];
                    c1[j]=tmp%10;
                    c1[j+1]=tmp/10;
                }
                if(c1[j]>0)
                {
                    c1[0]=a1[0]+1;
                }
                else
                {
                    c1[0]=a1[0];
                }
                //out(c1,c1[0]);
            }
            else
            {
                int j;
                for(j=i;j<b1[0]+2;j++)
                {
                    int tmp=b1[j]+c1[j];
                    c1[j]=tmp%10;
                    c1[j+1]=tmp/10;
                }
                if(c1[j]>0)
                {
                    c1[0]=b1[0]+1;
                }
                else
                {
                    c1[0]=b1[0];
                }
                //out(c1,c1[0]);
            }
        }
        else if(a1[1]==-1&&b1[1]==1)
        {
            int aa1[210];
            memset(aa1,0,sizeof(aa1));
            for(int i=0; i<a1[0]+2; i++)
            {
                aa1[i]=a1[i];
            }
            aa1[1]=1;
            sub(b1,aa1,c1);
        }
        else if(a1[1]==1 && b1[1]==-1)
        {
            int bb1[210];
            memset(bb1,0,sizeof(bb1));
            for(int i=0; i<b1[0]+2; i++)
            {
                bb1[i]=b1[i];
            }
            bb1[1]=1;
            sub(a1,bb1,c1);
        }
    }
    
    void mult(int XX[],int YY[],int nn,int ZZ[])
    {
        //cout<<endl<<"yilun "<<endl<<endl;
        int m1[210],m2[210],m3[210],m4[210],m5[210],m6[210],m7[210],m8[210];
        int A[210],B[210],C[210],D[210];///每次都要重新申请A,B,C,D数组
        memset(A,0,sizeof(A));
        memset(B,0,sizeof(B));
        memset(C,0,sizeof(C));
        memset(D,0,sizeof(D));
        memset(m1,0,sizeof(m1));
        memset(m2,0,sizeof(m2));
        memset(m3,0,sizeof(m3));
        memset(m4,0,sizeof(m4));
        memset(m5,0,sizeof(m5));
        memset(m6,0,sizeof(m6));
        memset(m7,0,sizeof(m7));
        memset(m8,0,sizeof(m8));
        if(nn==1)
        {
            ZZ[1]=XX[1]*YY[1];
            int tmp=XX[2]*YY[2];
            if(tmp>9)
            {
                ZZ[0]=2;
                ZZ[2]=tmp%10;
                ZZ[3]=tmp/10;
            }
            else
            {
                ZZ[0]=1;
                ZZ[2]=tmp;
            }
            return ;
        }
        else
        {
            B[0]=A[0]=nn/2;///进行分治
            B[1]=A[1]=XX[1];
            for(int i=2; i<2+nn/2; i++)
            {
                B[i]=XX[i];
            }
            int k=2;
            for(int i=2+nn/2; i<=nn+1; i++)
            {
                A[k++]=XX[i];
            }
    
            C[0]=D[0]=nn/2;
            C[1]=D[1]=YY[1];
            for(int i=2; i<2+nn/2; i++)
            {
                D[i]=YY[i];
            }
            k=2;
            for(int i=2+nn/2; i<=nn+1; i++)
            {
                C[k++]=YY[i];
            }
            /*cout<<"After fenzhi :"<<endl;///测试分治用
            out(A,nn/2);
            out(B,nn/2);
            out(C,nn/2);
            out(D,nn/2);*/
    
            mult(A,C,nn/2,m1);
            /*cout<<"chengjim1  :"<<endl;
            out(m1,m1[0]);*/
    
    
            sub(A,B,m4);
            sub(D,C,m5);
            /*cout<<"After sub"<<endl;
            out(m4,m4[0]);
            out(m5,m5[0]);*/
    
            mult(m4,m5,nn/2,m2);
            /*cout<<"chengji  :"<<endl;
            out(m2,m2[0]);*/
    
            mult(B,D,nn/2,m3);
            /*cout<<"chengji2  :"<<endl;
            out(m3,m3[0]);*/
    
            add(m1,m2,m6);
            /*cout<<"m1+m2="<<endl;
            out(m6,m6[0]);*/
    
            add(m6,m3,m7);
            /*cout<<"m1+m2+m3="<<endl;
            out(m7,m7[0]);*/
    
            yiwei(m7,nn/2);
            //out(m7,m7[0]);
            yiwei(m1,nn);
            /*cout<<"m1yiweihou"<<endl;
            out(m1,m1[0]);*/
    
            add(m1,m7,m8);
            /*cout<<"m8="<<endl;
            out(m8,m8[0]);*/
            add(m8,m3,ZZ);
            /*cout<<"ZZ==="<<endl;
            out(ZZ,ZZ[0]);*/
        }
    }
    int main()
    {
        char xx[210],yy[210];
        int X[210],Y[210],Z[500];
        int n;
        while(scanf("%s%s",xx,yy)!=EOF)///输入两个长度相等且都为2^n的字符串(不带正负号)
        {
            int k;
            n=strlen(xx);
            if(xx[0]=='-')
            {
                X[1]=-1;
                k=n;
                for(int i=1; i<n; i++)
                {
                    X[k--]=xx[i]-'0';
                }
            }
            else
            {
                X[1]=1;
                k=n+1;
                for(int i=0; i<n; i++)
                {
                    X[k--]=xx[i]-'0';
                }
            }
            int m=strlen(yy);
            if(yy[0]=='-')
            {
                Y[1]=-1;
                k=m;
                for(int i=1; i<m; i++)
                {
                    Y[k--]=yy[i]-'0';
                }
            }
            else
            {
                Y[1]=1;
                k=m+1;
                for(int i=0; i<m; i++)
                {
                    Y[k--]=yy[i]-'0';
                }
            }
            n=min(n,m);
            X[0]=Y[0]=n;
            ///把字符数组转化为int数组，并进行逆序
            /*cout<<"The chushizhi is:"<<endl;
            out(X,n);
            out(Y,n);*/
            memset(Z,0,sizeof(Z));///最终存放结果
    
            mult(X,Y,n,Z);
            //add(X,Y,Z);
            if(X[1]==Y[1])
                Z[1]=1;
            else
                Z[1]=-1;
    
            //yiwei(X,2);//测试移位用
            //out(X,n+2);
            cout<<"The answer is:"<<endl;
            if(Z[1]==-1)
                printf("-");
            for(int i=Z[0]+1; i>=2; i--)
            {
                printf("%d",Z[i]);
            }
            printf("\n");
    
            memset(X,0,sizeof(X));
            memset(Y,0,sizeof(Y));
    
            /*int ans[210];//测试加减法用
            memset(ans,0,sizeof(ans));
            sub(X,Y,ans);
            out(ans,ans[0]);
            memset(ans,0,sizeof(ans));
            add(X,Y,ans);
            out(ans,ans[0]);*/
        }
        return 0;
    }

代码实现：

完善版，正确。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    
    using namespace std;
    
    void out(int ppp[],int pppn)
    {
        for(int i=0; i<pppn+2; i++)
        {
            cout<<ppp[i]<<" ";
        }
        cout<<endl;
    }
    
    void yiwei(int ppp[],int posn)
    {
        for(int i=ppp[0]+1; i>=2; i--)
        {
            ppp[i+posn]=ppp[i];
        }
        for(int i=2; i<2+posn; i++)
        {
            ppp[i]=0;
        }
        for(int i=2+ppp[0]+posn; i>=2; i--)
        {
            if(ppp[i]!=0)
            {
                ppp[0]=i-2+1;
                break;
            }
        }
    }
    
    int max(int *A, int *B)  //判断|A|>|B|吗？大于返回1，小于返回-1，等于返回0
    {
        int i;
        if(A[0]>B[0])
            return 1;
        else if(A[0]<B[0])
            return -1;
        else
        {
            i=A[0]+1;
            while(i>=2&&A[i]==B[i])
                i--;
            if(i<2)
                return 0;
            else if(A[i]>B[i])
                return 1;
            else
                return -1;
        }
    }
    
    void sublalala(int *A, int * B, int * C)  /* 同号的减法运算，要求A,B位数相同，先改成相同的 */
    {
        int i,d;     /* d为借位数 */
        if(A[0]>B[0])
        {
            for(i=B[0]+2; i<=A[0]+1; i++)
                B[i]=0;
            B[0]=A[0];
        }
        else if(B[0]>A[0])
        {
            for(i=A[0]+2; i<=B[0]+1; i++)
                A[i]=0;
            A[0]=B[0];
        }
    
        C[0]=A[0];
        d=0;
        if(max(A,B)==1)
        {
            for(i=2; i<=C[0]+1; i++)
            {
                if(A[i]>=(d+B[i]))
                {
                    C[i]=A[i]-d-B[i];
                    d=0;
                }
                else
                {
                    C[i]=A[i]+10-d-B[i];
                    d=1;
                }
            }
            C[1]=A[1];
        }
        else
        {
            for(i=2; i<=C[0]+1; i++)
            {
                if(B[i]>=(d+A[i]))
                {
                    C[i]=B[i]-d-A[i];
                    d=0;
                }
                else
                {
                    C[i]=B[i]+10-d-A[i];
                    d=1;
    
                }
            }
            C[1]=A[1]*-1;
        }
    }
    
    void add(int *A,int *B, int *C) /* C=A+B,带符号的加法运算 */
    {
        int i,j,d,temp;   /*  d为进位  */
        int D[256];
        i=2;
        d=0;
        if(A[1]*B[1]==1)  //A,B同号
        {
            while(i<=A[0]+1&&i<=B[0]+1)
            {
                temp=A[i]+B[i]+d;
                C[i]=temp%10;
                d=temp/10;
                i++;
            }
            while(i<=A[0]+1)
            {
                temp=A[i]+d;
                C[i]=temp%10;
                d=temp/10;
                i++;
            }
            while(i<=B[0]+1)
            {
                temp=B[i]+d;
                C[i]=temp%10;
                d=temp/10;
                i++;
            }
            if(d>0)
            {
                C[i]=d;
                C[0]=i-1;
            }
            else
                C[0]=i-2;
            C[1]=A[1];
        }
        else        //A,B不同号，转换为同号减法
        {
    
            D[0]=B[0];   //用D替换一下，保留B的值
            D[1]=B[1]*-1;
            for(i=2; i<=B[0]+1; i++)
                D[i]=B[i];
            sublalala(A,D,C);
        }
    }
    
    void mult(int XX[],int YY[],int nn,int ZZ[])
    {
        //cout<<endl<<"yilun "<<endl<<endl;
        int m1[210],m2[210],m3[210],m4[210],m5[210],m6[210],m7[210],m8[210];
        int A[210],B[210],C[210],D[210];///每次都要重新申请A,B,C,D数组
        memset(A,0,sizeof(A));
        memset(B,0,sizeof(B));
        memset(C,0,sizeof(C));
        memset(D,0,sizeof(D));
        memset(m1,0,sizeof(m1));
        memset(m2,0,sizeof(m2));
        memset(m3,0,sizeof(m3));
        memset(m4,0,sizeof(m4));
        memset(m5,0,sizeof(m5));
        memset(m6,0,sizeof(m6));
        memset(m7,0,sizeof(m7));
        memset(m8,0,sizeof(m8));
        if(nn==1)
        {
            ZZ[1]=XX[1]*YY[1];
            int tmp=XX[2]*YY[2];
            if(tmp>9)
            {
                ZZ[0]=2;
                ZZ[2]=tmp%10;
                ZZ[3]=tmp/10;
            }
            else
            {
                ZZ[0]=1;
                ZZ[2]=tmp;
            }
            return ;
        }
        else
        {
            B[0]=A[0]=nn/2;///进行分治
            B[1]=A[1]=XX[1];
            for(int i=2; i<2+nn/2; i++)
            {
                B[i]=XX[i];
            }
            int k=2;
            for(int i=2+nn/2; i<=nn+1; i++)
            {
                A[k++]=XX[i];
            }
    
            C[0]=D[0]=nn/2;
            C[1]=D[1]=YY[1];
            for(int i=2; i<2+nn/2; i++)
            {
                D[i]=YY[i];
            }
            k=2;
            for(int i=2+nn/2; i<=nn+1; i++)
            {
                C[k++]=YY[i];
            }
            /*cout<<"After fenzhi :"<<endl;///测试分治用
            out(A,nn/2);
            out(B,nn/2);
            out(C,nn/2);
            out(D,nn/2);*/
    
            mult(A,C,nn/2,m1);
            /*cout<<"chengjim1  :"<<endl;
            out(m1,m1[0]);*/
    
    
            sublalala(A,B,m4);
            sublalala(D,C,m5);
            /*cout<<"After sub"<<endl;
            out(m4,m4[0]);
            out(m5,m5[0]);*/
    
            mult(m4,m5,nn/2,m2);
            /*cout<<"chengji  :"<<endl;
            out(m2,m2[0]);*/
    
            mult(B,D,nn/2,m3);
            /*cout<<"chengji2  :"<<endl;
            out(m3,m3[0]);*/
    
            add(m1,m2,m6);
            /*cout<<"m1+m2="<<endl;
            out(m6,m6[0]);*/
    
            add(m6,m3,m7);
            /*cout<<"m1+m2+m3="<<endl;
            out(m7,m7[0]);*/
    
            yiwei(m7,nn/2);
            //out(m7,m7[0]);
            yiwei(m1,nn);
            /*cout<<"m1yiweihou"<<endl;
            out(m1,m1[0]);*/
    
            add(m1,m7,m8);
            /*cout<<"m8="<<endl;
            out(m8,m8[0]);*/
            add(m8,m3,ZZ);
            /*cout<<"ZZ==="<<endl;
            out(ZZ,ZZ[0]);*/
        }
    }
    int main()
    {
        char xx[210],yy[210];
        int X[210],Y[210],Z[500];
        int n;
        while(scanf("%s%s",xx,yy)!=EOF)///输入两个长度相等且都为2^n的字符串(不带正负号)
        {
            int k;
            n=strlen(xx);
            if(xx[0]=='-')
            {
                X[1]=-1;
                k=n;
                for(int i=1; i<n; i++)
                {
                    X[k--]=xx[i]-'0';
                }
            }
            else
            {
                X[1]=1;
                k=n+1;
                for(int i=0; i<n; i++)
                {
                    X[k--]=xx[i]-'0';
                }
            }
            int m=strlen(yy);
            if(yy[0]=='-')
            {
                Y[1]=-1;
                k=m;
                for(int i=1; i<m; i++)
                {
                    Y[k--]=yy[i]-'0';
                }
            }
            else
            {
                Y[1]=1;
                k=m+1;
                for(int i=0; i<m; i++)
                {
                    Y[k--]=yy[i]-'0';
                }
            }
            n=min(n,m);
            X[0]=Y[0]=n;
            ///把字符数组转化为int数组，并进行逆序
            /*cout<<"The chushizhi is:"<<endl;
            out(X,n);
            out(Y,n);*/
            memset(Z,0,sizeof(Z));///最终存放结果
    
            mult(X,Y,n,Z);
            //add(X,Y,Z);
            if(X[1]==Y[1])
                Z[1]=1;
            else
                Z[1]=-1;
    
            //yiwei(X,2);//测试移位用
            //out(X,n+2);
            cout<<"The answer is:"<<endl;
            if(Z[1]==-1)
                printf("-");
            for(int i=Z[0]+1; i>=2; i--)
            {
                printf("%d",Z[i]);
            }
            printf("\n");
    
            memset(X,0,sizeof(X));
            memset(Y,0,sizeof(Y));
    
            /*int ans[210];//测试加减法用
            memset(ans,0,sizeof(ans));
            sub(X,Y,ans);
            out(ans,ans[0]);
            memset(ans,0,sizeof(ans));
            add(X,Y,ans);
            out(ans,ans[0]);*/
        }
        return 0;
    }

2.L型骨牌的棋盘覆盖问题：

代码实现：

#include <iostream>
    #include <cstdio>
    #include <cmath>
    
    using namespace std;
    
    const int maxn=2048;
    int Board[maxn][maxn];
    int tile=1;
    void ChessBoard(int tr,int tc,int dr,int dc,int size_b)
    {
        if(size_b==1) return ;
        int t=tile++,s=size_b/2;
        if(dr<tr+s && dc<tc+s)//左上角
        {
            ChessBoard(tr,tc,dr,dc,s);
        }
        else
        {
            Board[tr+s-1][tc+s-1]=t;
            ChessBoard(tr,tc,tr+s-1,tc+s-1,s);
        }
        if(dr<tr+s && dc>=tc+s)//右上角
        {
            ChessBoard(tr,tc+s,dr,dc,s);
        }
        else
        {
            Board[tr+s-1][tc+s]=t;
            ChessBoard(tr,tc+s,tr+s-1,tc+s,s);
        }
        if(dr>=tr+s && dc<tc+s)//左下角
        {
            ChessBoard(tr+s,tc,dr,dc,s);
        }
        else
        {
            Board[tr+s][tc+s-1]=t;
            ChessBoard(tr+s,tc,tr+s,dc+s-1,s);
        }
        if(dr>=tr+s && dc>=tc+s)//右下角
        {
            ChessBoard(tr+s,tc+s,dr,dc,s);
        }
        else
        {
            Board[tr+s][tc+s]=t;
            ChessBoard(tr+s,tc+s,tr+s,tc+s,s);
        }
    }
    
    int main()
    {
        int n,dr,dc;
        cout<<"请输入棋盘的边长大小：(2^n)"<<endl;
        scanf("%d",&n);
        cout<<"请输入特殊方格的位置："<<endl;
        scanf("%d%d",&dr,&dc);
        cout<<"对棋盘进行覆盖后得到："<<endl;
        ChessBoard(0,0,dr,dc,pow(2,n));
        for(int i=0;i<pow(2,n);i++)
        {
            for(int j=0;j<pow(2,n);j++)
            {
                printf("%3d ",Board[i][j]);
            }
            cout<<endl;
        }
        return 0;
    }