题目
如图【1.png】所示六角形中,填入1~12的数字。
使得每条直线上的数字之和都相同。
图中,已经替你填好了3个数字,请你计算星号位置所代表的数字是多少?
请通过浏览器提交答案,不要填写多余的内容。
答案
10
分析
这道题最方便、最快捷、最能想到的必须是暴利求解,把六角星从上到下,从左到右分别编号1~12,然后利用DFS(深度遍历搜索)
递归,把所有的可能都试一遍,直到满足每条直线上和相等则可得到*
的解。
代码里面有两个数组a[]
和vis[]
。分别用来存放1~12个数和记录哪个数被使用过,已经使用过则记为 true
否则记为false
,所以初始的时候:
a[1] = 1;
vis[1] = true;
a[2] = 8;
vis[8] = true;
a[12] = 3;
vis[3] = true;
然后从x=1
开始运行dfs(int x)
函数,求解。
代码
public class Six {
static int N = 14;
static int[] a = new int[N];
static boolean[] vis = new boolean[N];
public static void main(String[] args) {
a[1] = 1;
vis[1] = true;
a[2] = 8;
vis[8] = true;
a[12] = 3;
vis[3] = true;
dfs(1);
}
// a是最长数组,k是子数组的first index
private static void dfs(int x){
if(x==1||x==2||x==12){
dfs(x+1);
return;
}
if(x>12){
int t[] = new int[6];
t[0] = a[1] + a[3] + a[6] + a[8];
t[1] = a[1] + a[4] + a[7] + a[11];
t[2] = a[2] + a[3] + a[4] + a[5];
t[3] = a[2] + a[6] + a[9] + a[12];
t[4] = a[8] + a[9] + a[10] + a[11];
t[5] = a[12] + a[10] + a[7] + a[5];
for(int i = 1; i< t.length; i++){
if (t[i]!=t[i-1]) return;
}
System.out.println("*="+a[6]);
return;
}
for(int i = 1; i<13; i++){
if(!vis[i]){
vis[i]=true;
a[x] = i;
dfs(x+1);
vis[i]=false;
}
}
}
}