经典过河谜题

来自计算思维百科
跳转至: 导航搜索
经典过河谜题1.png

一个农夫带着一只狼,牵着一只羊,挑着一担菜去赶集,前面有一条河拦住了他,河边有一艘船但船太小一次只能载农夫和他所带的其中一种东西,农夫知道狼会吃羊`羊也会吃他所带的菜,要在都不被吃的情况下农夫怎么过去?

解决方案

方案1-穷举法解决过河问题

思想:通过列出各种可能的组合顺序,寻找满足条件的组合顺序。

Plan 1:农夫带羊到对岸—>农夫自己回去—>农夫带狼过去—>农夫自己回去  ×(狼会吃羊)

Plan 2:农夫带羊到对岸—>农夫自己回去—>农夫带菜过去—>农夫自己回去  ×(羊会吃菜)

Plan 3:农夫带羊到对岸—>农夫自己回去—>农夫带狼过去—>农夫带羊回去—>农夫带菜到对岸—>农夫自己回去—>农夫带羊到对岸 (√)

 . . . . . .

这种方法可以解决问题,但每次都要考虑两岸的情况,在列举的的过程中极不方便。

方案2-变治法将过河谜题转为图问题解决

思想:我们用P,w,g,c分别表示农夫、狼、羊和白菜;双直线||表示河。边表示过河,边上的标记表示过河时的负载。我们希望找出一条从 Pwcg ||到 ||pwcg的路径。这样就把过河谜题转化成了一个图问题,具体过程如下:(过河的过程中不该存在无意义的过河,如上次为农夫和羊到了右岸,那紧接着的下次农夫就不能又把羊带过去)

经典过河谜题2.png

很容易看出,在Pwgc||与||Pwgc之间存在着两条不同的路径,说明农夫有两种方法可以把所有东西带过河,且每个方法都需要过7次河(路径的长度)。

涉及到的计算思维

在我们碰到这个问题的时候,第一反应可能就是去列举各种可能出现的情况,然后一直找到一种可行的方法;但解决这个问题可以利用变治法将其转变成一个图问题,这个过程就体现了计算思维中的转化思想。