|
精华帖 (0) :: 良好帖 (0) :: 灌水帖 (1) :: 隐藏帖 (11)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2009-07-15
最后修改：2009-07-16
用 java 实现这么 一道 小学数学竞赛题：
用1-9 填充 3 * 3 格，使得 横、竖、斜 8条线上数字之和都相等。 java代码：
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;
/**
* 用 1 - 9 数字 填充 3 * 3 格，使得 横3、竖3、斜2 共8道，每道之和都相等；
*/
public class Test {
public static void main(String[] args) {
Long startT = System.currentTimeMillis();
Set<NineGrid> result = new LinkedHashSet<NineGrid>();
int i = 0;
for (int x9 = 1; x9 <= 9; x9++) {
for (int x8 = 1; x8 <= 9; x8++) {
if (x8 != x9) {
for (int x7 = 1; x7 <= 9; x7++) {
if (x7 != x9 && x7 != x8) {
for (int x6 = 1; x6 <= 9; x6++) {
if (x6 != x9 && x6 != x8 && x6 != x7) {
// 分析知 中间的数字 必须为 5
for (int x5 = 5; x5 <= 5; x5++) {
if (x5 != x9 && x5 != x8 && x5 != x7 && x5 != x6) {
for (int x4 = 1; x4 <= 9; x4++) {
if (x4 != x9 && x4 != x8 && x4 != x7 && x4 != x6 && x4 != x5) {
for (int x3 = 1; x3 <= 9; x3++) {
if (x3 != x9 && x3 != x8 && x3 != x7 && x3 != x6 && x3 != x5 && x3 != x4) {
for (int x2 = 1; x2 <= 9; x2++) {
if (x2 != x9 && x2 != x8 && x2 != x7 && x2 != x6 && x2 != x5 && x2 != x4 && x2 != x3) {
for (int x1 = 1; x1 <= 9; x1++) {
if (x1 != x9 && x1 != x8 && x1 != x7 && x1 != x6 && x1 != x5 && x1 != x4 && x1 != x3
&& x1 != x2) {
NineGrid gd = new NineGrid();
gd.value[8] = x9;
gd.value[7] = x8;
gd.value[6] = x7;
gd.value[5] = x6;
gd.value[4] = x5;
gd.value[3] = x4;
gd.value[2] = x3;
gd.value[1] = x2;
gd.value[0] = x1;
if (gd.isRight()) {
result.add(gd);
}
++i;
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
for (Iterator<NineGrid> it = result.iterator(); it.hasNext();) {
NineGrid _ng = (NineGrid) it.next();
_ng.printNg();
}
Long endT = System.currentTimeMillis();
System.out.println("Over, " + result.size() + " result, " + i + " try, " + (endT - startT) + " milliseconds.");
}
}
/**
* 3*3格 类
*/
class NineGrid {
int[] value = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
public void printNg() {
System.out.println();
for (int i = 8; i >= 0; i--) {
System.out.print(value[i] + "\t");
if (i % 3 == 0) {
System.out.println();
}
}
}
/** 判断 1 - 9 填充后是否满足条件 */
public boolean isRight() {
int sum = (value[0] + value[1] + value[2] + value[3] + value[4] + value[5] + value[6] + value[7] + value[8]) * 2
+ (value[8] + value[6] + value[2] + value[0]) + value[4] * 2;
if (sum % 8 != 0) {
return false;
}
int eq = sum / 8;
if ((value[8] + value[7] + value[6] == eq) && (value[5] + value[4] + value[3] == eq) && (value[2] + value[1] + value[0] == eq)
&& (value[8] + value[5] + value[2] == eq) && (value[7] + value[4] + value[1] == eq) && (value[6] + value[3] + value[0] == eq)
&& (value[8] + value[4] + value[0] == eq) && (value[6] + value[4] + value[2] == eq)) {
return true;
} else {
return false;
}
}
/**
* 用 hashCode 值来判断是否相等；
*/
public boolean equals(Object o) {
if (o == null || o.getClass() != this.getClass()) {
return false;
}
NineGrid ng = (NineGrid) o;
if (this.hashCode() == ng.hashCode()) {
return true;
} else {
return false;
}
}
/**
* 4个角的每种“组合”对应一个不同的 hashCode 值，
* 这里的“组合”是数学中“排列、组合”的“组合”；
*/
public int hashCode() {
int ez0, ez1, st0, st1;
if (value[8] > value[0]) {
ez0 = value[0];
ez1 = value[8];
} else {
ez0 = value[8];
ez1 = value[0];
}
if (value[6] > value[2]) {
st0 = value[2];
st1 = value[6];
} else {
st0 = value[6];
st1 = value[2];
}
int[] corners = { 0, 0, 0, 0 };
if (ez0 < st0) {
corners[0] = ez0;
corners[1] = st0;
corners[2] = st1;
corners[3] = ez1;
} else {
corners[0] = st0;
corners[1] = ez0;
corners[2] = ez1;
corners[3] = st1;
}
return (int) (corners[0] + corners[1] * 10 + corners[2] * 1e2 + corners[3] * 1e3);
}
}
看了各位的解答，发现我的算法不够精简，导致计算次数过多； 撇开算法和计算次数不改，看了 几位对 Arrays 和 Collections 类的使用，我重写了下 NineGrid.java 类； 重写后的 NineGrid.java:
class NineGrid {
int[] value = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
public void printNg() {
System.out.println();
for (int i = 8; i >= 0; i--) {
System.out.print(value[i] + "\t");
if (i % 3 == 0) {
System.out.println();
}
}
}
/** 判断 1 - 9 填充后是否满足条件 */
public boolean isRight() {
int sum = (value[1] + value[3] + value[5] + value[7]) * 2 + (value[8] + value[6] + value[2] + value[0]) * 3 + value[4] * 4;
if (sum % 8 != 0) {
return false;
}
int eq = sum / 8;
if ((value[8] + value[7] + value[6] == eq) && (value[5] + value[4] + value[3] == eq) && (value[2] + value[1] + value[0] == eq)
&& (value[8] + value[5] + value[2] == eq) && (value[7] + value[4] + value[1] == eq) && (value[6] + value[3] + value[0] == eq)
&& (value[8] + value[4] + value[0] == eq) && (value[6] + value[4] + value[2] == eq)) {
return true;
} else {
return false;
}
}
/**
* 用 hashCode 值来判断是否相等；
*/
public boolean equals(Object o) {
if (o == this) {
return true;
}
if (o == null || o.getClass() != this.getClass()) {
return false;
}
NineGrid ng = (NineGrid) o;
if (this.hashCode() == ng.hashCode()) {
return true;
} else {
return false;
}
}
/**
* 4个角的每种“组合”对应一个不同的 hashCode 值，
* 这里的“组合”是数学中“排列、组合”的“组合”；
*/
public int hashCode() {
List<Integer> li = Arrays.asList(value[0], value[2], value[6], value[8]);
Collections.sort(li);
return (int) (li.get(0) + li.get(1) * 10 + li.get(2) * 1e2 + li.get(3) * 1e3);
}
}
声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2009-07-15
最后修改：2009-07-15
笑死我了 …… 写程序的时间比人脑穷举长 ……
不过这个问题，古书上就有解法。 先斜着按顺序填下数字 1 4 2 7 5 3 8 6 9 上下交换，左右交换 9 4 2 3 5 7 8 6 1 然后把上下左右缩回去 492 357 816 对 4 x 4 同样成立 |
| 返回顶楼 | |
|
发表时间：2009-07-15
orz..
|
| 返回顶楼 | |
|
发表时间：2009-07-15
信曾哥，会做题
|
| 返回顶楼 | |
|
发表时间：2009-07-15
楼主的算法太复杂了， 应该尽量用集合，减少复杂度
|
| 返回顶楼 | |
|
发表时间：2009-07-15
night_stalker 写道 笑死我了 …… 写程序的时间比人脑穷举长 ……
不过这个问题，古书上就有解法。 先斜着按顺序填下数字 1 4 2 7 5 3 8 6 9 上下交换，左右交换 9 4 2 3 5 7 8 6 1 然后把上下左右缩回去 492 357 816 对 4 x 4 同样成立 4 X 4 最后一步怎么缩回去？ 对于 N X N 的格子，只要N为奇数，有一个非常简单的办法： step 1： 在第一排中间那个格子写上1 _ 1 _ _ _ _ _ _ _ step 2： 往右上依次写上234...，若是第一排则跳到最下一排，若是最右一列则跳到第一列 _ 1 _ 3 _ _ _ _ 2 若右上已经被填，则下移一排 _ 1 6 3 5 _ 4 _ 2 重复上一步 8 1 6 3 5 7 4 9 2 |
| 返回顶楼 | |
|
发表时间：2009-07-15
洛河图..
|
| 返回顶楼 | |
|
发表时间：2009-07-15
4 X 4 的解法：
1 2 3 4
翻转对角线，完成。
16 2 3 13
8 X 8 还有个国际象棋马遍历的解法 …… |
| 返回顶楼 | |
|
发表时间：2009-07-15
幸存者 的解法对所有的奇数成立。
偶数还没有通用解法 |
| 返回顶楼 | |
|
发表时间：2009-07-15
呃。。我还以为帖子的代码是故意写成这样来搞笑的。。。。
|
| 返回顶楼 | |
