`
spacefly
  • 浏览: 277894 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

小学数学竞赛题：1-9 填充 3 * 3 格

    博客分类：
  • java
算法LinqRuby 
阅读更多
用 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);
	}
}


分享到：
| 局域网抢带宽
评论
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
当然效率同样极其低下

嗯，不错不错，赞一个 ^ ^
lazy eval + inlining的效果使得出来的东西确实基本上是一样的
不过既然用上了static import，干脆连System.out.println也拉进来，下面看起来更清爽 =v=
13 楼 Eastsun 2009-07-16  
RednaxelaFX 写道
啊，楼主只是要穷举而已？穷举的话用Java真够麻烦的 OTL
咱们用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++) {
  ...
}
11 楼 RednaxelaFX 2009-07-16  
啊，楼主只是要穷举而已？穷举的话用Java真够麻烦的 OTL
咱们用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>
6 楼 gof95 2009-07-15  
洛河图..
5 楼 幸存者 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

4 楼 xyh 2009-07-15  
楼主的算法太复杂了， 应该尽量用集合，减少复杂度
3 楼 lw223 2009-07-15  
信曾哥，会做题
2 楼 Eastsun 2009-07-15  
orz..
1 楼 night_stalker 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 同样成立
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    word2010上机练习题库

    ### Word2010上机练习题库...以上练习题旨在通过实际操作帮助考生熟悉Word2010的基本功能和常用工具，提高对文档格式设置的能力。通过这些练习，不仅可以增强对Word软件的掌握程度，还能提升处理日常办公文档的效率。

    第十一届蓝桥杯青少组EV3竞赛规则及样题.pdf.pdf

    根据提供的文件信息，我们可以总结出以下相关知识点： ### 第十一届蓝桥杯青少组EV3竞赛概述 ...以上是关于第十一届蓝桥杯青少组EV3竞赛规则及样题的主要知识点汇总。希望对准备参加此类竞赛的学生有所帮助。

    小学二年级下学期数学期中考试题.docx

    3. **符号填充**： - **解析示例**：例如“42-6=36”，考察学生对于加减乘除符号的选择能力。 4. **最大填数**： - **解析示例**：通过计算确定填入的最大数，如“()×4”中最大填7。 5. **列式计算**： - **...

    2009年全国研究生数学建模竞赛优秀论文选-D-国防科学技术大学-熊晓雯、张斌、李厚森.pdf

    ### 2009年全国研究生数学建模竞赛优秀论文选-D-国防科学技术大学-熊晓雯、张斌、李厚森 #### 知识点概述 本文档是一篇关于2009年全国研究生数学建模竞赛的获奖论文摘要，主要探讨了社会安全系统中警车的优化配置...

    经典SQL语句大全

    **3. 备份SQL Server** - **创建备份设备**: - **语法**: ```sql USE master; EXEC sp_addumpdevice 'disk', 'testBack', 'c:\mssql7backup\MyNwind_1.dat'; ``` - **说明**: 上述代码用于创建一个备份设备...

    2014--2015小学一年级数学综合练习题(动脑筋).doc

    根据给定的小学一年级数学综合练习题文档，我们可以总结出以下关键知识点： ### 几何图形识别 1. **理解图形关系**： - **题目示例**：“在○里，但不在里，也不在△里，是（ ）。” - **解析**：此题考察的是...

    人教版六年级数学下册小学六年级毕业数学总复习PPT课件[1]2.ppt

    《人教版六年级数学下册》的复习课件涵盖了多个关键知识点，旨在帮助学生全面回顾和巩固小学阶段的数学知识。以下是对这些知识点的详细解释： 1. **数的认识**： - **自然数**：包括0和所有正整数，如1, 2, 3等，...

    数学建模历年真题

    #### 一、美国大学生数学建模竞赛(MCM) **1985年A题 动物群体管理** - **背景**: 对动物种群进行有效管理，确保生态平衡。 - **核心知识点**: - 种群增长模型：如Logistic模型等。 - 动态规划方法用于决定捕猎或...

    一年级数学上册期末测试题(可直接A4打印).pdf

    这份资料是一年级数学上册的期末测试题，涵盖了基础的数学概念和运算，包括数的认识、比较、加减法以及简单的规律推理。以下是对各部分知识点的详细解释： 1. **填空题**： - **数的认识**：题目要求识别和理解数...

    全国大学生英语竞赛题型

    全国大学生英语竞赛作为一项旨在提升大学生英语综合应用能力的重要赛事，其题型设计与评分标准直接关系到参赛者的准备方向和策略。根据给定的信息，我们可以深入解析竞赛的各个部分，以便更好地理解其考核重点。 ##...

    Html+Css+Javascript从入门到精通.pdf

    - **边距、边框与填充**：调整元素边缘的空白。 **第十四章：颜色与背景** - **颜色设置**：为元素设置前景色和背景色。 - **背景图片**：使用图片作为背景。 **第十五章：元素定位** - **绝对定位与相对定位**...

    Asp.net参考知识点即总结重点（笔记）

    - **Fill()**: 将数据填充到 DataSet 中。 以上内容总结了 ADO.NET 的基本概念及其主要组成部分，了解这些基础知识有助于开发者更好地利用 ADO.NET 来开发数据驱动的应用程序。接下来，可以进一步探索如何在实际...

    人教版小学一年级数学上学期期末-测试卷及答案.doc

    ### 人教版小学一年级数学知识点解析 #### 一、填空题解析 **1. 数字的认识与读法** - 题目要求学生识别并读出四个数字：12、21、42、0。 - **知识点**： - **数字的识别**：学生需要能够准确识别数字。 - **...

    一些mfc的练习题

    ### MFC练习题知识点解析 #### 题目0：绘制曲线 **知识点解析：** 1. **MFC窗口管理与最大化：** - **窗口类：** 在MFC中，可以通过`CWnd`类及其派生类来创建窗口。 - **窗口最大化：** 可以使用`CWnd::...

    PCIE SPEC 4.0 规格书

    - 引入了多项协议增强功能，如**优化的缓冲器刷新/填充**(Optimized Buffer Flush/Fill)、**ASPM选项性**(ASPM Optionality)等，提高了系统性能并减少了延迟。 ##### **5. 新特性** - **第9章“电气子模块”**的...

    数学建模-全国大学生数学建模竞赛论文写作模版.zip

    全国大学生数学建模竞赛是一项旨在提高大学生综合素质，培养创新思维和团队合作能力的学科竞赛。在准备这样的竞赛时，一篇高质量的论文至关重要。这个压缩包“数学建模-全国大学生数学建模竞赛论文写作模版.zip”...

    幼儿园大班数学期末考试题.docx

    ### 幼儿园大班数学期末考试题知识点解析 #### 一、比较大小关系 - **题目要求**：本部分要求学生在圆圈内填写适当的符号（&lt;、&gt; 或 =），来表示两个数字之间的大小关系。 - **示例**： - \(6+4\) 和 8 的比较 - ...

    小学数学概念及公式大全含举例.docx

    小学数学是基础教育的重要组成部分，它涵盖了众多的概念和公式，为孩子们日后的数学学习打下坚实的基础。以下是一些核心的数学概念和公式，以及如何读写和比较这些数。 1. **数的读法和写法**： - **整数**：读数...

Magicbox
Global site tag (gtag.js) - Google Analytics