阿拉伯夫妇过河问题

yinda_peng

大概两三天之后会发布答案，如果有鱼油在此之前写出来了，将提前发布答案
写对的鱼油给予评分奖励（非会员优先评鱼币，会员优先评荣誉），不仅写对还给出清晰解答的鱼油将额外给予贡献评分奖励
希望大家尽量自己思考，一道题目，你看答案写和没看答案写是完全不同的感受

有三对夫妻要过河，船最多只能载两人，

由于旧时阿拉伯法律约束，封建思想严重，

要求女子不能在丈夫不在场时与其他男性共处，

如何安排三对夫妇过河？

（记得考虑划船，可以使用编程求解哦）

提示：按男女分类，编程可考虑状态转移

    用向量(H,W)表示有H个男子，W个女子在起点，其中0<= H <= 3，0<= W <= 3.根据题意，一共有9个可取状态，它们是(0,0) , (0,1) , (0,2) , (0,3) , (3,1) , (3,2) , (3,3) , (1,1)和(2,2).定义运算向量为（(-1)^jm,(-1)^jn）,其中m,n = 0,1,2且1<=m+n<=2，j = 1,2,3……

    夫妻过河问题转化为：求由状态(3,3)经过奇数次运算转移到(0,0)的转移过程。

下面展示第一步运算过程：

    第二步是将(3,2),(3,1),(2,2)分别于运算向量进行计算，如此下去，容易验证，经过11次取运算之后可以完成。

为了便于计算机编程求解，记允许状态集合和可取状态集合分别为：

S = {(i,j)|i = 0,j = 0,1,2,3;j = 3,i = 0,1,2,3;i = j = 1,2},

D = {(m,n)|1<=m+n<=2,m,n = 0,1,2}

    并用S₁(m,n),S₂(m,n),...(S_k属于S)表示状态的变化过程，d_k(m,n)(d_k属于D)表示状态S_k下的过河方案，当k为奇数时，d_k表示从起点到对岸，当k为偶数时，表示从对岸到起点。状态转移满足下列关系：

                                                               S_k+1 = S_k+ (-1)^kd_k

    于是问题归结为：求d_k属于D(k = 1,2...)使(S_k属于S)状态按(2.5)式由初始状态S₁（3,3）经n步转移到S_n(0,0)的最小值n值。根据上述思路，现在就容易实现在计算机上实现了，如果计算过程出现循环，代表无解。

yinda_peng

参考思路已发布

yinda_peng

@中英文泡椒 @学习编程中的Ben @开心老六 @歌者文明清理员 @sfqxx

神佑邻祂

女 男
女1  男1
女2  男2
第一对男女划船到对岸之后，女划船回来，
接 女1 到对岸，然后自己下船。
女1 划船接 男1 到对岸，放下男1，然后再划船去接 女2 到对岸，然后自己下船。
女2 划船接 男2到对岸，一起下船。

蹲一个用编程求解的答案，我想不到怎么用编程求解。

歌者文明清理员

三对夫妻为 A1, A2, B1, B2, C1, C2
（1 男 2 女）

1. A1、B1 过河
2. A1 回来（B1 在对岸）
3. A1、C1 过河
4. C1 回来（A1、B1 在对岸）
5. C1、C2 过河
6. C2 回来（A1、B1、C1 在对岸）
7. C2、B2 过河
8. B1 回来（A1、B2、C1、C2 在对岸）
9. B1、B2 过河
10. B2 回来（A1、B1、C1、C2 在对岸）
11. A2、B2 过河

这样？

人造人

一对一对往过运么
先把第1对运过去，回来
再把第2对运过去，回来
然后是第3对运过去，再回来
完美

yinda_peng

歌者文明清理员 发表于 2024-3-16 11:42
三对夫妻为 A1, A2, B1, B2, C1, C2
（1 男 2 女）

7.8.9.检查一下

yinda_peng

神佑邻祂 发表于 2024-3-16 11:36
女 男
女1  男1
女2  男2

正确的

yinda_peng

人造人 发表于 2024-3-16 11:52
一对一对往过运么
先把第1对运过去，回来
再把第2对运过去，回来

要考虑划船哦，船只能载两人，谁划船回去，载谁过去，谁下船，没有这么简单滴

人造人

yinda_peng 发表于 2024-3-16 11:59
要考虑划船哦，船只能载两人，谁划船回去，载谁过去，谁下船，没有这么简单滴

这你的题目也没说呀
我还以为不算划船的，或者这船是自动的这类的
^_^

yinda_peng

人造人 发表于 2024-3-16 12:06
这你的题目也没说呀
我还以为不算划船的，或者这船是自动的这类的
^_^

行吧我的问题

歌者文明清理员

yinda_peng 发表于 2024-3-16 11:54
7.8.9.检查一下

神佑邻祂

歌者文明清理员 发表于 2024-3-16 16:12

思路没问题，就是后面几步有点多余了。
第7步之后，B2 直接回来带着 A2 过河就可以。
之前那几步所有男性都已经过去了，女性过去自己的丈夫就在，所以直接把女的一个一个带过去就可以。她丈夫肯定在。
而且第8步你括号里面，B2 自己的丈夫不在，和其他男人单独相处了。第7步里 C2 已经带着 B2 过河了，第9步 B1 又带着 B2 过了一次河。
前面还好，后面有点错乱。

中英文泡椒

分为ABC三对夫妻
1. 丈夫A和丈夫B过河，丈夫B划回来（终点的有丈夫A）
2. 丈夫B和丈夫C过河，丈夫C回来(终点有丈夫A,B)
3. 妻子A和妻子B过河，丈夫C和妻子C在原地，丈夫B和妻子B划回来（终点有丈夫A,妻子A）
4. 妻子B和妻子C过河，丈夫B和丈夫C在原地，丈夫A划回来(终点有妻子A,B,C)
5. 丈夫A和丈夫B过河，丈夫B回来(终点有丈夫A妻子A，妻子B和C)
6. 丈夫B和丈夫C一起过河

yinda_peng

中英文泡椒 发表于 2024-3-18 17:04
分为ABC三对夫妻
1. 丈夫A和丈夫B过河，丈夫B划回来（终点的有丈夫A）
2. 丈夫B和丈夫C过河，丈夫C回来( ...

如果先走两个男，那起点不就已经违反了么

中英文泡椒

yinda_peng 发表于 2024-3-18 18:47
如果先走两个男，那起点不就已经违反了么

那就先走妻子

分为ABC三对夫妻
1. 妻子A和妻子B过河，妻子B划回来（终点的有妻子A）
2. 妻子B和妻子C过河，妻子C回来(终点有妻子A,B)
3. 丈夫A和丈夫B过河，丈夫C和妻子C在原地，丈夫B和妻子B划回来（终点有丈夫A,妻子A）
4. 丈夫B和丈夫C过河，妻子B和妻子C在原地，妻子A划回来(终点有丈夫A,B,C)
5. 妻子A和妻子B过河，妻子B回来(终点有丈夫A妻子A，妻子B和C)
6. 妻子B和妻子C一起过河

wk012233

第一回合：男1和女1过河，男1回去
第二回合：男2和女2过河，女1回去
第三回合：男3和女3过河，女3回去
第四回合：女3和女1过河，女1回去
第五回合：女1和男1过河

yinda_peng

wk012233 发表于 2024-3-19 10:55
第一回合：男1和女1过河，男1回去
第二回合：男2和女2过河，女1回去
第三回合：男3和女3过河，女3回去

第三回合，男1，女1，女3在起点