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

香川群子

ykqrs 发表于 2018-9-4 14:47
第一步：两个妖过去，下一个妖，留一个妖开船返回，3-1；1；0-1
第二步：再上一个妖，下一个妖，留一个妖 ...

自定规则，是山不动，我就走过去的意思吗？

那还不如直接开一趟，上面一个和尚一个妖怪，水里2个和尚两个妖怪扶着船游泳游过去……

……
此题目只是锻炼编程算法能力，不是用来脑筋急转弯的。

香川群子

excelvlookup 发表于 2018-9-2 20:27
为什么不可以这样
1、送2个妖怪过去，空船返回。3、1；0、2
2、送2个和尚过去，空船返回。1、1；2、2

【有个类似小学数学题，答案允许空船返回...】

小学生简化版？

那还可以继续简化，让幼儿园水平也能回答。

zopey

和尚数、妖怪数、过河和尚数、过河妖怪数，
1、起始状态是： 3、3/0、0
2、最终状态是： 0、0/3、3
可能状态的总数是 4*4=16 。

再考虑动作，可能性如下：
2和尚过河；

1和尚单独过河；

1和尚1妖怪过河；

1妖怪单独过河；

2妖怪过河；


2和尚返回；

1和尚单独返回；

1和尚1妖怪返回；

1妖怪单独返回；

2妖怪返回。

kinlog

是这样吗？

香川群子

zopey 发表于 2018-9-4 16:15
和尚数、妖怪数、过河和尚数、过河妖怪数，
1、起始状态是： 3、3/0、0
2、最终状态是： 0、0/3、3

很好！

第一步，就是状态分析，起始状态和结束状态是什么样子，以及如何描述！

第二步，就是实现过程（改变状态的方法）的分析，对于计算机来说，就是要确定规则，然后穷举得到各种可能的方法。

规则为：
一、1只小船，每次载1-2位，不能空船。
二、和尚或妖怪，有2种组合，每次0-2位（3种状态可能）。

根据二，因为是3个状态的2种组合，所以最大可能性=3^2=9种，
再由一限制排除，所以只剩下5种可能。

去和返回，又是二种状态，那么就有了10种可能。
这里，对算法来说，就产生了第一个分歧：是把渡河过程只看做5种可能，另外考虑去和返的状态；
还是直接用10种渡河过程去处理数据？

哪一种的算法代码实现更简洁，哪一种的计算效率更好？

香川群子

zopey 发表于 2018-9-4 16:15
和尚数、妖怪数、过河和尚数、过河妖怪数，
1、起始状态是： 3、3/0、0
2、最终状态是： 0、0/3、3

一共只有5种符合规则的过河方式：

组合	和尚数	妖怪数	总数	判断
1	0	0	0	=0 NG
2	0	1	1	OK
3	0	2	2	OK
4	1	0	1	OK
5	1	1	2	OK
6	1	2	3	>2 NG
7	2	0	2	OK
8	2	1	3	>2 NG
9	2	2	4	>2 NG

香川群子

所以，第一步就是根据渡河规则，列出5种渡河方式。

写成代码很容易，2层循环，最简可以写成4行代码Debug.Print得到如下结果：

1  0  1
2  0  2
3  1  0
4  1  1
5  2  0

zopey

香川群子 发表于 2018-9-5 09:10
很好！

第一步，就是状态分析，起始状态和结束状态是什么样子，以及如何描述！

假设：和尚=m，妖怪=n，
因为河岸A与对河岸B 是互补的关系，河岸A 有1个和尚，对河岸B 就有 m-1个和尚，
只要记录某一边的 河岸情况 就能表达 完整的状态。

zopey

'过河方案brr() 有49种,对应返回方案也是49种。

Sub 按钮1_Click()
m = 3
n = 3
k0 = (m + 1) * (n + 1)

Dim arr()
ReDim arr(1 To k0, 1 To 2)

For i = 0 To m
For j = 0 To n
    k = k + 1
    arr(k, 1) = i
    arr(k, 2) = j
Next
Next

Dim brr()
ReDim brr(1 To 999, 1 To 1)
For i = 1 To k0 - 1
For j = i + 1 To k0
    x1 = arr(j, 1) - arr(i, 1)
    x2 = arr(j, 2) - arr(i, 2)
    If x2 >= 0 And x1 <= 2 - x2 Then
       k1 = k1 + 1
       brr(k1, 1) = arr(i, 1) & arr(i, 2) & "++" & arr(j, 1) & arr(j, 2)
    End If
Next
Next

[a1].Resize(999, 1) = brr
End Sub

godhands

如果考虑通用情况，船的载重数量(2)是否也应该变成能够设置的变量呢？