C语言程序设计100例之（65）：方格填数

本文主要是介绍C语言程序设计100例之（65）：方格填数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

例65  方格填数

问题描述

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

 

输入

第一行一个整数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;

}

习题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  地毯填补问题

问题描述

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

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

输入

输入文件共2 行。

第一行：k，即给定被填补迷宫的大小为2^k ×2^k （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）编程思路。

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

 

              图1   4个小迷宫

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

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

 

          图2 公主在左上角迷宫中

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

 

           图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）以长度为n³的一串破折号构成的虚线开始

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

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

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

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

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

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

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

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

再来一遍：

- -  - -     - -  - -

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

输入

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

输出

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

输入样例

0

1

3

输出样例

-

- -

- -   - -         - -   - -

         （1）编程思路。

         设S(n)表示长度为n³的近似康托集，显然可以发现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）：方格填数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！