QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3173|回复: 3
打印 上一主题 下一主题

[灌水]喜欢迎接挑战的请进来!

[复制链接]
字体大小: 正常 放大
god        

206

主题

2

听众

882

积分

升级  70.5%

该用户从未签到

新人进步奖

跳转到指定楼层
1#
发表于 2005-3-30 23:40 |只看该作者 |倒序浏览
|招呼Ta 关注Ta

喜欢迎接挑战的请进来! ; T! |( X3 s* o! G 《小擂台》 ) j+ b% w- v' C 这是一个若干年前的一个数学问题,当然是已经解决了的问题,之所 ) p# J1 f: L: e' m% V以贴出这个题目,是因为正当“非典”肆虐,许多网友有时间思考,对于 ' F+ |) t% L* e2 y我们来说,这是一个机会,何不适时迎接一个小小的挑战,丰富我们的业 8 o! N. V* O8 `: `& @( ^% d余生活,何况这个题目在今天研究,已经具有双重的考验作用了。 0 W7 Q+ ^! v/ u- i( @ 不要去找现成的答案。也不是那么好找。 5 D9 }% H7 Q, l5 f9 O4 R 一是完全用我们的大脑来解决问题,这个难度是有相当档次的。 - _" E' k2 I2 ?4 c0 @" ~# p& k, F 二是我们部分网友已经掌握的高超的电脑软件设计能力,可以设计出 / L% g% ?+ }3 n+ z' W& |( L一个解决问题的搜索程序,解决这个问题。 d; e. n8 m3 s- U* e7 N - V) k* C1 I& z& J 1、题目的来历:在欧洲,自600年前,就时髦着一种智力游戏——重 $ k" g# s- b, v排九宫。这种游戏类似于我们中国古代的“华容道”游戏,规则如下: 7 c; E4 D. w1 B7 Q9 \2 H7 Y在一个九宫图中(也就是横竖三行三列方格的方格图),从左上角第一格 3 Y! E7 Y- E* E8 T 开始,依次填上1、2、3、4、5、6、7、8八个数字,第九格空,然后在空 # c+ J E- T2 e0 [! N: w" D格处移动与空格相邻的一个数字,再移动新产生的空格相邻的数字中的任 3 H0 U9 J1 d7 N1 i e. N9 b 意一个数字,任何数字必须遵循这个规则移动。最后达到数字排列成8、7、 . m$ k3 b% U* l- U, e- P 6、5、4、3、2、1的顺序,就是重排九宫完成了。设每一个数字移动一格 & `2 k. I) R/ N1 x ]+ ~为一次或一步,那么用的步数越少就越好。在欧洲古代,往往能够在40步 w' k+ j+ M. @( n2 _0 y. i以内完成就是智商很高的体现了。 0 U+ W7 {5 b- M! ]$ p% k 2、寻找最优解。重排九宫的最优解实际上就是最少步数重排了九宫。 5 {) d7 Q$ T6 V1 i7 Z5 `+ n* u 但是在这个游戏欧洲时髦了5、6百年实际上连一个最优解也没有发现。 + s+ K" B; r! B- [. y' |$ c 事实上,20多年前美国计算机科学家就是依靠那时的最先进数学手段 ! f0 V, z9 @) c——电脑(大概是晶体管的)在设计了一个搜索程序以后,耗费了几个小 3 y |- A0 j e 时的计算机运算时间,才找到了全部的最优解。 ( v% b) x" {, x, Q- c 他们宣布,这十个只用30步就可完成的最优解,用人的大脑是不可能 & w8 I7 T' W* v! F 完成的。 6 R1 y/ C1 D. s0 r; P/ o" {& \ 事实上,在20多年前当这个题目在国内公布之后,在短短的半年内, & I& a) g9 p/ r3 d1 j 就有51名各界的人士给出了全部最优解。当时可以说是一个扬眉吐气的事 3 E) I( k9 r- z% N$ A件。体现了中国人的聪明才智。因为那时可以说我国的科技水平,尚不可 7 l' H, f3 f4 ?0 R; E0 w4 E能有那么多的人可以利用最先进的手段——电脑来帮助我们做此事。显然 g3 a% l4 R- Z' Y0 k; F是依靠中国人大脑的智慧回答了了这个美国数学家认为“依靠人的大脑不 % ^: W- Y3 p$ i 可能找到这十个最优解”的结论。 * e4 F' [' @- W- V 时代的变迁,科技水平是以爆炸式的方式发展,目前这样的问题解决 5 N4 I h+ U( u( y4 Q8 O0 z的手段显然已经超过了当年美国数学家的时代。或许有一个软件设计天才 % q" Q6 G* ]+ K# U3 J* C" [可以设计出一个搜索程序,不是利用几小时,而是几分钟或几十秒几秒就 # T" T& w4 c) N: k2 p找到这十个最优解,这都是可能的。 1 T7 ^* f8 J6 p; a/ \4 H) e2 c: n 科技的威力在解决此题与战胜SARS这件事上异曲同工。 ) O Z3 Z+ ?; Z1 _$ {- q 擂台已经摆下:请给出这十个最优解。 , T4 l, J, d7 g" F 补充:这是以前曾经出过的一个趣题,在现有的数学工具和编程技术条件下,本论坛必有高手很块就会给出答案,这是第一问.0 S3 O% t( Z- S: m6 {% D ; J: b8 k) b$ h2 q, x 加一下难度给个第二问: * ^2 ~- ^9 J! x/ C 3 X. ] M5 \5 L4 q/ o, | 证明:重排九宫最少步数为30步,并且只有十个最优解

