阿拉伯夫妇过河问题
本帖最后由 yinda_peng 于 2024-3-19 13:34 编辑大概两三天之后会发布答案，如果有鱼油在此之前写出来了，将提前发布答案
写对的鱼油给予评分奖励（非会员优先评鱼币，会员优先评荣誉），不仅写对还给出清晰解答的鱼油将额外给予贡献评分奖励
希望大家尽量自己思考，一道题目，你看答案写和没看答案写是完全不同的感受
有三对夫妻要过河，船最多只能载两人，
由于旧时阿拉伯法律约束，封建思想严重，
要求女子不能在丈夫不在场时与其他男性共处，
如何安排三对夫妇过河？
（记得考虑划船，可以使用编程求解哦）
提示：按男女分类，编程可考虑状态转移
用向量(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} 并用S1(m,n),S2(m,n),...(Sk属于S)表示状态的变化过程，dk(m,n)(dk属于D)表示状态Sk下的过河方案，当k为奇数时，dk表示从起点到对岸，当k为偶数时，表示从对岸到起点。状态转移满足下列关系： Sk+1 = Sk+ (-1)kdk 于是问题归结为：求dk属于D(k = 1,2...)使(Sk属于S)状态按(2.5)式由初始状态S1（3,3）经n步转移到Sn(0,0)的最小值n值。根据上述思路，现在就容易实现在计算机上实现了，如果计算过程出现循环，代表无解。
参考思路已发布 @中英文泡椒 @学习编程中的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对运过去，再回来
完美
歌者文明清理员 发表于 2024-3-16 11:42
三对夫妻为 A1, A2, B1, B2, C1, C2
（1 男 2 女）
7.8.9.检查一下 神佑邻祂 发表于 2024-3-16 11:36
女 男
女1男1
女2男2
正确的 人造人 发表于 2024-3-16 11:52
一对一对往过运么
先把第1对运过去，回来
再把第2对运过去，回来
要考虑划船哦，船只能载两人，谁划船回去，载谁过去，谁下船，没有这么简单滴 yinda_peng 发表于 2024-3-16 11:59
要考虑划船哦，船只能载两人，谁划船回去，载谁过去，谁下船，没有这么简单滴
这你的题目也没说呀
我还以为不算划船的，或者这船是自动的这类的
^_^
人造人 发表于 2024-3-16 12:06
这你的题目也没说呀
我还以为不算划船的，或者这船是自动的这类的
^_^
行吧{:10_262:}我的问题 yinda_peng 发表于 2024-3-16 11:54
7.8.9.检查一下
{:10_291:} 歌者文明清理员 发表于 2024-3-16 16:12
思路没问题，就是后面几步有点多余了。
第7步之后，B2 直接回来带着 A2 过河就可以。
之前那几步所有男性都已经过去了，女性过去自己的丈夫就在，所以直接把女的一个一个带过去就可以。她丈夫肯定在。
而且第8步你括号里面，B2 自己的丈夫不在，和其他男人单独相处了。第7步里 C2 已经带着 B2 过河了，第9步 B1 又带着 B2 过了一次河。
前面还好，后面有点错乱。
本帖最后由 中英文泡椒 于 2024-3-18 17:15 编辑
分为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一起过河 中英文泡椒 发表于 2024-3-18 17:04
分为ABC三对夫妻
1. 丈夫A和丈夫B过河，丈夫B划回来（终点的有丈夫A）
2. 丈夫B和丈夫C过河，丈夫C回来( ...
如果先走两个男，那起点不就已经违反了么 yinda_peng 发表于 2024-3-18 18:47
如果先走两个男，那起点不就已经违反了么
那就先走妻子{:5_109:}
分为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一起过河 第一回合：男1和女1过河，男1回去
第二回合：男2和女2过河，女1回去
第三回合：男3和女3过河，女3回去
第四回合：女3和女1过河，女1回去
第五回合：女1和男1过河
本帖最后由 yinda_peng 于 2024-3-19 12:53 编辑
wk012233 发表于 2024-3-19 10:55
第一回合：男1和女1过河，男1回去
第二回合：男2和女2过河，女1回去
第三回合：男3和女3过河，女3回去
第三回合，男1，女1，女3在起点
页:
[1]