求1-n个数总和符合目标值的 高效【组合递归方法】

gjj136138139

山菊花 发表于 2012-8-21 20:31
推荐两个帖子：
《归去来兮－－漫谈递归》----qee用

谢谢，递归好象在树型目录结构中用的比较多。

windimi007

一定得抽时间慢慢研究一下香川老师的大作！{:soso__7695307093266004165_1:}

clxka

太牛了，谢谢！！！

xsy我可以很好

佩服{:soso_e179:}

香川群子

递归求和方法改进，提前计算末位值并检查原始数据数组中是否存在有效末位值，
这样大幅减少了递归计算量。

尤其是，计算1-n的连续自然数对象的组合求和时速度最快。

1. Dim sj, d, jg(), m%, k, h%, cnt
   
2. Sub kagawa_dgH2() '递归组合求和-2
   
3.     tms = Timer
   
4.     m = [a1].End(4).Row
   
5.     h = [b1]
   
6.     sj0 = [a1].Resize(m): [a1].Resize(m).Sort [a1], 1, , , 2 '如果原始数据乱序则先升序排序
   
7.     sj = [a1].Resize(m)
   
8.     [a1].Resize(m) = sj0 '排序处理后原始数据恢复原状
   
9.    
   
10.     ReDim jg(65536, 0)
    
11.     k = 0: cnt = 0
    
12.    
    
13. '    Open "D:\Result.txt" For Output As #1
    
14. '    Open "D:\Documents\Result.txt" For Output As #1
    
15.     Open "D:\Backup\我的文档\Result.txt" For Output As #1
    
16.     '输出结果到记事本文件，地址可以自己修改
    
17. 
    
18.     Print #1, m & " / " & h
    
19.    
    
20.     Call dgH2("", 0, 0, 0)
    
21.    
    
22.     Print #1, "Result: " & k & "/ Calc " & cnt & "/ Time: " & Format(Timer - tms, "0.000s")
    
23.     Close #1
    
24. 
    
25.     If k < 65536 Then [d1].CurrentRegion = "": [d1].Resize(k) = jg
    
26.     MsgBox "Result: " & k & "/ Calc " & cnt & " Time: " & Format(Timer - tms, "0.000s")
    
27. End Sub
    
28. 
    
29. Sub dgH2(s$, r, i%, t%)
    
30.     Dim j%
    
31.     cnt = cnt + 1
    
32.    
    
33.     x = h - r
    
34.     If x >= sj(i + 1, 1) Then
    
35.         For j = i + 1 To m
    
36.             If x = sj(j, 1) Then
    
37.                 If k < 65536 Then jg(k, 0) = s & "+" & x
    
38.                 Print #1, s & "+" & x
    
39.                 k = k + 1
    
40.                 If k Mod 10000 = 0 Then Application.StatusBar = k & "/" & s
    
41.                 Exit For
    
42.             ElseIf x < sj(j, 1) Then
    
43.                 Exit For
    
44.             End If
    
45.         Next
    
46.     End If
    
47.    
    
48.     For j = i + 1 To m - 1
    
49.         If x - sj(j, 1) < sj(j + 1, 1) Then
    
50.             Exit Sub
    
51.         Else
    
52.             Call dgH2(s & "+" & sj(j, 1), r + sj(j, 1), j, t + 1)
    
53.         End If
    
54.     Next j
    
55. End Sub

复制代码

guzhen9315

优秀作品{:soso_e163:}

xuwenning

收藏了.....

谢谢分享

vbaplus

香川大妹子是个递归控啊
有个地方有点疑问：
If t = n Then Exit Sub 'n>m → go on 当n参数>m时应该继续，而n在1-m之间时因为t已经满足抽取个数则可退出递归进程。
t=n 只是判断本次结果的抽取数已经达到了设定的n值的个数，如果此时退出递归的话？那么后续结果怎么出来？ 就这里没看明白！难道退出递归后，后面还能继续？我没看出来哦

香川群子

vbaplus 发表于 2013-1-13 21:06
香川大妹子是个递归控啊
有个地方有点疑问：
If t = n Then Exit Sub 'n>m → go on 当n参数>m时应该继续 ...

如果有设定个数要求n时，当t=n时即可剪枝退出。
因为以后的计算结果，必定是t>n了。

至于其余符合t=n的组合，不会被忽略……
因为其它的组合计算只要是t<n的组合，还在继续。

这个本来就是递归计算过程的特点。
即每次剪枝结束时，仅仅是终止了这一个枝节的无效计算，
其余的枝节仍然会被遍历计算，直到符合剪枝条件是结束。

vbaplus

香川群子 发表于 2013-1-13 23:16
如果有设定个数要求n时，当t=n时即可剪枝退出。
因为以后的计算结果，必定是t>n了。

恩，通过单步运行，发现了这个特点~
也就是说，只有当一个递归过程完整的执行完毕后，这个过程中产生的一切变化才能生效，如果中途退出的话，那所产生的一切变化都将恢复到上一次完整执行完毕时的状态，但你又把这个递归巧妙地放在循环里面，可以通过循环记数来记录原始数据的取值位置，当循环完成后还没有找到满足要求的组合的话，指针位置会从第n个位置退回到第n-1个位置，再从第n-1位置开始在原始数据中重新取较新值（排序后，也就是较大的值），然后再到第n个位置，依次再次取值，直到循环结束，指针位置再次退回到n-1个位置，再次从n-1位置开始重新取更新的值 （也就是更大的值），直到n-1取到原始数据的最后一个值，而n位置没有值可取时，这时指针退回到n-3的位置，依次重复上述过程，直到找到满足要求时再记录到结果数组中，无论找到了还是找不到，递归过程始终在按原始逻辑继续着，直到第一个位置在原始数据中找到最后一个数，后面的所有位置都无数可找的情况时才结束所有递归，程序执行完毕。

不知道你有没有耐心看我这么啰嗦的表述。也不知道我的上述理解是不是正确的~

说白了，这个程序的每一次递归过程都在内存中保存有记录，如果在寻找第n个值时，在循环结束之前，只是n的指针t返回，但循环变量还在增加（也就是还在经排序后的原始数据中向后找），如果循环结束了（也就是在经排序后的原始数据找到最后一个数），这时n的指针不是像之前那样返回到5（如果n=6的话），而是退回到第n-1位置的指针（如果n=6的话，这时n-1的指针就是指向固定位置4,开始尝试寻找5的数据，而不是在循环结束之前一直在找的第6个位置）。

整个循环尝试的过程，就是在内存中取舍的问题~  

虽然说了这么多，但是要花时间再研究研究，因为我觉得你这个递归比一般的递归处理得要巧妙，对于循环结束后，返回到上一个位置查找的执行问题还不是很明白...