[已解决]从A到F，不能走重复路线，要求输出所有的走法

爱疯

2.rar (7.53 KB, 下载次数: 16)

2016-6-12 11:26 上传

点击文件名下载附件



返回：
ABDF
ABDEF
ABCEF
ABCEDF
ACBDF
ACBDEF
ACEDF
ACEF


请问如题，该怎样来写代码？谢谢！

最佳答案

月排行榜 / 总排行榜

香川群子

2016-6-12 14:23

递归

1. Dim dic, k&, s2$
   
2. Sub test() 'by kagawa 2016/6/12
   
3.     Dim ar, i&, s1$
   
4. 
   
5.     s1 = [a2]: s2 = [b2] '设置起点、终点
   
6.     [d1].CurrentRegion.Offset(1) = "" '清空输出区域
   
7.    
   
8.     ar = [a4].CurrentRegion '读取路径关系表
   
9.     Set dic = CreateObject("Scripting.Dictionary")
   
10.     For i = 2 To UBound(ar)
    
11.         dic(ar(i, 1)) = dic(ar(i, 1)) & "," & ar(i, 2) '路径关系写入字典
    
12.     Next
    
13. 
    
14.     k = 1: Call dg(s1, s1) '调用递归
    
15.     MsgBox k - 1
    
16. End Sub
    
17. 
    
18. Sub dg(s$, t$) 's为历史路径记录，t为当前路径节点
    
19.     Dim sr, i&, t2$
    
20.     sr = Split(dic(t), ",") '读取字典中当前节点的有效子节点路径关系
    
21.     For i = 1 To UBound(sr) '遍历有效子节点
    
22.         t2 = sr(i) '读取子节点
    
23.         If t2 = s2 Then '如果已到达终点
    
24.             k = k + 1: Cells(k, 4) = s & t2: Exit Sub '则输出该路径后结束本次递归
    
25.         Else
    
26.             If InStr(s, t2) = 0 Then Call dg(s & t2, t2) '如果子节点未曾用过则进入下一层递归搜索
    
27.         End If
    
28.     Next
    
29. End Sub
    

复制代码

其中，检查子节点是否已被利用过，这个很关键。 If InStr(s, t2) = 0

跳转到最佳答案楼层

老司机带带我

A B C B D F
A B C B D E F
这两个结果是不是有问题？

爱疯

老司机带带我 发表于 2016-6-12 11:40
A B C B D F
A B C B D E F
这两个结果是不是有问题？

谢谢！！
好像是有问题，可能写错了

蝶·舞

不就2*4吗？

爱疯

蝶·舞 发表于 2016-6-12 12:01
不就2*4吗？

谢谢蝶舞！
我不明白2*4是什么含义，这例子看上去不麻烦，可以数出来，我希望解决办法可以解决更复杂的情况，2*4是否也能解决？

蝶·舞

A是第一梯队
B,C是第二梯队
D,E是第三梯队
F是第四梯队
第一梯队到第二梯队是二种路线
第二梯队到第三梯队是四种路线
第三梯队到第四梯队是二种路线
所以第一梯队到第四梯队一共是2*4*2=16种
但由于第二梯队到第三梯队时，终点是重复二次，所以16/2=8

爱疯

蝶·舞 发表于 2016-6-12 12:16
A是第一梯队
B,C是第二梯队
D,E是第三梯队

5楼意思我明白了，是说明走法的总个数。
假如要输出其中每一种走法，不知会不会很难？是不是能按什么套路来做？已知的条件怎样写在表中更好。。。。。

香川群子

蝶·舞 发表于 2016-6-12 12:16
A是第一梯队
B,C是第二梯队
D,E是第三梯队

你这解释不对啊。

很简单。
第1层 2种分歧 A-B / A-C
第2层 也是各自多2种分歧 B-C/B-D 以及 C-B/C-E
第3层 又是各自多2种分歧 D-E/D-F 以及 E-D/E-F
第4层 只有1种分歧(如果有的话) D-F 以及 E-F  

因此，结果总数=2*2*2*1=8即可。无需考虑除以2

香川群子

爱疯 发表于 2016-6-12 12:34
5楼意思我明白了，是说明走法的总个数。
假如要输出其中每一种走法，不知会不会很难？是不是能按什么套路 ...

【已知的条件怎样写在表中更好】……这个确实是关键。

把问题条件用数学化语言进行表达，是必须的。

我想用列表方式可以。如：

起	终
A	B
A	C
B	C
B	D
C	B
C	E
D	E
D	F
E	D
E	F

这样10条有效线路即可。

估计用递归很容易解决的。

香川群子

递归

1. Dim dic, k&, s2$
   
2. Sub test() 'by kagawa 2016/6/12
   
3.     Dim ar, i&, s1$
   
4. 
   
5.     s1 = [a2]: s2 = [b2] '设置起点、终点
   
6.     [d1].CurrentRegion.Offset(1) = "" '清空输出区域
   
7.    
   
8.     ar = [a4].CurrentRegion '读取路径关系表
   
9.     Set dic = CreateObject("Scripting.Dictionary")
   
10.     For i = 2 To UBound(ar)
    
11.         dic(ar(i, 1)) = dic(ar(i, 1)) & "," & ar(i, 2) '路径关系写入字典
    
12.     Next
    
13. 
    
14.     k = 1: Call dg(s1, s1) '调用递归
    
15.     MsgBox k - 1
    
16. End Sub
    
17. 
    
18. Sub dg(s$, t$) 's为历史路径记录，t为当前路径节点
    
19.     Dim sr, i&, t2$
    
20.     sr = Split(dic(t), ",") '读取字典中当前节点的有效子节点路径关系
    
21.     For i = 1 To UBound(sr) '遍历有效子节点
    
22.         t2 = sr(i) '读取子节点
    
23.         If t2 = s2 Then '如果已到达终点
    
24.             k = k + 1: Cells(k, 4) = s & t2: Exit Sub '则输出该路径后结束本次递归
    
25.         Else
    
26.             If InStr(s, t2) = 0 Then Call dg(s & t2, t2) '如果子节点未曾用过则进入下一层递归搜索
    
27.         End If
    
28.     Next
    
29. End Sub
    

复制代码

其中，检查子节点是否已被利用过，这个很关键。 If InStr(s, t2) = 0