讨论/技术交流/求助|求大佬科普一下什么是'过江问题'?/
求助|求大佬科普一下什么是'过江问题'?

机试遇到两个题,一个是LC.135分糖果的变种;另一个说是经典问题过江问题,貌似听说过,但是没想出来 T_T
描述大概是这样的:东岸有若干农夫和若干盗贼要渡河到西岸去;如果一侧盗贼多余农夫,则盗贼会杀死农夫;船最多可以坐2个人;现在给你两个整数m和n,代表东岸农夫和盗贼的数量;求能安全渡河的渡河次数(用多少次船)。
大概是这样描述的,可能有细节没说对。

1
共 7 个回复

3个商人和3个强盗要过一条河,如果在河的任意一边商人数目比强盗少,商人就会被抢劫,如何过河?

河边有一只小船

小船上原本无人

小船最多能坐2人

他们都不会去游泳

要保证商人不会被抢劫

/   过渡   /

/   答案   /

问题分析

先简化一下商人和强盗:

商人为0

强盗为X

河为-

初始情况:商人和强盗都在河的一边,即000xxx-

操作步骤:

1商人1强盗过去 一商人回000xx-x

2强盗过去 1强盗回 000x-xx

2商人过去 1商人1强盗回 00xx-x0

2商人过去 1强盗回 xxx-000

2强盗过去 1强盗回 xx-000x

2强盗过去 完毕 -xxx000

4

这个应该是离散数学里的经典问题,也就是需要获取所有安全状态,是否存在一条路径从起始安全状态到终点安全状态。可以画在一个二维图上会更清楚

1

让盗贼全过去那么就会变成过去一个农夫死一个农夫了 哈哈哈哈哈哈哈

1

先让盗贼全过来,就变成了单向问题了- - good 毕竟你可没说最少需要多少次- -

1

有的,但是我忘了,肯定是在可解的范围内。

给的初始m,n有范围限制吗,如果2<m<n+2岂不是永远没法安全渡河?

哈哈。。