C&C++   发布时间:2022-04-13  发布网站:大佬教程  code.js-code.com
大佬教程收集整理的这篇文章主要介绍了C语言程序设计100例之(65):方格填数大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
@H_675_0@例65  方格填数

问题描述

给一个n*n的方格矩阵,还有n*n个整数,让你将这些整数填入矩阵,使得每行每列每个对角线上整数的和都相等。下面给出几个例子:

 

C语言程序设计100例之(65):方格填数

输入

第一行一个整数n.(1<=n<=4)

第二行n*n个整数 ai (-10^8<=ai<=10^8)

输出

第一行一个整数s 代表每行每列每个对角线的和值

接下来输出一个n*n的矩阵,表示填数方案。

数据保证有解,可能存在多种方案,输出字典序最小的(将每行顺次相连之后,字典序最小)

输入样例

3

1 2 3 4 5 6 7 8 9

输出样例

15

2 7 6

9 5 1

4 3 8

        (1)编程思路。

        将输入的n*n个整数保存到数组a中,这n*n个整数的总和除以n的值保存到变量sum中。为了输出时输出字典序最小的,先将数组a中的n*n个数按从小到大顺序排列,这样可以保证最先得到的可行解是字典序最小的。

        之后按照从左到右从上到下的顺序将n*n个数填写到n*n个方格中。

        编写递归函数int dfs(int x, int y),其功能是对方格(x,y)填写数。每个格子可以在a[0]~a[n*n-1]中选取一个没有填过的数a[i](vis[i]=0时表示a[i]可以填写)进行填写,填写后,递归调用dfs(x,y+1)填写下一个格子(若y=n,则递归调用的下一个格子为dfs(x+1,1))。

        在递归调用过程中可以进行剪枝:在每一行或每一列填写结束时,可以调用相应函数int chkRow(int row)或int chkCol(int col)判断这一行或这一列之和是否等于 sum,若不等于,则直接返回0,无需继续搜索。

所有方格填写结束后,判断最后一行、最后一列和两条对角线的和值是否都等于sum,若都等于,则找到一个可行解,返回1。

(2)源程序。

#include <stdio.h>

#include <String.h>

int n, a[25], ans[5][5], sum;

int vis[25]={0};

int chkRow(int row)

{

    int i,tmp = 0;

    for (i=1; i<=n; i++)

        tmp+= ans[row][i];

    return tmp == sum;

}

int chkCol(int col)

{

    int i,tmp = 0;

    for (i=1; i<=n; i++)

        tmp += ans[i][col];

    return tmp == sum;

}

int chkX()

{

    int  i,tmp1 = 0, tmp2 = 0;

    for (i=1; i<=n; i++) {

        tmp1 += ans[i][i];

        tmp2 += ans[i][n+1-i];

    }

    return tmp1 == sum && tmp2 == sum;

}

int dfs(int x, int y)

{

    if (x==n+1 && y==1)

    {

       return chkRow(n) && chkCol(n) && chkX();

    }

    if (x > 1 && y == 1 && !chkRow(x-1)) return 0;

    if (x == n && y > 1 && !chkCol(y-1)) return 0;

    int  xx = x, yy = y+1;

    if (y==n) { xx=x+1;   yy = 1; }

    int i;

    for (i=0; i<n*n; i++) {

        if (!vis[i]) {

            vis[i] = 1;

            ans[x][y] = a[i];

            if (dfs(xx, yy)) return 1;

            vis[i] = 0;

        }

    }

    return 0;

}

int main()

{

    scanf("%d",&n);

    int i,j,t;

    for (i=0; i<n*n; i++) {

        scanf("%d",&a[i]);

        sum += a[i];

    }

    sum/= n;

    for (i=0;i<n*n-1;i++)

       for (j=0;j<n*n-1-i;j++)

           if (a[j]>a[j+1]){

              t=a[j];  a[j]=a[j+1];  a[j+1]=t;

           }

    dfs(1,1);

    printf("%d\n",sum);

    for (i=1; i<=n; i++) {

        printf("%d",ans[i][1]);

        for (j=2; j<=n; j++) {

            printf(" %d",ans[i][j]);

        }

        printf("\n");

    }

    return 0;

}

@H_675_0@习题65
65-1  数独

问题描述

数独是根据9×9 盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫内的数字均含1 - 9,不重复。每一道合格的数独谜题都有且仅有唯一答案,推理方法也以此为基础,任何无解或多解的题目都是不合格的。

芬兰一位数学家号称设计出全球最难的“数独游戏”,并刊登在报纸上,让大家去挑战。

这位数学家说,他相信只有“智慧最顶尖”的人才有可能破解这个“数独之谜”。

