发信人: agx()
整理人: (2000-11-23 22:34:02), 站内信件
|
原题如下:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
有三只母狮子,它们各自带一只小狮子。
我们就用A、B、C来代表母狮子,用a、b、c来代表小狮子!!!
A狮子要照顾a狮子,如此类推!母狮子不会互相攻击,小狮子也不会互相攻击.
但母狮子不在,自己的小狮子就有危险了!!!
母狮子全过撑船,小狮子只有c会撑船!
现在问题来了:
它们要过一条河,但只有一只船,每次只能载两只狮子(不论大小),
怎样才能将所有狮子安全运过河对岸?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
思路:
因为不允许存在这样一种状态——一个没有大狮子保护的小狮子和其他的大
狮子同处一边,而且一条船又只能够坐下两只狮子,所以应当存在如下两种状态
:
未过河 已过河
a b c | 河 | A B C
A B C | 河 | a b c
找到了中间状态,发现从第一种状态推到最后全部过河的状态比较简单,而第二
种状态推回全部未过河比较简单,于是,正确的过河顺序就出来了。。。
正确顺序:
注: "U" 表示小船
未过河 已过河
第 1趟: Aa Bb Cc |U 河 |
第 2趟: Aa B C | 河 U| b c
第 3趟: Aa B Cc |U 河 | b
第 4趟: A B C | 河 U| a b c
第 5趟: A B Cc |U 河 | a b
第 6趟: Cc | 河 U| Aa Bb
第 7趟: Aa Cc |U 河 | Bb
第 8趟: Aa | 河 U| Bb Cc
第 9趟: Aa Bb |U 河 | Cc
第10趟: a b | 河 U| A B Cc
第11趟: a b c |U 河 | A B C
第12趟: a | 河 U| A Bb Cc
第13趟: a c |U 河 | A Bb C
第14趟: | 河 U| Aa Bb Cc
KO!
再注:由于Aa,Bb所处地位相同,所以有些地方可以互换。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
结论:找中间状态。
-- ※ 修改:.agx 于 Nov 21 09:13:56 修改本文.[FROM: 61.150.131.47] ※ 来源:.月光软件站 http://www.moon-soft.com.[FROM: 61.150.131.47]
|
|