| | 首页 | 会员专区 | 公共用户区 | 数学建模 | 江中数学 | 留言反馈 | | |
| |
 |
您现在的位置： 21世纪数学 >> 公共用户区 >> 美丽数学 >> 趣味数学 >> 正文 |  用户登录  新用户注册 |
|
|||||||||||||||||||
| 渡河 | |||||||||||||||||||
| 作者：佚名 文章来源：东山教育信息网 点击数： 更新时间：2003-7-26 | |||||||||||||||||||
题目：猎人要把一只狼、一头羊和一篮白菜从河的左岸带到右岸，但他的渡船太小，一次只能带一样。因为狼要吃羊，羊会吃白菜，所以狼和羊，羊和白菜不能在无人监视的情况下相处。问猎人怎样才能达到目的？ [解]：稍加思考就可得到渡河的方法，如下： 第一次，猎人把羊带至右崖； 第二次，猎人单身回左岸，把白菜带至右岸，此时右岸有猎人，羊和白菜； 第三次，猎人再把羊带回左岸，放下羊，把狼带至右岸，此时右岸有猎人，狼和白菜； 第四次，猎人单身回到左岸，最后把羊带至右岸，便可完成渡河的任务。 这是一个著名的古题，同样也是“图论”应用的经典例子，在这里，我们再向读者介绍一下，使用图论的方法是如何解答本题的。 首先，用字母P、L、C和X分别代表猎人、狼、羊和白菜，即 P——猎人，L——狼，C——羊，X——白菜。用字母的组合表示左岸的情况。例如，开始时，狼、羊、白菜和猎人全在左岸，我们就用LCXP表示；又若左岸只剩下狼时，就用L表之，等等。因为狼和羊、羊和白菜不能在无人监视的情况下共处，所以在整个渡河过程中，左岸始终不允许出现LC、CX、LP和XP所表示的情况（在后二种情况下，右岸将会出现羊和白菜或狼和羊在无人监视下共处的情况，这也是不允许的）。仔细地列出左岸所允许出现的全部情况，它们是： LCXP，LCP，CXP，LXP，LX，CP，C，L，X，ψ，其中记号ψ表示左岸已空无所有。 其次，把上列十种情况用点表示在图上，对于任意二种可能情况，如果经过一次渡河就可互相转变的话，我们就用一条曲线段将它们相联。例如LCP代表河左岸有狼、羊和猎人，如果猎人带走羊C，左岸只剩下狼L；若猎人带走狼L，左岸就变成只有羊C的情况（因为狼和羊、羊和白菜不能单独共处，所以猎人不能单独渡河）。这说明了LCP与L，LCP与C都可经一次渡河互相变换，于是在LCP与L之间，LCP与C应该用曲线段联起来。分析存于各种情况之间的联系，并作出所有可能的曲线段，我们得到下图。 最后，用A表示LCXP，用B表示ψ，那么只要在图中找到一条由A到B的通道（折线），实际上就给出了一个满足题意的过渡方法。图中箭头所示的粗黑线便给出了这样一条通道，不难看到，它与我们一开始使用的渡河方法是不相同的。 |
|||||||||||||||||||
| |||||||||||||||||||