据介绍,目前数独游戏的难度的等级有一到五级,一是入门等级,五则比较难。不过这位数学家说,他所设计的数独游戏难度等级是十一,可以说是所以数独游戏中,难度最高的等级。他还表示,他目前还没遇到解不出来的数独游戏,因此他认为“最具挑战性”的数独游戏并没有出现。

输入

一个未填的数独。

输出格式

填好的数独。

输入样例

8 0 0 0 0 0 0 0 0

0 0 3 6 0 0 0 0 0

0 7 0 0 9 0 2 0 0

0 5 0 0 0 7 0 0 0

0 0 0 0 4 5 7 0 0

0 0 0 1 0 0 0 3 0

0 0 1 0 0 0 0 6 8

0 0 8 5 0 0 0 1 0

0 9 0 0 0 0 4 0 0

输出样例

8 1 2 7 5 3 6 4 9

9 4 3 6 8 2 1 7 5

6 7 5 4 9 1 2 8 3

1 5 4 2 3 7 8 9 6

3 6 9 8 4 5 7 2 1

2 8 7 1 6 9 5 3 4

5 2 1 9 7 4 3 6 8

4 3 8 5 2 6 9 1 7

7 9 6 3 1 8 4 5 2

         (1)编程思路。

        定义二维数组int map[10][10];来保存所填写的数独,输入数据后,map[i][j]!=0表示格子(i,j)(0<=i<=8,0<=j<=8)已事先填写了数据,map[i][j]==0表示格子(i,j)尚没有填写数据,需要在1~9中选择一个数进行填写。

        编写递归函数void dfs(int pos)对第pos个格子进行填写。显然,0<=pos<=80,当pos=81时,所有格子填写完毕,输出找到的解,同时置标志flag=1,这样可以结束后续的搜索,不再找其他的可行解。

        第pos个格子对应的坐标位置为(x=pos/9,y=pos%9),若map[x][y]!=0,则第pos个格子已预先填写了数据,递归调用dfs(pos+1)直接填写下一个格子;若map[x][y]==0,则需要对第pos个格子填写一个数据,此时将数组vis[10]的元素先全部初始化为0,vis[i]=0表示数字i可以填写,vis[i]=1表示数字i不能填写在第pos个格子中,然后将第pos个格子所在行填写过的数字map[x][k]对应的vis[map[x][k]]置为1,第pos个格子所在列填写过的数字map[k][y]对应的vis[map[k][y]]置为1,还将第pos个格子所在的小3*3格子中填写过的数字对应的vis元素也置为1,这样可以选取1~9中某个vis[i]=0的数字i填写到第pos个格子中,填写后递归调用dfs(pos+1)继续填写下一个格子,直到pos=81,所有格子填写完毕。

        (2)源程序。

#include <stdio.h>

#include <String.h>

int map[10][10];

int flag;

void dfs(int pos)

{

    int i,j;

    if (pos == 81){

        for (i=0; i<9; i++){

            for (j=0; j<9; j++){

                printf("%d ",map[i][j]);

            }

            printf("\n");

        }

        flag = 1;

        return ;

    }

    if (flag)

        return ;

    if (map[pos/9][pos%9]){

        dfs(pos+1);

    }

    else{

        int x=pos/9,y=pos%9;

        int vis[10];

        memset(vis,0,sizeof(vis));

        for (i=0; i<9; i++){

            if (x != i)

                vis[map[i][y]] = 1;

            if (y != i)

                vis[map[x][i]] = 1;

        }

        int tx = x/3*3;

        int ty = y/3*3;

        for (i=0; i<3; i++){

            for (j=0; j<3; j++){

                if (tx+i==x && ty+j==y)

                    conTinue;

                vis[map[tx+i][ty+j]] = 1;

            }

        }

        for (i=1; i<=9; i++){

            if (!vis[i]){

                map[x][y] = i;

                dfs(pos+1);

                if (flag)

                    return ;

                map[x][y] = 0;

            }

        }

    }

}

int main()

{

    int i,j;

    for (i=0; i<9; i++){

        for (j=0; j<9; j++)

          scanf("%d",&map[i][j]);

    }

    flag =0;

    dfs(0);

    return 0;

}

65-2  地毯填补问题

问题描述

相传在一个古老的阿拉伯国家里,有一座宫殿。宫殿里有个四四方方的格子迷宫,国王选择驸马的方法非常特殊,也非常简单:公主就站在其中一个方格子上,只要谁能用地毯将除公主站立的地方外的所有地方盖上,美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住,毯子的形状有所规定,只能有四种选择(如图):

C语言程序设计100例之(65):方格填数

