|
喜欢迎接挑战的请进来! / @3 r0 d4 h# O& ?/ k; w
《小擂台》 6 A( n& b) A* V+ V) L" l! ]
这是一个若干年前的一个数学问题,当然是已经解决了的问题,之所
/ z+ n7 n/ S9 y6 ~% ?4 @" W以贴出这个题目,是因为正当“非典”肆虐,许多网友有时间思考,对于 " G# X. c+ v2 e! ? B, P
我们来说,这是一个机会,何不适时迎接一个小小的挑战,丰富我们的业 # p8 j( y' d9 L4 \+ |3 A7 r9 V
余生活,何况这个题目在今天研究,已经具有双重的考验作用了。
2 Q/ b; A4 }, z7 ^( m: f0 t9 C 不要去找现成的答案。也不是那么好找。
$ C- \6 V3 ]0 Z; V; g 一是完全用我们的大脑来解决问题,这个难度是有相当档次的。 3 w5 k/ S9 O% L% ~
二是我们部分网友已经掌握的高超的电脑软件设计能力,可以设计出
/ z: i2 i3 U) L) j一个解决问题的搜索程序,解决这个问题。
9 U* l( T! z/ P3 J9 i! o3 ^ - U' A+ e- }4 T" t" m7 n
1、题目的来历:在欧洲,自600年前,就时髦着一种智力游戏——重 # Y- A$ R: H- O0 S# W
排九宫。这种游戏类似于我们中国古代的“华容道”游戏,规则如下:
8 f# s. C9 T7 T6 `3 {0 l p' }在一个九宫图中(也就是横竖三行三列方格的方格图),从左上角第一格
, P1 l# y$ C" q开始,依次填上1、2、3、4、5、6、7、8八个数字,第九格空,然后在空 8 H( C/ @% D* W6 q
格处移动与空格相邻的一个数字,再移动新产生的空格相邻的数字中的任 ]+ D3 A6 x4 c8 |7 f
意一个数字,任何数字必须遵循这个规则移动。最后达到数字排列成8、7、 ( p$ I V. a+ L% C) l, s
6、5、4、3、2、1的顺序,就是重排九宫完成了。设每一个数字移动一格
6 f9 P0 v* x: B, S+ O: O. w为一次或一步,那么用的步数越少就越好。在欧洲古代,往往能够在40步
$ f: H: y. y- i1 w% ^以内完成就是智商很高的体现了。
! Y+ L& P" E) K! x 2、寻找最优解。重排九宫的最优解实际上就是最少步数重排了九宫。
3 _. r2 k- i& N5 i% n( J' @ 但是在这个游戏欧洲时髦了5、6百年实际上连一个最优解也没有发现。
2 ?4 r7 D8 Z$ P! t7 X0 H& Z7 `0 S 事实上,20多年前美国计算机科学家就是依靠那时的最先进数学手段 % ^9 u) q& `8 F3 {
——电脑(大概是晶体管的)在设计了一个搜索程序以后,耗费了几个小 4 V* I" ~- Y" |& J! ]# J: Y V$ N
时的计算机运算时间,才找到了全部的最优解。
T6 g3 F$ L4 d" s 他们宣布,这十个只用30步就可完成的最优解,用人的大脑是不可能 3 j" b8 W. u- C+ B
完成的。
7 F l) J! K' z; `# V 事实上,在20多年前当这个题目在国内公布之后,在短短的半年内, * c$ \$ Y* T! k1 X
就有51名各界的人士给出了全部最优解。当时可以说是一个扬眉吐气的事 $ T6 R7 y: z' Y; \) Z
件。体现了中国人的聪明才智。因为那时可以说我国的科技水平,尚不可 1 \( u' J5 |5 I, z! y6 V
能有那么多的人可以利用最先进的手段——电脑来帮助我们做此事。显然
; b2 u% E# d8 O: P是依靠中国人大脑的智慧回答了了这个美国数学家认为“依靠人的大脑不
$ s% F2 B% g, y- F( D可能找到这十个最优解”的结论。 8 b7 l; e$ e* E1 O3 P
时代的变迁,科技水平是以爆炸式的方式发展,目前这样的问题解决
2 D# M# X0 F9 I& S( l0 L的手段显然已经超过了当年美国数学家的时代。或许有一个软件设计天才 % ^. s- t, _7 [4 e* e" h" o9 v
可以设计出一个搜索程序,不是利用几小时,而是几分钟或几十秒几秒就 * ^) F) T6 R7 P+ i8 e, [7 }7 t8 F
找到这十个最优解,这都是可能的。
( @, Y: Y* `5 ^: k* J" w1 M 科技的威力在解决此题与战胜SARS这件事上异曲同工。
( ]6 I8 ]- k# q9 K4 F% F2 w 擂台已经摆下:请给出这十个最优解。 + f _/ S8 G, O9 D6 l* S: h+ y
补充:这是以前曾经出过的一个趣题,在现有的数学工具和编程技术条件下,本论坛必有高手很块就会给出答案,这是第一问.+ V! {& W f2 r% g: x2 t
. e/ o7 A" F2 ^ 加一下难度给个第二问:) F# C8 l; S- r; m& @
# ~' Q, |* c* W! P4 i 证明:重排九宫最少步数为30步,并且只有十个最优解 |