题目
编程实现把1~9九个数字填入九宫格中，满足每行、每列和对角线上的三个数字和为15。如图所示。
Paste_Image.png
解题思路
“魔方阵“问题
魔方阵，古代又称“纵横图”，是指组成元素为自然数1、2…n2
的平方的n×n的方阵，其中每个元素值都不相等，且每行、每列以及主、副对角线上各n个元素之和都相等。
两种解题思路
-
方法1.利用魔方阵的数学规律解题
这个方法属于利用了前人总结的经验，写程序会很简单。这也是课本例题。 -
方法2.穷举赋值
把9个数字不重复的放到九个位置之中。再检查结果是否符合横竖斜的和都是15的要求。
可以利用递归实现赋值。如下图所示，给第一个位置赋值19，再给第二个位置赋值19，在给第三个位置赋值前先检查前面位置赋值是否有重复的，有的话这个递归的赋值就可以结束了……一直递归赋值到第九个位置
树图.png
源码1
利用魔方阵的数学规律，修改RANK值可输出任意奇数阶的魔方阵
#include <stdio.h>
#include <time.h>
#define RANK 3
void main()
{
/*记时行,不用在意*/clock_t start, finish; start = clock();/*记时行*/
int i, j, temp1, temp2;
int num = 1;
int a[RANK][RANK];
for (i = 0; i < RANK; i++)
{
for (j = 0; j < RANK; j++)
{
a[i][j] = 0;
}
}
/*以上初始化矩阵*/
/*下面都是运用魔方阵数学规律的运算*/
i = 0;
j = RANK / 2;
a[i][j] = 1;
do
{
num += 1;
temp1 = i;
temp2 = j;
if (i == 0)
{
i = RANK - 1;
j = j + 1;
}
else if (j == RANK - 1)
{
i = i - 1;
j = 0;
}
else
{
i = i - 1;
j = j + 1;
}
if (a[i][j] == 0)
{
a[i][j] = num;
}
else
{
i = temp1 + 1;
j = temp2;
a[i][j] = num;
}
} while (num < RANK*RANK);
/*输出魔方阵*/
for (i = 0; i < RANK; ++i)
{
for (j = 0; j < RANK; ++j)
{
printf("%-3d", a[i][j]);
}
printf("\n");
}
/*记时*/finish = clock(); printf("共耗时%.3lf秒", ((double)finish - start) / 1000);/*记时*/
getchar();
}
执行结果1
数学建模法.PNG
源码2
递归穷举法
可输出所有合适的排列方式
修改RANK 和SUM值可输出任意阶魔方阵
#include <stdio.h>
#include <time.h>
#define SUM 15
#define RANK 3
#define MAX (RANK*RANK)
void fillNum(int num, int position);
int checkRepeatedFigures(int * p, int position);
int checkSum(int * p);
int g_arr[MAX];
void main()
{
/*记时用,不用在意*/clock_t start, finish; start = clock();/*记时用*/
int i;
for (i = 1; i <= MAX; i++)
{
fillNum(i, 0);
}
printf("查找完毕！\n");
/*记时*/finish = clock(); printf("共耗时%.3lf秒", ((double)finish - start) / 1000);/*记时*/
getchar();
}
void fillNum(int num, int position)
{
int i;
g_arr[position] = num;
position++;
if (position > MAX - 1)
{
if (checkRepeatedFigures(g_arr, position))//检查g_arr[9]有没有重复数字
{
if (checkSum(g_arr))//检查横竖斜和是否为15
{
printf("你得到了一个%d阶魔方阵\n", RANK);
for (i = 0; i < MAX; i++)
{
printf("%d ", g_arr[i]);
if ((i + 1) % RANK == 0)
{
printf("\n");
}
}
printf("\n");
}
}
}
else
{
if (checkRepeatedFigures(g_arr, position))
{
for (i = 1; i <= MAX; i++)
{
fillNum(i, position);
}
}
}
}
int checkRepeatedFigures(int * p, int position)//检查指针p指向数组arr的position位置前是否有重复值，有返回0.无返回1
{
int i, j;
for (i = 0; i < position; i++)
{
for (j = i + 1; j < position; j++)
{
if (*(p + i) == *(p + j))
{
return 0;
}
}
}
return 1;
}
int checkSum(int * p)//检查p指向数组横竖斜和是否为15 是返回1，否返回0
{
int arr[RANK][RANK];
int i, j;
int lineSum, columnSum;
int leanSumX = 0, leanSumY = 0;
//转化成二维数组
for (i = 0; i < RANK; i++)
{
for (j = 0; j < RANK; j++)
{
arr[i][j] = *(p++);
}
}
//检查横竖行和；
for (i = 0; i < RANK; i++)
{
lineSum = 0;
columnSum = 0;
for (j = 0; j < RANK; j++)
{
lineSum += arr[i][j];
columnSum += arr[j][i];
if (i == j)
{
leanSumX += arr[i][j];
}
if (i == RANK - j - 1)
{
leanSumY += arr[i][j];
}
}
if (lineSum != SUM || columnSum != SUM)
{
return 0;
}
}
//检查对角线和
if (leanSumX != SUM || leanSumY != SUM)
{
return 0;
}
return 1;
}
执行结果2
穷举法.PNG
总结
- 数学建模法
优点:
1.运算时间效率高，用时小于0.0001秒
2. 代码简单。
缺点:
1.只能运算出一种结果，不全面。
2.对于奇偶阶魔方阵，要区别对待写两段代码 - 递归穷举法
优点:
1.运算全面，可输出所有结果
2.可输出任意魔方阵
缺点:
1.运行时间效率低，对于3阶魔方阵就需0.774秒的时长
2.要提前查知指导N阶魔方阵的和SUM
网友评论