并且每一方格只能用一层地毯,迷宫的大小为2k ×2k的方形。当然,也不能让公主无限制的在那儿等,对吧?由于你使用的是计算机,所以实现时间为1s。

输入

输入文件共2 行。

第一行:k,即给定被填补迷宫的大小为2k ×2k (0<k≤10);

第二行:x,y,即给出公主所在方格的坐标(x为行坐标,y为列坐标),x和 y之间有一个空格隔开。

输出

将迷宫填补完整的方案:每一行为x y c(x,y为毯子拐角的行坐标和列坐标, c为使用毯子的形状,具体见上面的图1,毯子形状分别用 1,2,3,4表示,x,y,c之间用一个空格隔开)。

输入样例

3                         

3 3  

输出样例

5 5 1

2 2 4

1 1 4

1 4 3

4 1 2

4 4 1

2 7 3

1 5 4

1 8 3

3 6 3

4 8 1

7 2 2

5 1 4

6 3 2

8 1 2

8 4 1

7 7 1

6 6 1

5 8 3

8 5 2

8 8 1

        (1)编程思路。

        大小为2k ×2k的迷宫可以分割成为4个2(k-1)*2(k-1)的小迷宫,分别标记为左上角迷宫。右上角迷宫、左下角迷宫和右下角迷宫,如图1所示。

 

C语言程序设计100例之(65):方格填数

              图1   4个小迷宫

        公主的位置必然在这四个小迷宫的某个迷宫内,其余三个小迷宫中没有被公主占用。可以使用一个“L”型毯子覆盖在这三个小迷宫的汇合之处,这个“L”型毯子的3个小块一定在每个小迷宫中放置1个,这样可以将这三个小块各看成一个“假公主”,这样4个小迷宫中每个迷宫中均有1个位置被公主占用,由此可以将2k ×2k的迷宫地毯填补问题分割成为4个较小规模的2(k-1)*2(k-1)的小迷宫地毯填补问题,递归这种分割,直至小迷宫转化为1*1的1个格子。

        例如,设公主在左上角的小迷宫中,这样可以在其余3个小迷宫交汇处放置1个“1”行地毯,这样每个小迷宫中均有1个格子放置了公主,如图2所示。

 

C语言程序设计100例之(65):方格填数

          图2 公主在左上角迷宫中

        进一步以样例为例进行描述,样例中公主的坐标为(3,3),位于左上角小迷宫中,左上角的4x4小迷宫中公主占了1格,就还剩15个方格,这样15/3=5余0,则可以把地毯铺完。按图2思想,在剩下3个4x4的小迷宫的交汇处铺上一个地毯(即(5,5,1)),使其各占1格,从16变为15格,这样也可保证地毯可以正好铺满。然后对每个小迷宫各自进一步递归,如图3所示。

 

C语言程序设计100例之(65):方格填数

           图3 样例的递归示例

        编写递归函数void laying(int a,int b,int x,int y,int len)来铺设地毯,其中参数a,b代表当前小迷宫的左上角顶点,x,y代表公主位置,len表示迷宫大小为len*len。

        若x<=a+len/2-1 && y<=b+len/2-1,则公主在左上角小迷宫中,此时在其余3个小迷宫的交汇处铺设一个“1”型地毯,用语句printf("%d %d 1\n",a+len/2,b+len/2);输出即可,这样原来大小为len*len的迷宫可以分割为4个(len/2)*(len/2)的小迷宫,因此递归调用如下:

laying(a,b,x,y,len/2);

laying(a,b+len/2,a+len/2-1,b+len/2,len/2);

laying(a+len/2,b,a+len/2,b+len/2-1,len/2);

laying(a+len/2,b+len/2,a+len/2,b+len/2,len/2);

       同理可以处理公主在右上角、左下角和右下角的情形。

       需要注意的是按样例的输出,递归的顺序应该是左上角,右上角,左下角,右下角。

      (2)源程序。

#include <stdio.h>

void laying(int a,int b,int x,int y,int len)

// a,b代表当前棋盘的左上角顶点,x,y代表公主位置

