|
喜欢迎接挑战的请进来! . v2 L: t" k. E
《小擂台》 * u2 K7 B# @, c3 _, S$ S
这是一个若干年前的一个数学问题,当然是已经解决了的问题,之所
! | j+ [% O! [以贴出这个题目,是因为正当“非典”肆虐,许多网友有时间思考,对于 ( b/ ^/ O0 _5 Q
我们来说,这是一个机会,何不适时迎接一个小小的挑战,丰富我们的业
~: V" T/ f+ U余生活,何况这个题目在今天研究,已经具有双重的考验作用了。
% }$ s/ k O, z; x6 t6 y 不要去找现成的答案。也不是那么好找。 ; L, C3 B" ^/ G3 T6 O
一是完全用我们的大脑来解决问题,这个难度是有相当档次的。 $ a3 P! K& K' B2 E3 C/ K1 C" R/ W
二是我们部分网友已经掌握的高超的电脑软件设计能力,可以设计出 ( D/ i3 p* y4 J) S T
一个解决问题的搜索程序,解决这个问题。 # ]7 T% s5 H F5 c( i
& H, @; F8 b6 g! p. S$ A
1、题目的来历:在欧洲,自600年前,就时髦着一种智力游戏——重
* d! ~0 k, R' z$ e9 r排九宫。这种游戏类似于我们中国古代的“华容道”游戏,规则如下: - w3 G( `7 y! }+ a( {1 H
在一个九宫图中(也就是横竖三行三列方格的方格图),从左上角第一格 4 d3 w; M& d Z$ v; W% p+ _, T9 M
开始,依次填上1、2、3、4、5、6、7、8八个数字,第九格空,然后在空 8 V1 t% [) {( K) t9 k
格处移动与空格相邻的一个数字,再移动新产生的空格相邻的数字中的任
$ p1 h% I$ L9 A6 p" x# g, g9 i3 D$ R意一个数字,任何数字必须遵循这个规则移动。最后达到数字排列成8、7、 5 w K' }5 ~: w
6、5、4、3、2、1的顺序,就是重排九宫完成了。设每一个数字移动一格
* C# w$ d4 x* |6 n为一次或一步,那么用的步数越少就越好。在欧洲古代,往往能够在40步 2 Y7 [8 g) V- a
以内完成就是智商很高的体现了。 ' j1 P, }- ^6 I
2、寻找最优解。重排九宫的最优解实际上就是最少步数重排了九宫。
# u" _2 V! r1 K3 b5 R2 @8 \* N 但是在这个游戏欧洲时髦了5、6百年实际上连一个最优解也没有发现。 8 v- V, N- Q# {. h' Z
事实上,20多年前美国计算机科学家就是依靠那时的最先进数学手段 ' l; f j6 B( _ g8 {; {/ `
——电脑(大概是晶体管的)在设计了一个搜索程序以后,耗费了几个小 , m7 [$ Y" s% T* Y8 Y. F9 N0 @
时的计算机运算时间,才找到了全部的最优解。 8 I8 |& C$ s- C0 D4 t3 n
他们宣布,这十个只用30步就可完成的最优解,用人的大脑是不可能
& x1 ?% N0 [) [2 N$ a完成的。
/ s, J$ n7 o; i4 s' L+ c' X 事实上,在20多年前当这个题目在国内公布之后,在短短的半年内,
# D9 O2 ?( G$ |$ n就有51名各界的人士给出了全部最优解。当时可以说是一个扬眉吐气的事 ; N2 ]" H2 @" x# `" w* `$ T9 e
件。体现了中国人的聪明才智。因为那时可以说我国的科技水平,尚不可
+ k% I4 R5 Z9 _1 U- m7 S- S能有那么多的人可以利用最先进的手段——电脑来帮助我们做此事。显然
* E, |. ]8 s4 i* e" e, s是依靠中国人大脑的智慧回答了了这个美国数学家认为“依靠人的大脑不 ; `" z7 B+ F3 O! o" Z
可能找到这十个最优解”的结论。 ( d# j( B8 M/ l* B$ I- O% D
时代的变迁,科技水平是以爆炸式的方式发展,目前这样的问题解决 9 _; L9 T. p$ `, H' q
的手段显然已经超过了当年美国数学家的时代。或许有一个软件设计天才
4 }' k( S: u0 @3 W. j可以设计出一个搜索程序,不是利用几小时,而是几分钟或几十秒几秒就 9 P- l2 e( O# w3 E6 n' t
找到这十个最优解,这都是可能的。
* v. H/ D! ]( V/ F3 L4 a" [$ [ 科技的威力在解决此题与战胜SARS这件事上异曲同工。 . A: O. W& D, t- l8 f3 A
擂台已经摆下:请给出这十个最优解。 # f& N' M& \$ s
补充:这是以前曾经出过的一个趣题,在现有的数学工具和编程技术条件下,本论坛必有高手很块就会给出答案,这是第一问.6 Y+ l# i% t% f, g0 P5 [4 w0 W7 ^
]3 N/ L/ ?+ a 加一下难度给个第二问:
V% [/ b7 f! p. P, E) k
; m1 v: q5 O# x 证明:重排九宫最少步数为30步,并且只有十个最优解 |