从一组数字中任意组合N个数字，使之和在某个数值范围
本帖最后由 afan 于 2012-3-15 09:48 编辑比如有如下15个数，任意N个数组合，使之和在 102到105 之间（102>和值<105）的所有可能的组合或任意一个组合(此为延伸问题)：Dim $aArray =
本人菜鸟，运算耗时2.7xx 秒。请教各位高手有无高效的方法。
以下为本人写的代码，为不影响各位的思维，暂隐藏。
**** Hidden Message ***** 学习一下...... 还是先看看原麻 不行，想不出来，看一下！ 学习下，，好知识 楼主那么晚还不睡觉！还在研究！真是佩服！
不过我真的想不出来！还是看看源码先吧！ 不知道怎么弄，这属于“智能”问题，我却是愚蠢的。 不知道怎么弄，这属于“智能”问题，我却是愚蠢的。 ??????????????? 各位就别谦虚了，我这不是限制题（限制的话我也解不出~~），什么都可以上~:face (20): 本人X鸟+懒鸟,本有个构思,却懒于下手!只好先睹AFAN大大代码了! 本帖最后由 sanmoking 于 2010-1-25 18:57 编辑
0.3秒快不？
代码隐藏，afan要多多加分啊。。。
**** Hidden Message *****
上边的代码有问题,
如果数组最后边有0,1之类的数在得到51+8+37+7=103结果之后就不会再往下计算了,
比如51+8+37+7+1=104,更不会有51+8+37+7+1+0=104，现更正如下:
#include <Array.au3>
Dim $aArray = ;~ _ArraySort($aArray)
GUICreate("", 400, 620)
GUICtrlCreateEdit("", 10, 10, 380, 600)
$coo = 0 ;存储计算次数
$com = 0;存储正确结果数量
$num = UBound($aArray) - 1 ;计算数组最后一位
$begin = TimerInit();开始计时
mimi(0, 0, "")
$dif = TimerDiff($begin);结束记时
GUICtrlSetData(-1, "计算耗时: " & $dif&@CRLF,1)
GUICtrlSetData(-1, "总计计算了"&$coo&"次加法运算"&@CRLF,1)
GUICtrlSetData(-1, "正确结果有"&$com&"种算法"&@CRLF,1)
GUISetState()
While GUIGetMsg() + 3
WEnd
Func mimi($k, $resd, $txtd)
For $i = $k To $num
$resx = $resd + $aArray[$i]
$txtx = $txtd & $aArray[$i] & "+"
$coo += 1
If $resx <= 102 Then
mimi($i + 1, $resx, $txtx)
ElseIf $resx > 102 And $resx < 105 Then
GUICtrlSetData(-1, StringReplace($txtx & "=", "+=", "=") & $resx&@CRLF,1)
$com += 1
;~ --------------------------------下边这句必须加上的-----------------------
mimi($i + 1, $resx, $txtx)
;~ -------------------------------------------------------------------------
EndIf
Next
EndFunc ;==>mimi
;~ 之所以犯错,就是因为afan的题目直接是103,104两个结果,这两个相差为1,并且它提供的数组里面正好没有1,所以测试一下结果对上46就以为通过了
;~ 不加上面这句,如果得到一个51+13+2+19+11+7=103的结果,1在7之前,可以把1算上,1在7之后,就不会去计算了
;~ 假如题目要求是100,110之间的结果,那么比如51+13+2+19+11+5+7=108这样的结果就不会得到,
;~ 只会得到51+13+2+19+11+5=101,符合结果范围,就不在去加后边的7了
;~ 本代码上面的数组最后添加一个0,就会发现结果是92个,因为添加了一个0,所以46个结果每个加上0,还是符合的,所以结果翻了一倍变成92个了. 本帖最后由 sanmoking 于 2010-1-25 18:49 编辑
楼上的代码，我直接双击au3运行，结果是
计算耗时: 21.4052344641568
总计计算了2651次加法运算
正确结果有46种算法
编译成exe之后，
计算耗时: 21.5873805190324
总计计算了2651次加法运算
正确结果有46种算法
差不多时间
afan的代码我没都运行成功，也没仔细看afan的原理，应该跟我的不一样。。从排序上就能看出来。
另外验证有单一数字符合102-105的和0的情况下的计算结果.
如下：
Dim $aArray =
结果：
51+8+13+2+0+19+11=104
51+8+13+2+0+7+22=103
51+8+13+2+0+7+22+1=104
51+8+13+2+19+11=104
51+8+13+2+7+22=103
51+8+13+2+7+22+1=104
51+8+13+0+19+11+1=103
51+8+13+19+11+1=103
51+8+2+0+19+22+1=103
51+8+2+19+22+1=103
51+8+37+0+7=103
51+8+37+0+7+1=104
51+8+37+7=103
51+8+37+7+1=104
51+8+0+7+38=104
51+8+7+38=104
51+13+2+37=103
51+13+2+37+0=103
51+13+2+37+0+1=104
51+13+2+37+1=104
51+13+2+0+19+11+7=103
51+13+2+0+19+11+7+1=104
51+13+2+0+38=104
51+13+2+19+11+7=103
51+13+2+19+11+7+1=104
51+13+2+38=104
51+13+0+11+7+22=104
51+13+0+38+1=103
51+13+11+7+22=104
51+13+38+1=103
51+2+0+11+38+1=103
51+2+11+38+1=103
51+52=103
51+52+0=103
51+52+0+1=104
51+52+1=104
51+0+19+11+22=103
51+0+19+11+22+1=104
51+19+11+22=103
51+19+11+22+1=104
8+13+2+52+0+7+22=104
8+13+2+52+7+22=104
8+13+2+61+0+19=103
8+13+2+61+0+19+1=104
8+13+2+61+0+11+7+1=103
8+13+2+61+19=103
8+13+2+61+19+1=104
8+13+2+61+11+7+1=103
8+13+2+0+19+62=104
8+13+2+0+19+22+38+1=103
8+13+2+0+11+7+62=103
8+13+2+0+11+7+62+1=104
8+13+2+0+79+1=103
8+13+2+19+62=104
8+13+2+19+22+38+1=103
8+13+2+11+7+62=103
8+13+2+11+7+62+1=104
8+13+2+79+1=103
8+13+52+0+19+11=103
8+13+52+0+19+11+1=104
8+13+52+0+7+22+1=103
8+13+52+19+11=103
8+13+52+19+11+1=104
8+13+52+7+22+1=103
8+13+61+0+22=104
8+13+61+22=104
8+13+37+0+7+38=103
8+13+37+0+7+38+1=104
8+13+37+7+38=103
8+13+37+7+38+1=104
8+13+0+19+62+1=103
8+13+19+62+1=103
8+2+52+0+19+22=103
8+2+52+0+19+22+1=104
8+2+52+0+11+7+22+1=103
8+2+52+19+22=103
8+2+52+19+22+1=104
8+2+52+11+7+22+1=103
8+2+61+0+11+22=104
8+2+61+11+22=104
8+2+37+0+19+38=104
8+2+37+0+11+7+38=103
8+2+37+0+11+7+38+1=104
8+2+37+19+38=104
8+2+37+11+7+38=103
8+2+37+11+7+38+1=104
8+2+0+85+7+1=103
8+2+0+19+11+62+1=103
8+2+85+7+1=103
8+2+19+11+62+1=103
8+52+37+0+7=104
8+52+37+7=104
8+61+0+11+22+1=103
8+61+11+22+1=103
8+37+0+19+11+7+22=104
8+37+0+19+38+1=103
8+37+19+11+7+22=104
8+37+19+38+1=103
8+0+85+11=104
8+0+11+62+22=103
8+0+11+62+22+1=104
8+85+11=104
8+11+62+22=103
8+11+62+22+1=104
13+2+52+37=104
13+2+52+37+0=104
13+2+52+0+19+11+7=104
13+2+52+19+11+7=104
13+2+61+0+19+7+1=103
13+2+61+19+7+1=103
13+2+37+0+19+11+22=104
13+2+37+19+11+22=104
13+2+0+19+7+62=103
13+2+0+19+7+62+1=104
13+2+19+7+62=103
13+2+19+7+62+1=104
13+52+37+0+1=103
13+52+37+1=103
13+52+0+19+11+7+1=103
13+52+0+38=103
13+52+0+38+1=104
13+52+19+11+7+1=103
13+52+38=103
13+52+38+1=104
13+61+0+19+11=104
13+61+0+7+22=103
13+61+0+7+22+1=104
13+61+19+11=104
13+61+7+22=103
13+61+7+22+1=104
13+37+0+19+11+22+1=103
13+37+19+11+22+1=103
13+0+19+11+22+38=103
13+0+19+11+22+38+1=104
13+0+11+79=103
13+0+11+79+1=104
13+0+7+62+22=104
13+19+11+22+38=103
13+19+11+22+38+1=104
13+11+79=103
13+11+79+1=104
13+7+62+22=104
2+52+37+0+11+1=103
2+52+37+11+1=103
2+52+0+19+7+22+1=103
2+52+0+11+38=103
2+52+0+11+38+1=104
2+52+19+7+22+1=103
2+52+11+38=103
2+52+11+38+1=104
2+61+0+19+22=104
2+61+0+11+7+22=103
2+61+0+11+7+22+1=104
2+61+19+22=104
2+61+11+7+22=103
2+61+11+7+22+1=104
2+37+0+19+7+38=103
2+37+0+19+7+38+1=104
2+37+19+7+38=103
2+37+19+7+38+1=104
2+0+11+7+62+22=104
2+0+62+38+1=103
2+0+22+79=103
2+0+22+79+1=104
2+11+7+62+22=104
2+62+38+1=103
2+22+79=103
2+22+79+1=104
52+0+19+11+22=104
52+19+11+22=104
61+0+19+22+1=103
61+19+22+1=103
37+0+7+22+38=104
37+7+22+38=104
0+85+19=104
0+85+11+7=103
0+85+11+7+1=104
0+103=103
0+103+1=104
0+19+62+22=103
0+19+62+22+1=104
0+11+7+62+22+1=103
0+104=104
85+19=104
85+11+7=103
85+11+7+1=104
103=103
103+1=104
19+62+22=103
19+62+22+1=104
11+7+62+22+1=103
104=104
计算耗时: 81.7307786324798
总计计算了10338次加法运算
正确结果有192种算法
回复 12# sanmoking
高手就是高手，学习了~！ 先看一下，学习学习