spacefly
- 浏览: 279439 次
- 性别:
- 来自: 北京
-
文章分类
最新评论
-
plg17：
properties文件中文自动转码问题确实给开发带来不便，按 ...
eclipse .properties插件 -
sorriest-siben：
帅哥，你的例子是不是笔误了呀应该是这样的吧<result ...
struts2 redirect 传参数 -
Masket874：
沙发。。。。。
session的监听器 -
spp_1987：
<%@page import="jav ...
jsp输出静态的图片 -
spp_1987：
如何 限制输出图片大小。 还有我的后台报错 出来一个异常：
严 ...
jsp输出静态的图片
用 java 实现这么 一道 小学数学竞赛题：
用1-9 填充 3 * 3 格，使得 横、竖、斜 8条线上数字之和都相等。
java代码：
看了各位的解答，发现我的算法不够精简，导致计算次数过多；
撇开算法和计算次数不改，看了 几位对 Arrays 和 Collections 类的使用，我重写了下 NineGrid.java 类；
重写后的 NineGrid.java:
嗯，不错不错，赞一个 ^ ^
lazy eval + inlining的效果使得出来的东西确实基本上是一样的
不过既然用上了static import，干脆连System.out.println也拉进来，下面看起来更清爽 =v=
只能说楼主用java写的很麻烦。。
把你的用java翻译一下，也不用什么Linq
当然效率同样极其低下：
4 X 4 最后一步怎么缩回去？
对于 N X N 的格子，只要N为奇数，有一个非常简单的办法：
step 1：
在第一排中间那个格子写上1
step 2：
往右上依次写上234...，若是第一排则跳到最下一排，若是最右一列则跳到第一列
若右上已经被填，则下移一排
重复上一步
用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);
}
}
分享到：
评论
16 楼
Eastsun
2009-07-16
速度一点的：
import java.util.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
public class A {
public static void main(String[] args) {
List<Integer> nums = asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
for(int x1: nums) for(int x2: nums)
for(int x4: nums) for(int x5: nums)
{
int x3 = 15 - x1 - x2;
int x6 = 15 - x4 - x5;
int x7 = 15 - x1 - x4;
int x8 = 15 - x2 - x5;
int x9 = 15 - x3 - x6;
List<Integer> nls = new ArrayList<Integer>(asList(x1,x2,x3,x4,x5,x6,x7,x8,x9));
sort(nls);
if(!nls.equals(nums)) continue;
if(x1 + x5 + x9 != 15) continue;
if(x3 + x5 + x7 != 15) continue;
System.out.println();
System.out.println(asList(x1,x2,x3));
System.out.println(asList(x4,x5,x6));
System.out.println(asList(x7,x8,x9));
}
}
}
15 楼
night_stalker
2009-07-16
动态规划 …… 3 x 3 比较小，体现不出递归的简洁性，就用比较详细的写法吧 ……
s = 15
a = 1..9
(a1 = a.to_a ).each{|x1|
(a2 = a1-[x1]).each{|x2|
(a3 = a2-[x2]).each{|x3|
next if (x1+x2+x3 != s)
(a4 = a3-[x3]).each{|x4|
(a5 = a4-[x4]).each{|x5|
(a6 = a5-[x5]).each{|x6|
next if (x4+x5+x6 != s)
(a7 = a6-[x6]).each{|x7|
next if (x1+x4+x7 != s)
next if (x3+x5+x7 != s)
(a8 = a7-[x7]).each{|x9|
next if (x3+x6+x9 != s)
next if (x1+x5+x9 != s)
x8 = (a8-[x9])[0]
p [x1,x2,x3],[x4,x5,x6],[x7,x8,x9]
puts
}} }}} }}}
14 楼
RednaxelaFX
2009-07-16
Eastsun 写道
只能说楼主用java写的很麻烦。。
把你的用java翻译一下，也不用什么Linq
当然效率同样极其低下
把你的用java翻译一下，也不用什么Linq
当然效率同样极其低下
嗯，不错不错，赞一个 ^ ^
lazy eval + inlining的效果使得出来的东西确实基本上是一样的
不过既然用上了static import，干脆连System.out.println也拉进来，下面看起来更清爽 =v=
13 楼
Eastsun
2009-07-16
RednaxelaFX 写道
啊，楼主只是要穷举而已？穷举的话用Java真够麻烦的 OTL
咱们用C#做效率更低的穷举来看看：
easy things easy, hard things possible
咱们用C#做效率更低的穷举来看看：
using System;
using System.Linq;
static class Program {
static void Main(string[] args) {
var candidateNumbers = new [] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
var results = from x1 in candidateNumbers
from x2 in candidateNumbers
from x3 in candidateNumbers
from x4 in candidateNumbers
from x5 in candidateNumbers
from x6 in candidateNumbers
from x7 in candidateNumbers
from x8 in candidateNumbers
from x9 in candidateNumbers
let r = new [] { x1, x2, x3, x4, x5, x6, x7, x8, x9 }
where r.Distinct().Count() == 9
let r1 = x1 + x2 + x3
let r2 = x4 + x5 + x6
let r3 = x7 + x8 + x9
let r4 = x1 + x4 + x7
let r5 = x2 + x5 + x8
let r6 = x3 + x6 + x9
let r7 = x1 + x5 + x9
let r8 = x3 + x5 + x7
where (new [] { r1, r2, r3, r4, r5, r6, r7, r8 }).Distinct().Count() == 1
select r;
foreach (var r in results) {
Console.WriteLine("{0} {1} {2}", r[0], r[1], r[2]);
Console.WriteLine("{0} {1} {2}", r[3], r[4], r[5]);
Console.WriteLine("{0} {1} {2}", r[6], r[7], r[8]);
Console.WriteLine();
}
}
}
easy things easy, hard things possible
只能说楼主用java写的很麻烦。。
把你的用java翻译一下，也不用什么Linq
当然效率同样极其低下：
import java.util.*;
import static java.util.Arrays.*;
public class S {
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
for(int x1: nums) for(int x2: nums) for(int x3: nums)
for(int x4: nums) for(int x5: nums) for(int x6: nums)
for(int x7: nums) for(int x8: nums) for(int x9: nums)
{
if(new HashSet(asList(x1,x2,x3,x4,x5,x6,x7,x8,x9)).size() < 9) continue;
int r1 = x1 + x2 + x3;
int r2 = x4 + x5 + x6;
int r3 = x7 + x8 + x9;
int r4 = x1 + x4 + x7;
int r5 = x2 + x5 + x8;
int r6 = x3 + x6 + x9;
int r7 = x1 + x5 + x9;
int r8 = x3 + x5 + x7;
if(new HashSet(asList(r1,r2,r3,r4,r5,r6,r7,r8)).size() > 1) continue;
System.out.println();
System.out.println(asList(x1,x2,x3));
System.out.println(asList(x4,x5,x6));
System.out.println(asList(x7,x8,x9));
}
}
}
12 楼
night_stalker
2009-07-16
穷举嘛 ……
for(int i=123456789;i<1000000000;i++) {
...
}
for(int i=123456789;i<1000000000;i++) {
...
}
11 楼
RednaxelaFX
2009-07-16
啊，楼主只是要穷举而已？穷举的话用Java真够麻烦的 OTL
咱们用C#做效率更低的穷举来看看：
easy things easy, hard things possible
咱们用C#做效率更低的穷举来看看：
using System;
using System.Linq;
static class Program {
static void Main(string[] args) {
var candidateNumbers = new [] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
var results = from x1 in candidateNumbers
from x2 in candidateNumbers
from x3 in candidateNumbers
from x4 in candidateNumbers
from x5 in candidateNumbers
from x6 in candidateNumbers
from x7 in candidateNumbers
from x8 in candidateNumbers
from x9 in candidateNumbers
let r = new [] { x1, x2, x3, x4, x5, x6, x7, x8, x9 }
where r.Distinct().Count() == 9
let r1 = x1 + x2 + x3
let r2 = x4 + x5 + x6
let r3 = x7 + x8 + x9
let r4 = x1 + x4 + x7
let r5 = x2 + x5 + x8
let r6 = x3 + x6 + x9
let r7 = x1 + x5 + x9
let r8 = x3 + x5 + x7
where (new [] { r1, r2, r3, r4, r5, r6, r7, r8 }).Distinct().Count() == 1
select r;
foreach (var r in results) {
Console.WriteLine("{0} {1} {2}", r[0], r[1], r[2]);
Console.WriteLine("{0} {1} {2}", r[3], r[4], r[5]);
Console.WriteLine("{0} {1} {2}", r[6], r[7], r[8]);
Console.WriteLine();
}
}
}
easy things easy, hard things possible
10 楼
logicgate
2009-07-15
这个有固定算法的。任意n*n（n为奇数）的我都会写。
9 楼
playfish
2009-07-15
呃。。我还以为帖子的代码是故意写成这样来搞笑的。。。。
8 楼
kimmking
2009-07-15
幸存者 的解法对所有的奇数成立。
偶数还没有通用解法
偶数还没有通用解法
7 楼
night_stalker
2009-07-15
<p>4 X 4 的解法：</p>
<p> </p>
<p><span style="font-family: courier new,courier;"><span style="color: #0000ff;">1</span> 2 3 <span style="color: #ff6600;">4</span><br>5 <span style="color: #0000ff;">6</span> <span style="color: #ff6600;">7</span> 8<br>9 <span style="color: #ff6600;">10</span> <span style="color: #0000ff;">11</span> 12<br><span style="color: #ff6600;">13</span> 14 15 <span style="color: #0000ff;">16</span><br></span></p>
<p> </p>
<p>翻转对角线，完成。</p>
<p> </p>
<p><span style="font-family: courier new,courier;"><span style="color: #0000ff;">16</span> 2 3 <span style="color: #ff6600;">13</span><br>
5 <span style="color: #0000ff;">11</span> <span style="color: #ff6600;">10</span> 8<br>
9 <span style="color: #ff6600;">7</span> <span style="color: #0000ff;">6</span> 12<br><span style="color: #ff6600;">4</span> 14 15 <span style="color: #0000ff;">1</span><br></span></p>
<p> </p>
<p> </p>
<p>8 X 8 还有个国际象棋马遍历的解法 ……</p>
<p> </p>
<p><span style="font-family: courier new,courier;"><span style="color: #0000ff;">1</span> 2 3 <span style="color: #ff6600;">4</span><br>5 <span style="color: #0000ff;">6</span> <span style="color: #ff6600;">7</span> 8<br>9 <span style="color: #ff6600;">10</span> <span style="color: #0000ff;">11</span> 12<br><span style="color: #ff6600;">13</span> 14 15 <span style="color: #0000ff;">16</span><br></span></p>
<p> </p>
<p>翻转对角线，完成。</p>
<p> </p>
<p><span style="font-family: courier new,courier;"><span style="color: #0000ff;">16</span> 2 3 <span style="color: #ff6600;">13</span><br>
5 <span style="color: #0000ff;">11</span> <span style="color: #ff6600;">10</span> 8<br>
9 <span style="color: #ff6600;">7</span> <span style="color: #0000ff;">6</span> 12<br><span style="color: #ff6600;">4</span> 14 15 <span style="color: #0000ff;">1</span><br></span></p>
<p> </p>
<p> </p>
<p>8 X 8 还有个国际象棋马遍历的解法 ……</p>
6 楼
gof95
2009-07-15
洛河图..
5 楼
幸存者
2009-07-15
night_stalker 写道
笑死我了 …… 写程序的时间比人脑穷举长 ……
不过这个问题，古书上就有解法。
先斜着按顺序填下数字
上下交换，左右交换
然后把上下左右缩回去
对 4 x 4 同样成立
不过这个问题，古书上就有解法。
先斜着按顺序填下数字
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
4 楼
xyh
2009-07-15
楼主的算法太复杂了， 应该尽量用集合，减少复杂度
3 楼
lw223
2009-07-15
信曾哥，会做题
2 楼
Eastsun
2009-07-15
orz..
1 楼
night_stalker
2009-07-15
笑死我了 …… 写程序的时间比人脑穷举长 ……
不过这个问题，古书上就有解法。
先斜着按顺序填下数字
上下交换，左右交换
然后把上下左右缩回去
对 4 x 4 同样成立
不过这个问题，古书上就有解法。
先斜着按顺序填下数字
1 4 2 7 5 3 8 6 9
上下交换，左右交换
9 4 2 3 5 7 8 6 1
然后把上下左右缩回去
492 357 816
对 4 x 4 同样成立
发表评论
-
事务 transaction
2009-04-21 15:32 1162事务 即 transaction 是个什么概念，又为什么有事务 ... -
struts2 redirect 传参数
2009-04-14 12:40 3809struts2 redirect 时如果想传参数示例如下，注意 ... -
eclipse .properties插件
2008-12-30 10:32 26535资源文件 即 .properties ... -
hql oracle 比较 日期时间
2008-12-25 10:58 13946oracle 里比较date类型时 ... -
单例模式-简单示范
2008-11-01 16:56 1345======所谓单例模式====== 即项目中某个类，只生成1 ... -
一道有关 变量、对象 作用域的java面试题
2008-11-01 16:50 1332这道java面试题，主要考了以下2点: * 变量、对象 作 ... -
struts2.0.11.2 的 validator 功能的 1个bug
2008-10-08 16:38 3410今天又用了一下struts2的validator功能，也就是校 ... -
log4j 配置详解
2008-10-06 19:22 4135转载 自 http://zhang-hong-cai-sina ... -
security 获得登陆用户
2008-10-06 19:00 2509如何在 security 中 获得 user 信息？由 sec ... -
java 反编译
2008-09-30 00:08 1504有时候需要将现有的 java 类，即 .class 文件编译成 ... -
acegi 的 session 控制 和 自定义的 remember-me 功能 冲突解决
2008-09-22 11:29 1787将 org.acegisecurity.context.Htt ... -
jsp输出静态的图片
2008-09-19 16:14 66302个方式，jsp中直接输出静态图片： img.jsp &l ... -
jstl core
2008-09-16 12:24 1708jstl core 的标签使用 jstl-core.jsp ... -
jstl fmt
2008-09-12 15:44 382861）导入jstl 包，加载ftm标签 首先将jstl的jar包 ... -
session 过期时间设置
2008-09-10 18:08 8101原文地址：http://hailan1987.blog ... -
session的监听器
2008-09-10 17:35 2789javax.servlet.http.HttpSession ... -
eclipse 快捷键
2008-09-03 15:00 62321）设置eclipse的快捷键 打开eclipse，Windo ... -
ant 风格的 url 匹配
2008-08-21 14:33 4334转载自：http://hi.baidu.com/xiaolan ... -
DBCP使用
2008-08-12 16:09 17928dbcp使用--------------------dbcp提 ... -
tomcat dbcp jndi 配置
2008-08-11 16:33 5152使用tomcat6，mysql6 1）添加jar包tomcat ...
相关推荐
这些题目来自于第四届“蓝桥杯”全国软件专业人才设计与创业大赛的C/C++高职高专组竞赛，涵盖了一系列的编程与数学问题。以下是各题目的解析： 1. **猜年龄**：根据题目描述，美国数学家维纳年龄的立方是4位数，4...
这篇文档是关于第九届小学《祖冲之杯》数学邀请赛的试题，涵盖了多个数学知识点，包括基础算术、代数、几何、比例和逻辑推理等。以下是这些题目所涉及的具体知识点： 1. **比例与等式关系**：第1题考察了小数点移动...
小学数学奥林匹克竞赛是培养小学生数学兴趣与能力的重要平台，而其中的图形与数列问题更是锻炼学生逻辑思维与空间想象的利器。本文将详细介绍小学二年级奥数图形题中的各类问题，并提供相应的答案与解析，以帮助学生...
在2021年诸暨市浣纱小学四年级集训队的考试中，试题主要集中在信息技术奥林匹克（简称信奥）的相关知识上，这是一场针对编程和算法基础的测验。信奥是针对青少年开展的一项科技竞赛活动，旨在培养学生的逻辑思维、...
九宫格问题要求学生将数字1到9填入空格中，使得每行、每列及对角线上的数字和相等，这不仅考验了学生的计算能力，更锻炼了他们解决问题的策略。 序列位置题是对学生理解序列中位置关系的能力的测试。通过题目中提供...
《小学数学奥数解题技巧大全100讲》是一份专注于提升小学生数学能力的教育资源，特别是对于数学奥林匹克竞赛的准备。这份文档的核心是通过观察法来培养学生的解题技能，观察法是解决数学问题的基础，它强调在解题...
1. **龟兔赛跑** (15 分) 这个编程题目是基于经典的寓言故事"龟兔赛跑"。问题的核心是找出在兔子先睡t分钟后，乌龟能够比兔子先到达终点或者同时到达的最远距离。题目要求编写一个名为`t1.cpp`的C++程序，该程序应...