{

       if (len==1) return ;

       len=len/2;

       if (x<=a+len-1 && y<=b+len-1)  // 公主在左上角棋盘

       {

              printf("%d %d 1\n",a+len,b+len);

              laying(a,b,x,y,len);

              laying(a,b+len,a+len-1,b+len,len);

              laying(a+len,b,a+len,b+len-1,len);

              laying(a+len,b+len,a+len,b+len,len);

        }

        else if (x<=a+len-1 && y>b+len-1) // 公主在右上角棋盘

        {

             printf("%d %d 2\n",a+len,b+len-1);

             laying(a,b,a+len-1,b+len-1,len);

             laying(a,b+len,x,y,len);

             laying(a+len,b,a+len,b+len-1,len);

             laying(a+len,b+len,a+len,b+len,len);

       }

       else if (x>a+len-1 && y<=b+len-1)  //公主在左下角棋盘

       {

              printf("%d %d 3\n",a+len-1,b+len);

              laying(a,b,a+len-1,b+len-1,len);

              laying(a,b+len,a+len-1,b+len,len);

              laying(a+len,b,x,y,len);

              laying(a+len,b+len,a+len,b+len,len);

       }

       else                             // 公主在右下角棋盘

      {

              printf("%d %d 4\n",a+len-1,b+len-1);

              laying(a,b,a+len-1,b+len-1,len);

              laying(a,b+len,a+len-1,b+len,len);

              laying(a+len,b,a+len,b+len-1,len);

              laying(a+len,b+len,x,y,len);

       }

}

int main()

{

       int m;

       int k,x,y;

       scanf("%d %d %d",&k,&x,&y);

       m=1<<k;

       laying(1,1,x,y,m);

       return 0;

}

65-3  康托集

问题描述

康托集是由乔治·康托发现的。它是一种更简单的分形。这是一个无限过程的结果,因此对于这个程序,打印整个集合的近似值就足够了。以下步骤描述了输出给定整数n所对应近似康托集的一种方法:

1)以长度为n3的一串破折号构成的虚线开始

2)将虚线的中间三分之一替换为空格。在原始字符串的每一端留下一根由连续的破折号构成的虚线。

3)将每组虚线的中间三分之一再替换为空格。重复此操作,直到每组虚线由一个破折号组成。

例如,如果近似顺序为3,则从包含27个破折号的字符串开始:

---------------------------

将虚线中间三分之一变成空格 :

---------     ---------

然后再将每组虚线中间三分之一变成空格:

---  ---     ---  ---

再来一遍:

- -  - -     - -  - -

当破折号组的长度均为1时,此过程停止。输出时不应该打印程序中的中间步骤。只应显示上面最后一行给出的最终结果。

输入

输入包括多组测试用例。每个测试用例占一行,为一个介于0和12之间(包括0和12)的数字。

输出

必须输出康托集的近似值,后跟换行符。在康托集近似前后没有空格。行中应该出现的唯一字符是“-”和“ ”。

输入样例

0

1

3

输出样例

-

- -

- -   - -         - -   - -

         (1)编程思路。

         设S(n)表示长度为n3的近似康托集,显然可以发现S(n)=S(n-1)+n*n*n/3个空格+S(n-1)。

         编写递归函数void cantor(int s,int E),参数s和e分别表示描述近似康托集字符串的开始位置和结束位置,显然若e-s==1,字符串中1个字符,直接赋值为“-”,递归调用结束;否则,分别对前三分之一进行递归调用cantor(s,s+(e-s)/3); ,对后三分之一进行递归调用cantor(s+2*(e-s)/3,E); 。

      (2)源程序1。

#include <stdio.h>

#include <String.h>

char ans[1000000];

void cantor(int s,int E)

{

       if (e-s==1)

       {

              ans[s]='-';

              return;

       }

       int len=(e-s)/3;

       cantor(s,s+len);       // 对前三分之一进行递归

       cantor(s+2*len,E);     // 对后三分之一进行递归

}

int main()

{

       int i,n,len,a[13]={1};

       for (i=1;i<=12;i++)

          a[i]=a[i-1]*3;

       while(scanf("%d",&n)!=EOF)

       {

              len = a[n];

              memset(ans,' ',sizeof(ans));    //对整个数组赋值为空格

              cantor(0,len);

              for (i=0;i<len;i++)

                     printf("%c",ans[i]);

              printf("\n");

       }

       return 0;

}

        也可以编写非递归程序如下。

      (3)源程序2。

#include <stdio.h>

#include <String.h>

char ans[13][540000];

int main()

{

       int i,j,a[13]={1};

       for (i=1;i<=12;i++)

          a[i]=a[i-1]*3;

    strcpy(ans[0],"-");

    strcpy(ans[1],"- -");

    for (i=2; i<=12;i++)

    {

        strcpy(ans[i],ans[i-1]);

        int k=strlen(ans[i-1]);

        for (j = 0; j<k; j++)

            ans[i][j+k]=' ';

        ans[i][2*k]='\0';

        strcat(ans[i],ans[i-1]);

    }

    int n;

    while (scanf("%d",&n)!=EOF)

    {

        printf("%s\n",ans[n]);

    }

    return 0;

}

大佬总结

以上是大佬教程为你收集整理的C语言程序设计100例之(65):方格填数全部内容,希望文章能够帮你解决C语言程序设计100例之(65):方格填数所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。
标签: