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

yipzx

定义类做了一个，比较好理解递归。为了让初学者看懂，程序没做优化，可能有点啰嗦。结果在立即窗口查看。

1. Option Explicit
   
2. Sub main()
   
3. Dim s As New Scene
   
4. 
   
5.     s.left_bank_monks = 3 'inputbox instead
   
6.     s.left_bank_monsters = 3
   
7.     s.right_bank_monks = 0
   
8.     s.right_bank_monsters = 0
   
9.     s.boat_capacity = 2
   
10.     s.boat_location = "left"
    
11.     s.boat_step = Array()
    
12.    
    
13.     Call monks_vs_monsters(s)
    
14. 
    
15. End Sub
    
16. 
    
17. Sub monks_vs_monsters(current_scene)
    
18.     Dim i As Long, ns
    
19.    
    
20.     With current_scene
    
21.    
    
22.         If .is_done Then
    
23.             Debug.Print .result
    
24.             Exit Sub
    
25.         End If
    
26.         
    
27.         ns = .next_steps
    
28.         For i = LBound(ns) To UBound(ns)
    
29.             Call monks_vs_monsters(.genarate_next_scene(ns(i)))
    
30.         Next i
    
31.         
    
32.     End With
    
33.    
    
34.     Set current_scene = Nothing
    
35.    
    
36. End Sub
    
37. 
    

复制代码

yipzx

昨天少写一初始条件，补上，年纪大了。在立即窗口看答案。答案格式为，过河和尚数-过后妖怪数，每一步后“，”号隔开。最少就4种解法。

1234vba

第一时间收藏帖子。要学习的

香川群子

zopey 发表于 2018-9-5 17:05
'过河方案brr() 有49种,对应返回方案也是49种。

Sub 按钮1_Click()

你这个49方案，是啥意思？

已经脱离题目要求了吧。

再用数学语言描述一下：
起始状态3，3，0，0，要求经过最少步数达到 0，0，3，3状态，
渡河规则为0<x+y<=2 (每次渡河最多2位，最少1位)
另有限制条件 x=0 or  (x>0 and x>=y)  (如果和尚数x不为0时需满足x>=y 即和尚数>=妖怪数)
求不同路径的数量。（过程不同的路径数）

m=3
n=3
时，只有4个不同的最短路径。

香川群子

1234vba 发表于 2018-9-6 08:19
第一时间收藏帖子。要学习的

有人关注，有人想要学习，

那么大家就会讨论下去、逐步揭开知识点。

我会在最后做总结，把递归解题的算法过程交代清楚。

1234vba

香川群子 发表于 2018-9-6 08:29
有人关注，有人想要学习，

那么大家就会讨论下去、逐步揭开知识点。

恩、、

期待老师后面的揭秘

香川群子

yipzx 发表于 2018-9-6 06:43
昨天少写一初始条件，补上，年纪大了。在立即窗口看答案。答案格式为，过河和尚数-过后妖怪数，每一步后“ ...

代码写的很规范。

算法基本没问题了，但是我在检查m=3，n=2时发现，

left-1-1,right-0-1,left-1-1,right-1-0,left-1-1,right-0-1,left-1-0,right-0-1,left-0-2
left-1-1,right-0-1,left-1-1,right-1-0,left-1-1,right-0-1,left-1-1

left-1-1,right-1-0,left-2-0,right-1-0,left-1-1,right-0-1,left-1-0,right-0-1,left-0-2
left-1-1,right-1-0,left-2-0,right-1-0,left-1-1,right-0-1,left-1-1

这4个解，其实上面一个是下面解的冗余步数（可以蓝色一步完成的，却多走了几步）

如果按照最短路径的要求，这是不是只能算2组解？哈哈。

zopey

香川群子 发表于 2018-9-6 08:25
你这个49方案，是啥意思？

已经脱离题目要求了吧。

为了求路径，我想先制作邻接表，如下图（只显示一半）：
按乘船方案的限制 ，m=3 n=3 过河及返回 各有 有49 种可能。

香川群子

zopey 发表于 2018-9-6 09:16
为了求路径，我想先制作邻接表，如下图（只显示一半）：
按乘船方案的限制 ，m=3 n=3 过河及返回 各有  ...

哦，那就是最终路径结果还没整理出来，代码需要继续的意思。

yipzx

香川群子 发表于 2018-9-6 09:11
代码写的很规范。

算法基本没问题了，但是我在检查m=3，n=2时发现，

没错，再加个优化条件，记录最短步数，超过了直接剪枝就可以了。