62.由8个整数形成奇特的立方体
任意给出8个整数，将这8个整数分别放在一个立方体的八个顶点上，要求每个面上的四个数之和相等。
*问题分析与算法设计
简化问题：将8个顶点对应数组中的8个元素，将“每个面上的四个数之和皆相等”转换为数组无素之间和的相等关系。这里的关键在于正确地将立方体的8个顶点与数组的8个元素对应。
可以利用简单的穷举方法建立8个数的全部排列。
*程序与程序注释
#include<stdio.h>
#include<stdlib.h>
void main()
{
int a[9],ii=0,i,a1,a2,a3,a4,b1,b2,b3,b4,flag;
for(i=1;i<=8;i++) /*输入个数*/
{
printf("Please enter [%d]number:",i);
scanf("%d",&a[i]);
ii+=a[i];
}
printf("******************************************\n");
if(ii%2) /*和为奇数则输入的8个数不可用*/
{
printf("Sorry they can't be constructed required cube!\n");
exit(0);
}
for(flag=0,a1=1;a1<=8;a1++) /*flag:完成标记.flag=1;表示完成*/
for(a2=1;a2<=8;a2++) /*采用八重循环建立八个整数的全排列*/
if(a2!=a1) /*前两个数不能相同*/
for(a3=1;a3<=8;a3++)
if(a3!=a2&&a3!=a1) /*前三个数不能相同*/
for(a4=1;a4<=8;a4++)
if(a4!=a3&&a4!=a2&&a4!=a1) /*前四个数不能相同*/
for(b1=1;b1<=8;b1++)
if(b1!=a4&&b1!=a3&&b1!=a2&&b1!=a1) /*不能相同*/
for(b2=1;b2<=8;b2++)
if(b2!=b1&&b2!=a4&&b2!=a3&&b2!=a2&&b2!=a1)
for(b3=1;b3<=8;b3++)
if(b3!=b2&&b3!=b1&&b3!=a4&&b3!=a3&&b3!=a2&&b3!=a1)
/*不能取相同的数*/
for(b4=1;b4<=8;b4++)
if(b4!=b2&&b4!=b1&&b4!=b3&&b4!=a4&&b4!=a3&&b4!=a2&&b4!=a1)
if(a[b1]+a[b2]+a[b3]+a[b4]==ii/2
&&a[a1]+a[a2]+a[b1]+a[b2]==ii/2
&&a[a1]+a[a4]+a[b1]+a[b4]==ii/2)
{
flag=1;goto out; /*满足条件则将flag置1后退出*/
}
out:
if(flag)
{
printf("They can be constructed required cube as follow:\n");
printf(" /%2d............/%2d\n",a[a4],a[a3]);
printf(" %2d/............%2d/|\n",a[a1],a[a2]);
printf(" | | | |\n");
printf(" | | | |\n");
printf(" | %2d| | |%2d\n",a[b4],a[b3]);
printf(" /................/\n");
printf(" %2d/.............%2d/\n",a[b1],a[b2]);
}
else printf("Sorry they can't be constructed required cube!\n");
}
*运行结果
Please enter [1] number:20
Please enter [2] number:45
Please enter [3] number:39
Please enter [4] number:25
Please enter [5] number:29
Please enter [6] number:7
Please enter [7] number:3
Please enter [8] number:2
Sorry they can't be constructed required cube!

思考题
程序中建立全排列的方法效率太低，算法虽然简单但程序过于冗余。请读者自行设计新的算法完成同样的工作。

评论