[开_86] 比速度,看谁的程序更快.

香川群子

就用这个算法，已经可以轻松地计算到160/170这样子了……而以前的代码早已死机。

当然，这个算法还有两大问题：

第一，子过程算法应该可以提速。→目前的dg71算法应该进一步套用，以便进一步提高速度。

第二，对随机数序列的适用研究。


求和速度如下：

求和值  预置时间   计算时间  计算结果数k
10        0.000s        0.000s        10
20        0.000s        0.000s        64
30        0.000s        0.000s        296
40        0.000s        0.016s        1113
50        0.016s        0.016s        3658
60        0.016s        0.016s        10880
70        0.031s        0.063s        29927
80        0.047s        0.141s        77312
90        0.094s        0.281s        189586
100        0.188s        0.703s        444793  → 参考，以前代码的速度最快也要2秒多（我的慢机器上）一般要3秒多。
110        0.438s        1.422s        1004544
120        0.703s        3.109s        2194432
130        1.250s        6.188s        4654670
140        2.422s        12.500s        9617150
150        4.547s        25.016s        19406016
160        7.125s        49.906s        38328320
170        11.328s        96.641s        74236384

灰袍法师

香川群子 发表于 2012-10-14 13:30
经过算法上的进一步研究，速度又有了突破……

1-100的100个连续自然数，求目标和=100时，

不能计算随机的自然数序列，只能计算从1开始递增的自然数序列。
========================================
这。。。。。。等于毫无用处吖。
还不如就用之前的，正反序各算一次的话，就跟你说的一样，适用性很好，可以求解论坛出现过的所有数据（彭希仁的程序只能求解大概80%）

不过你预置一些已知和，然后计算它们的补数，这个思路是很好的。
实际上 求解子集和问题，有一个叫做“两表法”的算法
就是先算出两堆和值，然后互相查找相加等于指定和值的组合。

香川群子

灰袍法师 发表于 2012-10-14 16:53
不能计算随机的自然数序列，只能计算从1开始递增的自然数序列。
===================================== ...

随机数序列的解，肯定是可以做到的。

我已经初步试了一下，是可以的。

具体说，我原来是循环 for i = 1 to m，即循环1-100

现在只要改成循环 for i = 1 to sj(m,1)， 即循环1-第100个数的实际值就可以解决了。



不过还有一些bug要处理，过程中间的比对方式要调整一下。

香川群子

具有通用性的代码也调试成功了。

不过，很显然，本代码算法只是特别适合于1-m的连续自然数计算。（因为每一个中间值都是连续存在的）
而对于其它间隔>1或任意随机间隔的序列求和来说，则无法体现速度优势，甚至于变慢了……。


因此，最后的结论是：

如果仅仅用来计算1-m的连续自然数求和，那么【数组预置结果算法】速度是最酷的，目前没有更快的算法。

而如果真正用来求各种任意序列数的定值和，则【倒序差额+末位搜寻+累计和剪枝的算法】是目前最快的、适用性最强的算法代码。

1. Dim sj, jg(), m%, k, h%
   
2. Sub kagawa_5() '递归组合求和-5 【最优算法最终版】
   
3.     '【倒序差额+末位搜寻+次位超r剪枝+不足累计和剪枝 的算法】
   
4.     tms = Timer
   
5.     h = [b1]
   
6.     m = [a1].End(4).Row: ' sj0 = [a1].Resize(m)
   
7.     [a1].Resize(m).Sort [a1], 1, , , 2 '如果原始数据乱序则先升序排序
   
8.     sj = [a1].Resize(m, 2): ' [a1].Resize(m) = sj0 '排序处理后原始数据恢复原状
   
9.    
   
10.     sj(1, 2) = sj(1, 1)
    
11.     For i = 2 To m
    
12.         sj(i, 2) = sj(i - 1, 2) + sj(i, 1)
    
13.     Next
    
14.    
    
15.     ReDim jg(65536, 0)
    
16.     Open "D:\Backup\我的文档\kagawa-5.txt" For Output As #1
    
17.     k = 0 'tms = Timer
    
18.    
    
19.     Call dgH5(h, "", m + 1)
    
20.    
    
21.     Close #1
    
22.     MsgBox "Result: " & k & "/ Time: " & Format(Timer - tms, "0.000s")
    
23.     If k > 0 And k < 65536 Then [h:h] = "": [h1].Resize(k) = jg
    
24. End Sub
    
25. Sub dgH5(r%, s$, i%)
    
26.     Dim j%
    
27.    
    
28.     For j = 1 To i - 1 '【末位搜寻】
    
29.         If r = sj(j, 1) Then
    
30.             If k < 65536 Then jg(k, 0) = s & "+" & r
    
31.             Print #1, s & "+" & r
    
32.             k = k + 1
    
33.             Exit For
    
34.         ElseIf r < sj(j, 1) Then
    
35.             j = j + 1 '【次位超r剪枝】
    
36.             Exit For
    
37.         End If
    
38.     Next
    
39.         
    
40.     For j = j - 1 To 2 Step -1
    
41.         If r > sj(j, 2) Then
    
42.             Exit For '【不足累计和剪枝】
    
43.         Else
    
44.             Call dgH5(r - sj(j, 1), s & "+" & sj(j, 1), j) '【倒序差额递归计算】
    
45.         End If
    
46.     Next
    
47. End Sub

复制代码

漫天星光

换换数据，就死机了

香川群子

漫天星光 发表于 2012-10-14 20:18
换换数据，就死机了

代码不是万能的。

换换数据是啥意思，怎么换的，能说明一下么。

你的要求和目的是什么？

灰袍法师

香川群子 发表于 2012-10-15 09:36
代码不是万能的。

换换数据是啥意思，怎么换的，能说明一下么。

发帖数＝1的新人，理他干嘛？
你的程序唯一弱点是：指定和值等于总和的1/3以上，而且无解的时候。。。。。。
运行有解的实际数据，效果是非常好的。

/fendoude/zt

谢谢 帮我解决了个问题

zyhui1961

很好，做个记号!

woyls51

谢谢分享!!












高技术
YY