zan
转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
如果我没给你翅膀,你要学会用理想去飞翔!!!
god        

206

主题

2

听众

882

积分

升级  70.5%

该用户从未签到

新人进步奖

765 765 765 7 5  75 475 475 475 475 4 5  45 145 145 145 145 1 5 15  153 153 153
& q; s; k. x! u  d432 43  4 3 463 463  63 163 163 1 3 173 173  73 073 073 0 3 043 043 04  042 042 ; Q1 e  ?. u# A6 P3 x
10  102 102 102 102 102  02 0 2 062 062 062 062  62 6 2 672 672 672 672 67  6 7 : @1 T7 ]% {* U$ c+ e# u
9 R8 c" H- d! A5 @1 z3 m/ S
153 1 3 13  132 132 1 2  12 012 012 012 012
5 t. a' b( y: q6 x; F0 2 052 052 05  0 5 035 035  35 3 5 345 345 8 ?- ~8 }1 N$ p' w7 w9 |/ K8 c1 r" E2 r
647 647 647 647 647 647 647 647 647 6 7 67  5 m2 k) x. y' Q  f4 C' \

/ x9 o' Y6 y# L. G7 t0 C1 N
3 b3 V7 D0 W0 X765 765 765 7 5  75 475 475 475 475 475 475 475 475 4 5 45  452 452 4 2  42 142
9 U, ]1 s4 q' T# t: f432 43  4 3 463 463  63 163 163 1 3 13  132 132 1 2 172 172 17  1 7 157 157  57 4 p) \9 C5 k) Q6 I
10  102 102 102 102 102  02 0 2 062 062 06  0 6 036 036 036 036 036 036 036 036
0 V$ ~- G6 [0 H$ n- F* g" ^/ y4 e
142 142 142 142 142 1 2  12 012 012 012 012
+ I0 k4 U2 K% N3 W& V0 H: H9 B9 J057 057 057 05  0 5 045 045  45 345 345 345 % G' `$ [5 l/ o& P0 S& X+ x
36 3 6 36  367 367 367 367 367  67 6 7 67  % [9 m) d" i$ y' M
3 f1 i3 w; C. @% R
5 p8 G8 _2 a1 y4 t4 G7 q5 {; t# s' L
765 765 765 765  65 6 5 645 645 645 645 64  6 4 604 604 604 604  04 0 4 024 024
7 U. e( Y2 m  v% B2 Q) U# H/ ?/ p6 D432 43  4 3  43 743 743 7 3 703 703 70  705 705 7 5 725 725  25 625 625 6 5 615   p4 U" q: l$ X
10  102 102 102 102 102 102 1 2 12  123 123 123 123 1 3  13 713 713 713 713 7 3
& V7 R; ~* |+ Y# M4 m# t8 q; b
024 024 02  0 2 012 012 012 012 012 012 012 7 H+ G& U6 m+ R! f
615 61  614 614 6 4 634 634  34 3 4 34  345 ' m4 S  U! P6 {: y6 a
73  735 735 735 735 7 5  75 675 675 675 67  
; j/ g6 @7 D# r$ I+ c2 e
- b- u) g* d- E+ W  O6 h* O, o  p
+ `0 p* t: T9 A765 765 765 765 765 765 765 7 5 75  753 753 753 753 7 3  73 173 173 173 173 1 3 " D8 E- u! j6 k9 d- r: V& e
432 43  4 3  43 143 143 1 3 163 163 16  162 162 1 2 152 152  52 052 052 0 2 072 2 t6 \$ i9 |- C; R* R
10  102 102 102  02 0 2 042 042 042 042 04  0 4 064 064 064 064  64 6 4 654 654 7 F: e6 d  J8 o* _, H; X

: n! I+ |# t5 G9 x! O; G8 A2 ~13  132 132 132 132 1 2  12 012 012 012 012 " O, p& V! [' m% z1 I) a
072 07  074 074 0 4 034 034  34 3 4 34  345
+ q5 Z: h1 @* t0 G; N: a654 654 65  6 5 675 675 675 675 675 675 67  ; F2 u$ `% J8 i- |9 S2 }( ~2 A9 o

4 a* r9 T/ @# R% I( }) j4 U0 e& L3 v7 l* W( I
765 765 765 765 765 765 765 765 765 765 765 7 5  75 175 175 175 175 1 5 15  152
; d( d: _& J9 Q432 43  4 3  43 143 143 1 3 13  132 132 1 2 162 162  62 062 062 0 2 072 072 07  # ?/ M. O+ b1 g# o
10  102 102 102  02 0 2 042 042 04  0 4 034 034 034 034  34 3 4 364 364 364 364 + L& a7 s1 Z, K  U' x7 s1 e% Z

. J1 `/ g5 S/ e* I$ r1 `) b152 1 2  12 012 012 012 012 012 012 012 012
& m1 A+ g) T+ Q, X/ Q( {/ \0 p0 7 057 057  57 357 357 357 35  3 5 345 345
0 b- X% X9 z: B( b364 364 364 364  64 6 4 64  647 647 6 7 67  3 Q6 Y8 K/ x6 s( u
8 \/ ~$ {6 Q7 u# A1 y9 c

3 E1 S7 ?9 L8 `' e( R7 ~# C+ H/ y765 765 765 7 5  75 475 475 475 475 4 5 45  452 452 4 2  42 142 142 142 142 142
8 m5 Z- A' N- k. b432 432 4 2 462 462  62 162 162 1 2 172 172 17  1 7 157 157  57 357 357 357 35  
& W, Z3 Q8 e( d( a( M+ W( n: 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 p6 Z1 N7 }4 V: J+ W; U6 B8 z2 N& ~* k+ H
142 142 142 142 142 1 2  12 012 012 012 012
" H* y1 v4 h9 R  C% G1 I8 K+ U3 5 305 305  05 0 5 045 045  45 345 345 345 ! U0 {" |& K$ I( c+ @8 V
607 6 7  67 367 367 367 367 367  67 6 7 67  
3 v  T+ {/ Q5 ]( c+ k' ^6 i
" w* r" k" r; i4 K0 }& o( S$ A9 g0 n4 P# i8 k' w" i
765 765 765 765  65 6 5 645 645 64  6 4 624 624 624 624 62  6 2 632 632 632 632 ) X  C0 K' F7 O( v& S
432 432 4 2  42 742 742 7 2 72  725 725 7 5 735 735 73  734 734 7 4 704 704  04 ! D! n* G- q9 ~- I) N/ m
10  1 0 130 130 130 130 130 130 130 130 130 1 0 10  105 105 105 105 1 5  15 715 1 ?3 N1 B$ i. F& u# |

5 D  p9 A; M8 ] 32 3 2 302 302 302 302  02 0 2 012 012 012
& [0 ~% d4 m1 l6 f- }# w604 604 6 4 614 614  14 314 314 3 4 34  345 6 i7 \. n4 i- N
715 715 715 7 5  75 675 675 675 675 675 67  + b/ z- u/ g% o
1 K2 ]/ f+ T: k& n9 Z# Z: M/ E

5 H0 T$ L. {& N/ l4 P5 l# `765 765 765 765 765 765 765 765  65 6 5 625 625 62  6 2 602 602 602 602  02 0 2 2 ]6 z0 D# X7 w$ G
432 432 4 2 42  420 420 420  20 720 720 7 0 70  705 705 7 5 715 715  15 615 615
- j  \6 G6 Q$ w* C; x; m10  1 0 130 130 13  1 3  13 413 413 413 413 413 413 413 413 4 3  43 743 743 743
, n" I0 h2 U2 ?. s0 J8 L" M2 A
012 012 012 012 012 012 012 012 012 012 012 4 N9 K2 T) {- W2 q4 l
6 5 645 645 64  6 4 634 634  34 3 4 34  345 + S2 v* ]- S3 g2 c/ V3 |% M
743 7 3 73  735 735 7 5  75 675 675 675 67  ( U: n0 L' V: C% \% l7 u+ Z. Y
6 \1 X% c. D" k* a+ t2 P, `& X
/ }5 Q' C( T& Q" ]5 |' S  L
765 765 765 765  65 6 5 635 635 635 635 635 635 635 635 635 635  35 3 5 325 325 7 @$ O0 ?1 R6 Y& s9 [; L7 V: n
432 432 432  32 732 732 7 2  72 472 472 4 2 42  420 420 420  20 620 620 6 0 60  & [6 W5 h1 g( e5 @$ W: L
10  1 0  10 410 410 410 410 410  10 1 0 170 170 17  1 7  17 417 417 417 417 417 4 L  e6 M; k5 G8 B8 L8 G9 b0 B
* E, p1 @8 ?4 y- {& Y
32  3 2 302 302 302 302  02 0 2 012 012 012 5 h0 y% x7 _  j# k, w
605 605 6 5 615 615  15 315 315 3 5 345 345 - u6 {' R) L0 F
417 417 417 4 7  47 647 647 647 647 6 7 67  
9 b/ X/ X* m/ S" p: |8 Z% {; v% t2 O2 H: P% U1 q$ X1 |: ?) l. A

+ o( A; F( }# q4 h" T/ L4 }: J765 765 765 765  65 6 5 635 635 635 635 635 635  35 3 5 325 325 32  3 2 302 302 . E, ?3 A0 W& }# x" ~) X
432 432 432  32 732 732 7 2 72  720 720 720  20 620 620 6 0 60  605 605 6 5 645
: K6 j, B; C3 N, |4 K10  1 0  10 410 410 410 410 410 41  4 1  41 741 741 741 741 741 741 741 741 7 1
* G* k  g; t8 s) L6 D* F6 C. v. y
: j( k8 u8 Z: r* l! K- T& M6 w302 302 302 302 302 302  02 0 2 012 012 012
- I9 ^6 B1 A* X$ [4 L645 64  6 4 614 614  14 314 314 3 4 34  345 ' r' k( A' C" j
71  715 715 7 5  75 675 675 675 675 675 67
如果我没给你翅膀,你要学会用理想去飞翔!!!
回复

使用道具 举报

fly_eager        

0

主题

2

听众

23

积分

升级  18.95%

该用户从未签到

新人进步奖

回复

使用道具 举报

罗炳        

0

主题

2

听众

31

积分

升级  27.37%

该用户从未签到

新人进步奖

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册地址

qq
收缩
  • 电话咨询

  • 04714969085
fastpost

关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

手机版|Archiver| |繁體中文 手机客户端  

蒙公网安备 15010502000194号

Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

GMT+8, 2026-7-27 09:09 , Processed in 0.623779 second(s), 68 queries .

回顶部