“渡河问题”有几解

“渡河问题”有几解

有一则古老的智力游戏题:有一个人带着一只狼、一只羊、一筐卷心菜来到河边(这里假设狼是不吃人的)。河边正好有一条空着的小船。那人想将狼、羊、卷心菜都带到河的对岸去。可是船很小，每次都只能让他带走一样东西，如果带两样东西上船，船就会沉没。另一方面，如果没人照管，狼会吃掉羊，羊又很喜欢吃卷心菜，所以，狼与羊、羊与菜，在人不在的情况下，是不能放在一起的。怎么办呢?他应当采取什么样的渡河方案，才能把狼、羊、菜都安全地带到对岸去呢?

这个问题称为“渡河问题”，也有人称之为“狼、羊、菜问题”。对于多数人，要解决这个问题是不会有什么困难的，试上几次，就能给出一个符合要求的答案。但是，你能说出，该题共有多少解吗?人将狼、羊、卷心菜都安全地带到河的对岸去，至少需要摆渡几次呢?

先想一想，可以允许出现的状态有几种，也就是说不会有狼吃羊、羊吃菜现象的状态有几种。动动脑筋，你就会得到以下的结果:

第1种状态就是我们的初始状态，而第10种状态是我们要达到的最终状态。人划着船，每渡河一次，就会引起一次状态的改变。第一步，人要带一样东西过河，则河的这边只留下两样东西(表中的5、6状态)，只能是第6种状态，即人带羊过河。第二步，人把船划回来，即呈第3种状态。第三步，人再带一样东西过河，对岸可以出现两种情况(表中的7、9状态)，即可以有两种方案。我们先来看第一种，人带菜过河，即第7种状态。第四步，这次人不可能空船回来，因为羊会吃了菜，所以人必须带一样东西划船回来，当然不可能是菜，否则就等于取消第三步，回到第3种状态。因此人将羊又带回去，于是呈现的是第2种状态。第五步，人带狼过河(羊刚带回来，再带回去岂不重复)，现在是第8种状态。第六步，这次人可以空船回来了，因为狼可以和菜在一起，即第5种状态。第七步，人带羊过河，大功告成。

按照这种方法，第二种方案请你自己完成。你会发现，也是用了七步，也就是说，人要把狼、羊、菜都安全地带到河对岸去，至少要摆渡七次，而且，如果要求每种状态不重复出现，渡河问题只有两解。