过河问题

来自计算思维百科
跳转至: 导航搜索
过河问题.jpg

河岸有三对夫妇,他们都要过河,可是只有一条能乘两个人的小船,而且,这三个男人都很保守,他们不希望自己的妻子在他本人不在的情况下和别的男人在一起。

请想想,用什么办法把他们都渡过去。当然,船要他(她)们自己划。因此每次渡河都要有人划回原处,直至全渡过去为止。

解决方案-合理调度法

过河必须满足两个条件。

条件一:男人的妻子必须时刻跟他的男人一起;

条件二:每次只能满足两个人过河。

还需要注意的一点,不是只有过河才能坐两个人,回来时也可以坐两个人。下面表格表示每次小船过河时的状态。用大写字母表示丈夫,对应小写字母表示他的妻子,例如A的妻子是a:

河岸人员

过河人员

返回人员

对岸人员

Aa Bb Cc

a b

a

b

Aa B Cc

a c

a

b c

Aa B C

B C

Bb

Cc

Aa Bb

A B

c

ABC

a b c

a b

C

Aa Bb

Cc

Cc

 

Aa Bb Cc

河岸人员表示当前河岸的人员,过河人员表示将要过河的人员,返回人员表示谁把船划回来,对岸人员表示已经到对岸的人员。

涉及的计算思维

过河问题是很经典的益智类问题,它们的共同点是列出一系列的制约条件(像这道题中自己的妻子不能跟别的男人同时过河),然后让你合理分配每次过河和返回的人员,让所有的人都到达河对岸,它体现了调度的计算思维(这次过河我要把船给谁)。这道题的关键点是返回的不一定是一个人,也可能是两个人,虽然返回两个人是浪费资源的表现,但是为了满足制约条件不得不这么做。