|
喜欢迎接挑战的请进来!
) {2 R0 N! ?8 ]- G: O5 W《小擂台》 " W9 [- R: ~; E
这是一个若干年前的一个数学问题,当然是已经解决了的问题,之所 , l/ _& p/ z( D7 a9 o9 L
以贴出这个题目,是因为正当“非典”肆虐,许多网友有时间思考,对于
% z" m4 w8 h: ~+ ^我们来说,这是一个机会,何不适时迎接一个小小的挑战,丰富我们的业
, s& s% x1 d% i7 x; Z4 i0 |余生活,何况这个题目在今天研究,已经具有双重的考验作用了。 " G P: }% q, c8 J w3 D# ]
不要去找现成的答案。也不是那么好找。 % `+ v: e' I& I5 R/ a6 }% S/ b+ [
一是完全用我们的大脑来解决问题,这个难度是有相当档次的。 2 Q! T S$ E/ [
二是我们部分网友已经掌握的高超的电脑软件设计能力,可以设计出 e" O* a, _3 f0 z! N; |
一个解决问题的搜索程序,解决这个问题。
* M8 p3 {1 y; J 0 G5 X7 I7 Y* s0 g, M& o
1、题目的来历:在欧洲,自600年前,就时髦着一种智力游戏——重
3 q7 n2 f* U: W+ b3 A$ U排九宫。这种游戏类似于我们中国古代的“华容道”游戏,规则如下: " O7 h' t, k0 q* g( @% `; f+ H
在一个九宫图中(也就是横竖三行三列方格的方格图),从左上角第一格
% r! Y0 ?/ J) c7 [& |4 x7 J; K2 X开始,依次填上1、2、3、4、5、6、7、8八个数字,第九格空,然后在空 ) @6 f" {+ U) ^3 O5 R! \: u" B
格处移动与空格相邻的一个数字,再移动新产生的空格相邻的数字中的任 : }& y( f1 Z! x$ k: ]" q t0 v5 k
意一个数字,任何数字必须遵循这个规则移动。最后达到数字排列成8、7、 9 U* X& g( l6 c5 g* }; g5 w
6、5、4、3、2、1的顺序,就是重排九宫完成了。设每一个数字移动一格 {& C; z4 Y" q0 M
为一次或一步,那么用的步数越少就越好。在欧洲古代,往往能够在40步 5 U) }& z9 G7 {3 f! {& y
以内完成就是智商很高的体现了。
7 p7 I' J% z) q o 2、寻找最优解。重排九宫的最优解实际上就是最少步数重排了九宫。 6 M% N5 h, z) n/ w/ H
但是在这个游戏欧洲时髦了5、6百年实际上连一个最优解也没有发现。 ( m6 e5 ~4 |8 h
事实上,20多年前美国计算机科学家就是依靠那时的最先进数学手段
1 I! E" O" L) h6 r——电脑(大概是晶体管的)在设计了一个搜索程序以后,耗费了几个小 $ Q" X, q- D1 O" O" x
时的计算机运算时间,才找到了全部的最优解。
. Q6 }% D* y. r$ ~# ^3 ?# b 他们宣布,这十个只用30步就可完成的最优解,用人的大脑是不可能 0 r) Z, R% H# F; Y/ C8 T
完成的。 $ w' k! V1 _' z) w0 c( ]3 t
事实上,在20多年前当这个题目在国内公布之后,在短短的半年内, 0 h t; p- P) x' X: H7 O
就有51名各界的人士给出了全部最优解。当时可以说是一个扬眉吐气的事
5 Y8 y6 z+ C6 e' E. Y H5 p件。体现了中国人的聪明才智。因为那时可以说我国的科技水平,尚不可 ( b7 z) e; D: N3 s. G" n
能有那么多的人可以利用最先进的手段——电脑来帮助我们做此事。显然 ' L- n+ u7 U% W
是依靠中国人大脑的智慧回答了了这个美国数学家认为“依靠人的大脑不
% ]3 b' i# k$ @可能找到这十个最优解”的结论。
; X3 Q& k# ]) D% E7 ] 时代的变迁,科技水平是以爆炸式的方式发展,目前这样的问题解决 2 o D$ A$ c1 e* u7 [ N
的手段显然已经超过了当年美国数学家的时代。或许有一个软件设计天才 8 f0 b* ^6 H& g0 y& M! s( `# Q
可以设计出一个搜索程序,不是利用几小时,而是几分钟或几十秒几秒就
' X0 f4 A( _' G8 p5 \& e" R找到这十个最优解,这都是可能的。
5 Z& ]8 T) U% X, G 科技的威力在解决此题与战胜SARS这件事上异曲同工。
2 O! p0 |& P7 p M ] 擂台已经摆下:请给出这十个最优解。 3 d. c& I M9 m$ Z. R3 H+ i
补充:这是以前曾经出过的一个趣题,在现有的数学工具和编程技术条件下,本论坛必有高手很块就会给出答案,这是第一问.
+ D' v5 f0 m" L" j) t @; F / L& x- ?$ \) e) ?
加一下难度给个第二问: c# q2 a5 y1 y) B8 I
1 t$ m1 S4 r$ I h7 J 证明:重排九宫最少步数为30步,并且只有十个最优解 |