数学建模社区-数学中国
标题: [灌水]喜欢迎接挑战的请进来！ [打印本页]
作者: god 时间: 2005-3-30 23:40
标题: [灌水]喜欢迎接挑战的请进来！
喜欢迎接挑战的请进来！ . Y2 C% X( x) ^% d4 N
《小擂台》 # n8 e) j6 Z- D8 C1 F) E
这是一个若干年前的一个数学问题，当然是已经解决了的问题，之所 " z! |0 o/ k7 W1 S# {9 p" F0 N# v# I
以贴出这个题目，是因为正当“非典”肆虐，许多网友有时间思考，对于
, u3 X. P- `/ n" P# X我们来说，这是一个机会，何不适时迎接一个小小的挑战，丰富我们的业 " y, C7 ~% ]# o$ F; M, I
余生活，何况这个题目在今天研究，已经具有双重的考验作用了。
4 S Y5 j _ ^8 C8 O; ? 不要去找现成的答案。也不是那么好找。
. ^" b% z1 H0 j; g; }" U; B' y- y 一是完全用我们的大脑来解决问题，这个难度是有相当档次的。 * V8 G( P8 Q: K
二是我们部分网友已经掌握的高超的电脑软件设计能力，可以设计出
; B' ? p0 q' j( p4 `3 I, M一个解决问题的搜索程序，解决这个问题。
7 p d7 D9 B; I8 D 6 g# O7 T X8 c8 T" g& ~/ N
1、题目的来历：在欧洲，自600年前，就时髦着一种智力游戏——重 * K# Z5 ~! d0 I
排九宫。这种游戏类似于我们中国古代的“华容道”游戏，规则如下：
; A$ P! _! p- z在一个九宫图中（也就是横竖三行三列方格的方格图），从左上角第一格
* N B$ J6 T/ M9 |开始，依次填上1、2、3、4、5、6、7、8八个数字，第九格空，然后在空
- F# [# k! t0 b1 P3 V格处移动与空格相邻的一个数字，再移动新产生的空格相邻的数字中的任
* T5 u+ r, K2 C& b9 @意一个数字，任何数字必须遵循这个规则移动。最后达到数字排列成8、7、
# S6 H2 l1 h6 b; I- {6、5、4、3、2、1的顺序，就是重排九宫完成了。设每一个数字移动一格 / s5 [4 L) Y. k) j, `% \: r) K
为一次或一步，那么用的步数越少就越好。在欧洲古代，往往能够在40步 3 ?' t* v) O& E/ E1 ]
以内完成就是智商很高的体现了。
I& `% [: J" C 2、寻找最优解。重排九宫的最优解实际上就是最少步数重排了九宫。 " n `, A% c6 _* F, a
但是在这个游戏欧洲时髦了5、6百年实际上连一个最优解也没有发现。
9 k* l) R; k) t7 g' N, {0 S. U 事实上，20多年前美国计算机科学家就是依靠那时的最先进数学手段
: }- {0 G y2 n, Q4 P# E——电脑（大概是晶体管的）在设计了一个搜索程序以后，耗费了几个小 ! }4 a$ p7 N/ j& X
时的计算机运算时间，才找到了全部的最优解。 - \# D1 I# o$ j$ \4 T0 I* p
他们宣布，这十个只用30步就可完成的最优解，用人的大脑是不可能 : o: D% w' a' A0 h% r* M L0 w' U# [
完成的。 , K) |- U: E6 ~ w' L0 x9 Z4 G
事实上，在20多年前当这个题目在国内公布之后，在短短的半年内， 1 {$ T' s( H6 }. E
就有51名各界的人士给出了全部最优解。当时可以说是一个扬眉吐气的事 $ p; o' i8 n2 i# b5 D6 v
件。体现了中国人的聪明才智。因为那时可以说我国的科技水平，尚不可
# C5 H# k' {! s# Y* K$ S1 M9 C能有那么多的人可以利用最先进的手段——电脑来帮助我们做此事。显然
* y! x+ M" D+ [1 v8 o- d是依靠中国人大脑的智慧回答了了这个美国数学家认为“依靠人的大脑不
1 \6 E: s' Q3 e1 K! O `可能找到这十个最优解”的结论。 ! n3 o8 d5 E7 y: d- ?1 I- i; O5 e
时代的变迁，科技水平是以爆炸式的方式发展，目前这样的问题解决
/ x, v5 }$ i" l z; \5 C) c! L的手段显然已经超过了当年美国数学家的时代。或许有一个软件设计天才 1 W( @' E3 a8 e
可以设计出一个搜索程序，不是利用几小时，而是几分钟或几十秒几秒就
. q( k4 X1 m/ A5 E4 n5 p找到这十个最优解，这都是可能的。
: h5 h0 R6 r: q 科技的威力在解决此题与战胜SARS这件事上异曲同工。 & R C2 J) b: @2 q: U- r
擂台已经摆下：请给出这十个最优解。 7 g( x' D8 ?$ g
补充:这是以前曾经出过的一个趣题,在现有的数学工具和编程技术条件下,本论坛必有高手很块就会给出答案,这是第一问.
$ K% \ B- I1 O2 ?8 P : G- J+ j5 S" L8 Y' r9 R
加一下难度给个第二问:6 M2 X3 \' }: b( {" q1 O
' h: u7 F% j0 r" Q" P* x 证明:重排九宫最少步数为30步,并且只有十个最优解
作者: god 时间: 2005-3-30 23:40
765 765 765 7 5 75 475 475 475 475 4 5 45 145 145 145 145 1 5 15 153 153 153 * P! Z2 h3 s5 N' F& O d
432 43 4 3 463 463 63 163 163 1 3 173 173 73 073 073 0 3 043 043 04 042 042 ( c6 Z$ G- u% z
10 102 102 102 102 102 02 0 2 062 062 062 062 62 6 2 672 672 672 672 67 6 7 L8 G% _* {2 i# j
+ z7 r- @2 @0 C/ \- \6 ^
153 1 3 13 132 132 1 2 12 012 012 012 012
7 |$ {# z- ~ K0 2 052 052 05 0 5 035 035 35 3 5 345 345
6 l) l e7 b( ?8 ]2 @647 647 647 647 647 647 647 647 647 6 7 67 % U! L+ ^3 B# `( Q5 F c
' \3 }/ R7 u' J( L6 f4 q3 e8 [
! R: b4 }8 k0 z) `" x
765 765 765 7 5 75 475 475 475 475 475 475 475 475 4 5 45 452 452 4 2 42 142
9 J( g. D# q' h9 a, u432 43 4 3 463 463 63 163 163 1 3 13 132 132 1 2 172 172 17 1 7 157 157 57 . j/ f, ^1 d' S% ^
10 102 102 102 102 102 02 0 2 062 062 06 0 6 036 036 036 036 036 036 036 036 , F, V; w" u8 {
' Y" c. s% |$ M+ U' o6 q
142 142 142 142 142 1 2 12 012 012 012 012 4 t7 Y; t! v: T3 p& y
057 057 057 05 0 5 045 045 45 345 345 345
2 B/ u) E3 c* Y7 H w* N E 36 3 6 36 367 367 367 367 367 67 6 7 67
9 ?. b7 G8 _0 U% i& n7 K
' f8 U0 W$ O0 f4 g4 Y# L0 r3 n3 ?6 c3 \! N. R- @
765 765 765 765 65 6 5 645 645 645 645 64 6 4 604 604 604 604 04 0 4 024 024 5 Z8 @# M. p+ e- K" X+ e
432 43 4 3 43 743 743 7 3 703 703 70 705 705 7 5 725 725 25 625 625 6 5 615
7 V( s2 n8 I( E# Q r' n% E10 102 102 102 102 102 102 1 2 12 123 123 123 123 1 3 13 713 713 713 713 7 3
: O$ Z5 d* t/ B7 G) p% ~
- Y; t/ o/ f% y. b! [6 l& n024 024 02 0 2 012 012 012 012 012 012 012
8 [% z) A |6 v! M4 t3 ]615 61 614 614 6 4 634 634 34 3 4 34 345
+ c% x' u0 |# t! O- h& q; n& E73 735 735 735 735 7 5 75 675 675 675 67 % _3 H1 P( W2 X# X( b( O# U2 B
4 |8 T6 j5 T4 n# i) S+ s# r( i
9 r$ F2 J. v! }2 c8 [9 J765 765 765 765 765 765 765 7 5 75 753 753 753 753 7 3 73 173 173 173 173 1 3 S+ c! e$ R) L: D+ o
432 43 4 3 43 143 143 1 3 163 163 16 162 162 1 2 152 152 52 052 052 0 2 072 0 S' V9 v" X1 j/ O( T. n3 c% Z
10 102 102 102 02 0 2 042 042 042 042 04 0 4 064 064 064 064 64 6 4 654 654 ( v5 t+ H% i5 J
" L4 j. \1 ^: A6 \% u# |! E13 132 132 132 132 1 2 12 012 012 012 012 1 h; G, V. ^4 x1 ] g
072 07 074 074 0 4 034 034 34 3 4 34 345
( u! H7 {$ K H) X654 654 65 6 5 675 675 675 675 675 675 67 8 E, O& I# e" S6 s6 J" H
7 K/ ~0 q# _; P4 f+ Q! n5 @! n
- y! q% c4 i" E$ ~765 765 765 765 765 765 765 765 765 765 765 7 5 75 175 175 175 175 1 5 15 152
5 a5 x2 X+ e& v432 43 4 3 43 143 143 1 3 13 132 132 1 2 162 162 62 062 062 0 2 072 072 07
+ k1 g }9 v: `0 q0 `$ z' [: S10 102 102 102 02 0 2 042 042 04 0 4 034 034 034 034 34 3 4 364 364 364 364 + h1 ?0 E* I1 H" J
5 `& G) [( k8 z. X4 R# M. R152 1 2 12 012 012 012 012 012 012 012 012
9 J6 t% N8 W5 v# v3 T' a' ~9 I* d0 7 057 057 57 357 357 357 35 3 5 345 345
: f \. ^! J: h. [# z: ]% O364 364 364 364 64 6 4 64 647 647 6 7 67
1 H3 |; @+ O6 V* s1 A3 V
$ ~& d" G; }2 }. u6 y5 z
8 h! Y8 Y- ^* A% u765 765 765 7 5 75 475 475 475 475 4 5 45 452 452 4 2 42 142 142 142 142 142 7 ]8 \' k( ?0 P* m7 I' Z
432 432 4 2 462 462 62 162 162 1 2 172 172 17 1 7 157 157 57 357 357 357 35 3 J9 e! L7 E. Z" v. F
10 1 0 130 130 130 130 30 3 0 360 360 360 360 360 360 360 360 60 6 0 60 607 9 J! s! w3 h& k& `, w
. O( {: g3 g2 f7 n. f
142 142 142 142 142 1 2 12 012 012 012 012 - ]& p3 @; \! a$ B5 V6 D( y+ V% Y
3 5 305 305 05 0 5 045 045 45 345 345 345 & ]. \* k1 J# U
607 6 7 67 367 367 367 367 367 67 6 7 67 + s! q5 E. z% v' q6 L, X4 \8 s
- b) F, y+ u$ J6 [
+ W5 R/ [1 }: a% T- P; \765 765 765 765 65 6 5 645 645 64 6 4 624 624 624 624 62 6 2 632 632 632 632 & s( @- e+ Y' ^7 D2 u) K
432 432 4 2 42 742 742 7 2 72 725 725 7 5 735 735 73 734 734 7 4 704 704 04 * k5 M7 G _5 l
10 1 0 130 130 130 130 130 130 130 130 130 1 0 10 105 105 105 105 1 5 15 715
) s" g$ l6 U! G' X# H
4 V/ ~1 W! G* {4 l6 o7 m9 Y6 J5 D 32 3 2 302 302 302 302 02 0 2 012 012 012 ! X% }9 F' Y* G6 K* \/ g Z# A
604 604 6 4 614 614 14 314 314 3 4 34 345
1 v; U: @% d% X715 715 715 7 5 75 675 675 675 675 675 67
! S: U* V, q$ y" L2 |& F, q( F
/ d/ l1 e8 f1 ?. _* O765 765 765 765 765 765 765 765 65 6 5 625 625 62 6 2 602 602 602 602 02 0 2
$ o0 h' `& i, _9 Y432 432 4 2 42 420 420 420 20 720 720 7 0 70 705 705 7 5 715 715 15 615 615 ! n3 F! U" J v; V# n
10 1 0 130 130 13 1 3 13 413 413 413 413 413 413 413 413 4 3 43 743 743 743 ! H% n5 h/ Q- u8 ?, s
" w0 E3 q4 [) |% j+ L4 {8 x
012 012 012 012 012 012 012 012 012 012 012 3 W& a! [% C1 D7 n
6 5 645 645 64 6 4 634 634 34 3 4 34 345 3 y& n, U3 t. |) Z7 A% F
743 7 3 73 735 735 7 5 75 675 675 675 67
) A7 u1 ^. ` d& |9 p6 i6 v( p3 m- t! u: E
u% q8 l0 Y. N& e- @% U, ]6 O
765 765 765 765 65 6 5 635 635 635 635 635 635 635 635 635 635 35 3 5 325 325 # v5 g! V% I, @% H. C! z- s
432 432 432 32 732 732 7 2 72 472 472 4 2 42 420 420 420 20 620 620 6 0 60
# o6 p, ^, v1 g# O2 x/ ^5 t" `0 N10 1 0 10 410 410 410 410 410 10 1 0 170 170 17 1 7 17 417 417 417 417 417
+ ~- }2 W7 H; I( ]3 {5 L0 m2 S! ]
+ W7 x$ y2 @8 d' z2 F: W" Z32 3 2 302 302 302 302 02 0 2 012 012 012 $ q ~6 Y( y- I0 n, o
605 605 6 5 615 615 15 315 315 3 5 345 345 / p* b+ [1 O. o1 C
417 417 417 4 7 47 647 647 647 647 6 7 67
9 n6 Z! i5 G1 m% j! L, g0 k0 N; G3 K+ e
4 ~* r6 R9 }% X6 e$ K7 }+ {9 v
0 B* m; A! V J3 L9 U5 L/ `1 ^765 765 765 765 65 6 5 635 635 635 635 635 635 35 3 5 325 325 32 3 2 302 302
' F. |! P4 y$ N7 p$ z& m5 ?432 432 432 32 732 732 7 2 72 720 720 720 20 620 620 6 0 60 605 605 6 5 645 & b p% c( J; D# M
10 1 0 10 410 410 410 410 410 41 4 1 41 741 741 741 741 741 741 741 741 7 1 6 @# j9 b+ f \, \* Z4 N/ Q
& \% Q( B# [0 N. P3 S7 A# S302 302 302 302 302 302 02 0 2 012 012 012 o4 m" ?: a& Y4 c" q
645 64 6 4 614 614 14 314 314 3 4 34 345
1 `& X- j# h: C71 715 715 7 5 75 675 675 675 675 675 67
作者: fly_eager 时间: 2005-4-27 16:10
很有兴趣！
作者: 罗炳 时间: 2005-5-2 14:44
请教
后面的数字是什么意思啊
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) |
Powered by Discuz! X2.5 |