| « | August 2025 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | | | | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | | | | | | | |
|
| 公告 |
本站技术贴除标明为“原创”的之外，其余均为网上转载，文中我会尽量保留原作者姓名，若有侵权请与我联系，我将第一时间做出修改。谢谢！
——既瑜 |
| 统计 |
blog名称:★既瑜★
日志总数:183
评论数量:636
留言数量:-25
访问次数:1407031
建立时间:2005年3月12日 |
OICQ：215768265
njucs2001@hotmail.com
erichoo1982@gmail.com |
|
W3CHINA Blog首页 管理页面 写新日志 退出
 [【技术文档】]野人，修道士过河问题 |
[野人，修道士过河问题] 有一条河分割两岸，开始时左岸有m个野人，n个修道士 （m≤n）要过河 但是只有一条船，船上可坐c个人。在船上或在某边的岸上如果野人的数目大于修 道士的数目野人 就会吃掉修道士。要求给出一种对修道士安全的过河方案。 设有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复赛考过的题目，题目不难，但是要注意讨论全面。
|
阅读全文(2102) | 回复(0) | 编辑 | 精华 |
|
