六角填数（蓝桥杯）

六角填数

如图【1.png】所示六角形中，填入1~12的数字。

使得每条直线上的数字之和都相同。

图中，已经替你填好了3个数字，请你计算星号（*）位置所代表的数字是多少？

解析：这个题只是让你提交一个整数，并不是让你提交代码，所以不用担心运行超不超时的问题，本题要求填入1-12数字，这个题还隐藏着一个条件：1-12分别且只能出现一次，分别且只出现一次是不是从哪一类题上见过，那就是全排列类型题，所以该题可以用全排列方法来解决这个题。

 具体解法：先创建一个int类型的数组(c[12])，先把上述六角形的各个位置标上下标，如上图所示，然后向数组中放值，数组中存放1-12，12个数，因为六角形中给出了三个数，所以我把下标0赋值为8、下标3赋值为3、下标4赋值为1，即c[0] = 8、c[3] = 3、c[4] = 1，具体初始赋值为int[] c = {8,2,4,3,1,5,6,7,9,10,11,12}（这样得到的都是先以8为开头的全排列），六角形一共有6条边，先判断数组的下标（0，3，4）对应的值是否对应已给的三个值，然后再判断这6条边是否相等，如果这6条边都相等，则下标为1的值即c[1]就是我们所求的值。

int A = c[0]+c[1]+c[2]+c[3];

int B = c[4]+c[5]+c[1]+c[6];

int C = c[0]+c[5]+c[7]+c[8];

int D = c[4]+c[7]+c[9]+c[11];

int E = c[8]+c[9]+c[10]+c[3];

int F = c[6]+c[2]+c[10]+c[11];

答案：10

代码如下：（耗时200ms左右）

public class 六角填数
{private static long Begin = 0;       //与本题无关，只是计算一下程序总共耗时多长时间private static long End = 0;		 //与本题无关，只是计算一下程序总共耗时多长时间public static void Swap(int[] c,int i,int j){int tmp = c[i];c[i] = c[j];c[j] = tmp;}public static void AllPermutation(int[] c,int start){if(start==c.length-1)        //说明已找到一个排列{if(c[0]==8&&c[3]==3&&c[4]==1)     //判断六角形的下标（0，3，4）对应的值是否符合已给的三个值{int A = c[0]+c[1]+c[2]+c[3];   //第一条边的和int B = c[4]+c[5]+c[1]+c[6];   //第二条边的和int C = c[0]+c[5]+c[7]+c[8];   //第三条边的和int D = c[4]+c[7]+c[9]+c[11];  //第四条边的和 int E = c[8]+c[9]+c[10]+c[3];  //第五条边的和int F = c[6]+c[2]+c[10]+c[11]; //第六条边的和if(A==B&&B==C&&C==D&&D==E&&E==F){for(int i=0,t=c.length;i<t;++i)  //把所有下标的值都输出{if(i!=0){System.out.print(" ");}System.out.print(c[i]);}System.out.println("\nc[1]："+c[1]);   //所求*值End = System.currentTimeMillis() - Begin;   //与本题无关，只是计算一下程序总共耗时多长时间System.out.println("耗时："+End+"ms");   //总共耗时System.exit(0);						//退出java虚拟机}}}else{for(int i=start,t=c.length;i<t;++i){Swap(c,i,start);AllPermutation(c,start+1);Swap(c,start,i);}}}public static void main(String[] args){int[] c = {8,2,4,3,1,5,6,7,9,10,11,12};   //根据六角形的下标位置赋值Begin = System.currentTimeMillis();    //与本题无关，只是计算一下程序总共耗时多长时间AllPermutation(c,0);      //全排列算法}

运行结果：8 10 5 3 1 9 6 2 7 12 4 11
c[1]：10
耗时：198ms