出个算法题，大家练练手【3个和尚和3个妖怪过河】

香川群子

wuliaolang 发表于 2018-9-6 21:32
试着做了一下，把自己做晕了，估计漏洞百出
一开始想起来前几年考一建时学的网络计划，和关键线路计算很类 ...

挺好，把渡船方向考虑进去了，一般就不会错了。

没有使用字典，用字符串记录路径节点，然后用Instr检查是否路径有重复。这个也可以。

缺点是，得到的路径，有些不是最短路径（中间过程和别的解有重复）
这是因为，你的路径检查，只是本次递归计算的防止路径重复，无法比较所有组合解。
举例，如果m=3，n=2，你会得到16各解，其中有4个是存在路径冗余（达到某个状态时，走了更多步数）

yipzx

香川群子 发表于 2018-9-7 08:27
深度搜索、和 广度搜索 的递归代码，我都写成功了。计算结果一致。

计算过程不同，但是剪枝方式基本相 ...

给出通解后，建议再加一个条件，比较好玩，也是在广度搜索上进一步的一个经典的算法。题目为，如果和尚和妖怪数量一致时，消耗能量，能量以单位时间记，一次过河为一个单位时间。比如第一次过河，一个妖怪一个和尚过河，船上和岸上和尚都等于妖怪数，那么消耗3个能量。求最小消耗能量数，及路径

wuliaolang

香川群子 发表于 2018-9-7 11:11
挺好，把渡船方向考虑进去了，一般就不会错了。

没有使用字典，用字符串记录路径节点，然后用Instr检 ...

想了一个方法，到达终点后在返回过程中，字典记录每个节点的步数和它的上一个节点，步数相同的上一个节点连接，步数比之前少的替换掉，步数多的不做处理。这样历遍一次后字典里就是每个走得通的节点，和到达它的最短步数的上一个节点，再把结果循环输出。比如，3个和尚3个妖怪，就是有两个节点上有两个步数相同的上一节点，所以结果是2X2个。试着写了一下，写到一半感觉太麻烦了，还是坐等高手的作品学习学习

lsdongjh

思路上，结构体的设想：

wuliaolang

我把想法做个图，这样比较清晰

lsdongjh

lsdongjh 发表于 2018-9-7 14:17
思路上，结构体的设想：

在这个结构的基础上，加个动态数组，保存每一次变动的情况，如果走不通，索引向后回退，走通了，将这个动态数组的 内容合并一下就是 一次成功的转移啊

zopey

香川群子 发表于 2018-9-2 10:05
算法要求是通解，小船固定一次只能载2位，但和尚数m和妖怪数n不确定时，都要能解出答案。
（即，和尚和妖 ...

m=3 n=2  时， 黄色格子为和尚、妖怪渡河 必经路径。



m=4  n=4 无解

zopey

完整代码

渡河3.zip (24.22 KB, 下载次数: 17)

2018-9-7 16:48 上传

点击文件名下载附件

excelvlookup

说的太复杂了，我对此题的理解是从A把人运到B，满足最短。只需考虑以下条件
如不考虑别的条件：A到B两人，B到A一人 。最短
加上僧大于等于妖的情况，就可能出现A到B一人或B到A两人，则最短加一。
当无法满足A到B两人，B到A一人时，无解。因为船上始终为两人或始终为一人，总量上看是没人过河的

excelvlookup

另外，不必考虑船上的僧妖情况，因为只能两人，三种情况僧2妖0，妖2僧0，僧1妖1，均符合规则