ITPub博客

首页 > 应用开发 > IT综合 > 修道士过河问题 (转)

修道士过河问题 (转)

原创 IT综合 作者:gugu99 时间:2007-11-11 17:40:20 0 删除 编辑
修道士过河问题 (转)[@more@]


设有m个野人,n个修道士,(m≤n)船上可坐c个人。
1. c=1,无解;
2. c=2,对较小的M,N有解,对于较大的M,N无解,比如m=n=4,c=2无解;
3. c=3,情况同上;
4. c>3,分情况讨论如下:
(1) m=n,
此时可以按照下面的方案设计(下面S表示野人savage,R表示修道士religious, B表示船boat, ||表示河)
方案一:

m S ||  (m-c)S || cS  (m-c+1) S  || (c-1) S  (m-c+1)S || (c-1)S  (m-c+2)S || (c-2)S
m R ||  =>  m R ||  =>  m R  ||  =>  (m-c+1)R || (c-1)R  =>  (m-c+2)R || (c-2)R
B  ||  ||  B  B  ||  ||  B  B ||

于是又回到了开始时候的情况,两岸的S,R相等且船在左岸,已经有c-2个S和c-2个R过了河。依次做下去,最终所有的人都会过河;
还有一种方案:
方案二:
mS ||  (m-[c/2])S || [c/2]S  (m-[c/2]+1)S || ([c/2]-1)S
mR ||  => (m-[c/2])R || [c/2]R  =>  (m-[c/2]+1)R || ([c/2]-1)R
 B ||  ||  B  B ||
 最终也会到两岸S,R相等而船在左岸的情况,有[c/2]-1个S和R过了河。
 
 当c为偶数时,方案一和方案二的过河速度是一样的;当c为奇数时,方案一要比方案二快。
 当m=n时,一些特例需要考虑:
 a. k≥m+n,让所有人一次全部过河;
 b. k≥m, 用上面的方案一;


(2)n>m时,
①n=m+1,又分以下两种情况:
(a) c为偶数,方案如下:

方案三:

mS ||  (m-c)S || cS  (m-c+1)S || (c-1)S  (m-c+1)S || (c-1)S  (m-c+1)S || (c-1)S
nR ||  =>  nR ||  =>  nR ||  =>  (n-c)R ||  cR  =>  (n-c+1)R || (c-1)R
 B ||  ||  B  B ||  ||  B  B ||

 令m'=m-c+1,n'=n-c+1,则又重复了n'=m'+1的情况;

(b) c为奇数,设c=2h+1,显然a的方案三也可用,另外还有以下方案:

方案四

mS ||  (m-h)S ||  hS  (m-h)S || hS
nR ||  => (n-h-1)R || (h+1)R  => (n-h)R || hR
 B ||  ||  B  B || 

令m'=m-h,n'=n-h,又回到了n'=m'+1的情况。按照这个方案每次h个S和h+1个R过河,然后1个R回来。

当c为奇数的时候a,b两种方案的过河速度一样。

②n≥m+2时:
(a) c为奇数时,可以用n=m+1的情况b的方案四。

(b) c为偶数时,设c=2h,可以每单次过h-1个S,h+1个R,然后回来一个R,每双次过h个S,h个R,回来一个R.具体如下所示:
方案五:


mS ||  (m-h+1)S || (h-1)S  (m-h+1)S || (h-1)S  (m-2h+1)S || (2h-1)S  (m-2h+1)S || (2h-1)S
nR ||  => (n-h-1)R || (h+1)R  =>  (n-h)R ||  hR  =>  (n-2h)R ||  2hR  => (n-2h+1)R || (2h-1)R
 B ||  ||  B  B ||  ||  B  B ||

 令m'=m-2h+1, n'=n-2h+1,重复上述过程。

算法设计的总思路是每次过河的人尽可能地多,回来的人尽可能地少,当n>m,c≥2的时候总是有解。

上述的算法已经说的很清楚了,程序你应该可以自己写出来吧。

这个问题是NOI复赛考过的题目,题目不难,但是要注意讨论全面。


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10748419/viewspace-981741/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
  • 博文量
    3122
  • 访问量
    2245681