Board logo

标题: 批处理从一组数字中取任意个数字之和在一个数值范围内 [打印本页]

作者: caruko    时间: 2011-5-2 21:34     标题: 批处理从一组数字中取任意个数字之和在一个数值范围内

假如有这么一组数字
{51, 8, 13, 2, 52, 61, 37, 85, 19, 11, 7, 62, 22, 38, 79}
使其中N个数字的和sum满足  102<sum<105
并打印出来。
好吧,好像难度过高,那么改为可以支持<=40个数字的组合,每个数字<100。

结果如下:

作者: caruko    时间: 2011-5-6 19:21

算了,我自己放一组代码吧。
  1. @ECHO OFF&SETLOCAL ENABLEDELAYEDEXPANSION
  2. set "sz=51, 8, 13, 2, 52, 61, 37, 85, 19, 11, 7, 62, 22, 38, 79"
  3. for %%i in (!sz!) do (
  4.       set "array=_%%i_ !array!"
  5.       for %%j in (!array!) do (
  6.           for /f "delims=_" %%k in ("%%j") do (
  7.               if %%i gtr %%k (
  8.                   set "array=!array:_%%i_=#!"
  9.                   set "array=!array:_%%k_=_%%i_!"
  10.                   set "array=!array:#=_%%k_!"
  11.               )
  12.            )
  13.       )
  14. )
  15. set "array=!array:_=!"&for %%i in (!array!) do (
  16.       if %%i lss 58 (
  17.           set /a n+=1
  18.           set "min_!n!=%%i"
  19.       ) else (
  20.           set "_max=!_max! %%i"
  21.       )
  22. )
  23. for %%i in (0 !_max!) do (
  24.     call :loop %%i !n!
  25. )
  26. goto :eof
  27. :loop [next] [cut]
  28. for /l %%n in (%2,-1,1) do (
  29.     set str=%1+!min_%%n!
  30.     if %1 equ 0 set str=!min_%%n!
  31.     set /a v=!str!
  32.     if !v! lss 105 if !v! gtr 102 echo,!str!=!v!
  33.     if !v! lss 103 (
  34.             set /a cut=%%n-1
  35.             call :loop !str! !cut!
  36.      )
  37. )
复制代码

作者: wankoilz    时间: 2011-5-6 20:30

本帖最后由 wankoilz 于 2011-5-17 14:33 编辑

楼主能不能说说大致思路,看代码有点累
我来一个比较笨的方法:
将这15个数字分成两组,小于等于51的10个数字为一组,大于51的5个数字为一组。
求出前一组10个数字的所有组合的和,找出符合102<sum<105 组合。
后一组的5个数中最小的也是52,所以任何一个符合102<sum<105 的组合都只可能有该分组中的一个数字。
于是把这5个数分别和“前10个数字的所有组合(上一步已保存)”进行组合,找出符合102<sum<105的就行了。

这方法已经近似穷举了,幸好大于等于52的数字有5个,而使得前面只需要找出10个数字的组合。要如果直接求15个数字的所有组合的话就不知要等到猴年马月了!
  1. @echo off&setlocal enabledelayedexpansion
  2. set str=8, 13, 2,  37, 19, 11, 7,  22, 38
  3. set _51=ok
  4. for %%a in (%str%) do (
  5.     for /f "delims=_=" %%b in ('set _') do (
  6.         set/a sum=%%b+%%a
  7.         if !sum! gtr 102 if !sum! lss 105 echo %%b+%%a=!sum!
  8.         if !sum! lss 104 set _%%b+%%a=ok
  9.     )
  10. set _%%a=ok
  11. )
  12. rem 将后5个数字分别与前面所有组合相组合,并求和判断
  13. for %%a in (52, 61,62, 79, 85) do (
  14.     for /f "delims=_=" %%b in ('set _') do (
  15.         set/a sum=%%b+%%a
  16.         if !sum! gtr 102 if !sum! lss 105 echo %%b+%%a=!sum!
  17. ))
  18. pause
复制代码

作者: caruko    时间: 2011-5-7 23:03

楼上说的没错,将(最好是53) 作为分界线,可以减少很多计算。
我说说我的算法吧

1:将数字排序,从小到大。
2:分成2个数字组合,>=53的 和 <53的,才发现我写成了58 =.=。
3:从大到小,循环<53的数字组合,递归调用。每循环到一个数字时,计算当前SUM,如果102<sum<105,则输出。如果<103则递归调用余下的数字。

比如 54321 的数字串,循环到5的时候,下一次就循环4321字串,计算5+4的值,再下一次循环321,计算5+4+3。
这主要是为了防止重复。
因为当计算5+3的时候,就不用再计算5+3+4了,直接5+3+2。
以此类推。 如果当前SUM>104,那么则轮空。

其实从小到大循环是最好的,当较小的数的SUM>104时,后面较大的数就可以不用参与计算,跳过循环了,但批处理的跳出机制问题没有采用。
作者: wankoilz    时间: 2011-5-7 23:31

楼主是说>=52吧?
看来思路是大致相同的,主要还是求组合的问题。不过用批处理实现递归,感觉call太多,是不是会影响效率(当然我的代码效率也不见得高)
作者: powerbat    时间: 2011-5-8 11:20

来一个穷举法
  1. @echo off
  2. setlocal enableDelayedExpansion
  3. set "arr=51, 8, 13, 2, 52, 61, 37, 85, 19, 11, 7, 62, 22, 38, 79"
  4. set /a range1=102, range2=105
  5. for %%a in (%arr%) do set /a num+=1 & set a[!num!]=%%a
  6. rem 冒泡排序
  7. for /l %%i in (1 1 %num%) do (
  8.     set /a start = %%i + 1
  9.     for /l %%j in (!start! 1 %num%) do if !a[%%i]! gtr !a[%%j]! (
  10.         set tmp=!a[%%i]!
  11.         set a[%%i]=!a[%%j]!
  12.         set a[%%j]=!tmp!
  13.     )
  14. )
  15. for /l %%a in (1 1 %num%) do (
  16.     set /a min=0, max=0
  17.     for /l %%i in (1 1 %%a) do set /a min+=a[%%i], n=num-%%i+1&set /a max+=a[!n!]
  18.     if !min! leq %range2% if !max! geq %range1% (
  19.         rem echo %%a:[!min!,!max!]
  20.         call :Arrangement  %%a %num%
  21.     )
  22. )
  23. pause&exit/b
  24. rem 获取排列
  25. :Arrangement [num] [len]
  26. setlocal enableDelayedExpansion
  27. set /a num=%1, len=%2
  28. for /l %%a in (1 1 %num%) do (
  29.     if 1==%%a (set start=1&set "setstart=set start=1&") else (set /a start=%%a-1&set start=%%!start!&set "setstart=set /a start=!start!+1&")
  30.     set "do=!do! !setstart! for /l %%%%a in (^!start^!,1,%len%) do "
  31.     set "exp=!exp!,^!a[%%%%a]^!"
  32. )
  33. %do% (
  34.     set /a prior=sum, sum=0
  35.     if !prior! leq %range2% (
  36.         for %%a in (%exp%) do set /a sum+=%%a
  37.         if !sum! geq %range1% if !sum! leq %range2% echo%exp:,=+%=!sum!
  38.     )
  39. )
  40. endlocal
  41. goto :eof
复制代码

作者: powerbat    时间: 2011-5-8 13:16

思维稍乱,重新整理了一下
  1. @echo off
  2. set "arr=51, 8, 13, 2, 52, 61, 37, 85, 19, 11, 7, 62, 22, 38, 79,  1,2,3"
  3. set /a range1=102, range2=105
  4. :main
  5. setlocal enableDelayedExpansion
  6. for %%a in (%arr%) do set /a num+=1 & set a[!num!]=%%a
  7. if %num% gtr 20 echo Are you killing me?&pause&exit /b %num%
  8. rem 冒泡排序
  9. for /l %%i in (1 1 %num%) do (
  10.     set /a start = %%i + 1
  11.     for /l %%j in (!start! 1 %num%) do if !a[%%i]! gtr !a[%%j]! (
  12.         set tmp=!a[%%i]!
  13.         set a[%%i]=!a[%%j]!
  14.         set a[%%j]=!tmp!
  15.     )
  16. )
  17. for /l %%a in (1 1 %num%) do (
  18.     set /a min=0, max=0
  19.     for /l %%i in (1 1 %%a) do set /a min+=a[%%i], n=num-%%i+1&set /a max+=a[!n!]
  20.     if !min! leq %range2% if !max! geq %range1% (
  21.         rem echo %%a:[!min!,!max!]
  22.         call :Combination  %%a %num%
  23.     )
  24. )
  25. pause
  26. endlocal&exit/b
  27. rem 获取组合
  28. :Combination [num] [len]
  29. %static% set letters=[abcdefghijklmnopqrstuvwxyz]
  30. setlocal enableDelayedExpansion
  31. set /a num=%1, len=%2
  32. for /l %%a in (1 1 %num%) do (
  33.     set var=!letters:~%%a,1!
  34.     if 1==%%a (
  35.         set "set_start=set start=1"
  36.     ) else (
  37.         set /a base=%%a-1
  38.         for %%i in (!base!) do set base=!letters:~%%i,1!
  39.         set "set_start=set /a start=%%!base!+1"
  40.     )
  41.     set "do=!do! !set_start! & for /l %%!var! in (^!start^!,1,%len%) do "
  42.     set "exp=!exp!,^!a[%%!var!]^!"
  43. )
  44. %do% (
  45.     set /a prior=sum, sum=0
  46.     if !prior! leq %range2% (
  47.         for %%a in (%exp%) do set /a sum+=%%a
  48.         if !sum! geq %range1% if !sum! leq %range2% echo%exp:,=+%=!sum!
  49.     )
  50. )
  51. endlocal
  52. goto :eof
复制代码

作者: caruko    时间: 2011-5-8 14:18

好吧,其实我忘了说。。
每个数字只用一次来的。。
作者: powerbat    时间: 2011-5-8 15:08

我知道是这个意思。
set "arr=51, 8, 13, 2, 52, 61, 37, 85, 19, 11, 7, 62, 22, 38, 79,  1,2,3"
后面故意加了个重复数字
作者: wankoilz    时间: 2011-5-8 17:38

楼上也说说思路吧,直接看代码头晕
作者: powerbat    时间: 2011-5-8 19:10

思维形成定势了,果然有纰漏。稍作改造如下:
  1. @echo off
  2. set "arr=51, 8, 13, 2, 52, 61, 37, 85, 19, 11, 7, 62, 22, 38, 79"
  3. set /a min=102, max=105
  4. :main
  5. setlocal enableDelayedExpansion
  6. %const% set MAXNUM=20
  7. for %%a in (%arr%) do set /a num+=1 & set a[!num!]=%%a
  8. if %num% gtr %MAXNUM% echo Are you kidding me?&pause&exit /b %num%
  9. rem 冒泡排序
  10. for /l %%i in (1 1 %num%) do (
  11.     set /a start = %%i + 1
  12.     for /l %%j in (!start! 1 %num%) do if !a[%%i]! gtr !a[%%j]! (
  13.         set tmp=!a[%%i]!
  14.         set a[%%i]=!a[%%j]!
  15.         set a[%%j]=!tmp!
  16.     )
  17. )
  18. rem 为枚举组合数生成for嵌套语句
  19. set letters=[abcdefghijklmnopqrstuvwxyz]
  20. for /l %%a in (1 1 %MAXNUM%) do (
  21.     set var=!letters:~%%a,1!
  22.     if 1==%%a (
  23.         set "set_start=set /a start=00+1"
  24.     ) else (
  25.         set /a base=%%a-1
  26.         for %%i in (!base!) do set base=!letters:~%%i,1!
  27.         set "set_start=set /a start=%%!base!+1"
  28.     )
  29.     set "do=!do!!set_start! & for /l %%!var! in (^!start^!,1,^!num^!) do "
  30.     set "exp=!exp!,^!a[%%!var!]^!"
  31. )
  32. rem echo !do!
  33. rem echo !exp!
  34. rem pause
  35. for /l %%a in (1 1 %num%) do (
  36.     set /a minsum=0, maxsum=0
  37.     for /l %%i in (1 1 %%a) do set /a minsum+=a[%%i], n=num-%%i+1&set /a maxsum+=a[!n!]
  38.     rem echo %%a:[!minsum!,!maxsum!]
  39.     if !minsum! leq %max% if !maxsum! geq %min% (
  40.         set /a do_len=54*%%a, exp_len=8*%%a
  41.         call:enum
  42.     )
  43. )
  44. pause
  45. endlocal&exit/b
  46. :enum
  47. setlocal enableDelayedExpansion
  48. set do=!do:~0,%do_len%!
  49. set exp=!exp:~0,%exp_len%!
  50. %do% (
  51.     set /a sum=0%exp:,=+%
  52.     if !sum! geq %min% if !sum! leq %max% echo%exp:,=+%=!sum!
  53. )
  54. endlocal
  55. goto :eof
复制代码

作者: powerbat    时间: 2011-5-8 19:16

思路比较普通:先排序,分别从数组中取N个数(1≤N≤num)进行组合(先简单判断是否需要取组合数),再将组合数的和与目标比较。取组合数用的是for嵌套循环(利用bat预处理机制),echo !do!就知道展开后是什么了。

之前形成思维定势,老想着因为数组经过排序,所以如果前一组组合数的和大于max,后面就不用比较了,也即下面的当prior(sum)小于max时才比较:
    set /a prior=sum, sum=0
    if !prior! leq %max% (
        for %%a in (%exp%) do set /a sum+=%%a
        if !sum! geq %min% if !sum! leq %max% echo%exp:,=+%=!sum!
    )
还有逻辑问题,完全是废代码。
作者: wankoilz    时间: 2011-5-8 19:36

本帖最后由 wankoilz 于 2011-5-8 19:49 编辑

是有点复杂,没怎么看懂,不过楼上用的变量嵌套值得学习!
我求组合的思路是:
先随便拿一个元素出来,比如a,它形成的组合就一个a
然后加入b,它与前面所有已有的组合相组合,这里得到ab。加上前面已有的组合a、自身b,所以a和b形成的组合是a,ab,b
接着加入c,和前面一样,先得到ac,abc,bc,加上已有的和自身c,所有组合就是a,ab,b,ac,abc,bc,c
接下来是d
.
.
.
作者: caruko    时间: 2011-5-8 23:09

本帖最后由 caruko 于 2011-5-8 23:14 编辑

其实有想过只用一层循环来解决,通过一些判断来控制参与计算的变量就可以了。
但循环次数需要先计算全排列次数出来,可是全排列的数字超过13个就溢出了。
没有while条件的循环,用goto实际上跟call差不多效率。
作者: terse    时间: 2011-5-12 00:31

本帖最后由 terse 于 2011-5-12 00:32 编辑

怎么都这样复杂  我这样递归  效率当然不是很好
  1. @echo off&setlocal enabledelayedexpansion
  2. set "var=51 8 13 2 52 61 37 85 19 11 7 62 22 38 79"
  3. for %%i in (%var%) do set /a N+=1&set _!N!=%%i
  4. for /l %%i in (1 1 %N%) do (
  5.     set /a i=%%i+1
  6.     call :lp !_%%i!
  7. )
  8. pause&exit
  9. :lp
  10. for /l %%i in (!i! 1 %N%) do (
  11.      set /a i=%%i+1,M=%~1+_%%i
  12.      if !M! geq 103 if !M! leq 104 echo %~1+!_%%i!=!M!
  13.      if !M! lss 104 CALL%0 "%~1+!_%%i!"
  14. )
复制代码

作者: wankoilz    时间: 2011-5-13 10:01

ters这种方法会漏掉不少组合吧。
假设有1-15这15个数,在取两个数的组合中就只能得到1-2,2-3,3-4,4-5...14-15,而其它的1-3,1-4,1-5...等都漏掉了
作者: terse    时间: 2011-5-13 11:01

ters这种方法会漏掉不少组合吧。
假设有1-15这15个数,在取两个数的组合中就只能得到1-2,2-3,3-4,4-5...14-15,而其它的1-3,1-4,1-5...等都漏掉了
wankoilz 发表于 2011-5-13 10:01


怎么会呢?
给个直观点
  1. @echo off
  2. set n=8
  3. for /l %%i in (1 1 %N%) do (
  4.     set /a i=%%i+1
  5.     call :lp "%%i"
  6. )
  7. pause&exit
  8. :lp
  9. for /l %%i in (%i% 1 %N%) do (
  10.      set /a i=%%i+1
  11.      echo %~1 %%i
  12.      if %%i equ %n% exit/b
  13.      CALL :Lp "%~1 %%i"
  14. )
复制代码

作者: wankoilz    时间: 2011-5-13 22:41

本帖最后由 wankoilz 于 2011-5-13 22:54 编辑

抱歉,之前不能上网,自己照着手机在电脑上测试了一下你的代码有点问题,现在直接复制代码测试是没问题的。
看来我还没高清楼上的算法,请教下:楼上代码的运行结果中,从 12,123,1234,12345,123456,1234567,12345678后接着是123456 8 ,为什么会有123456 8这个结果呢(按照我的理解接下来应该是23,234,2345,23456...),不懂...
作者: powerbat    时间: 2011-5-15 18:38

递归里面用循环,循环体里面又递归调用,这个递归是很多层的。(这种方法很少用,要死很多脑细胞的)
楼上估计是把递归函数第一个语句还要循环给忘了:
for /l %%i in (%i% 1 %N%) do (
作者: wankoilz    时间: 2011-5-15 19:46

本帖最后由 wankoilz 于 2011-5-15 19:48 编辑

我的理解是:批处理开始执行第一个for,调用函数会得到12,123,1234,12345,123456,1234567,12345678。此时跳出函数,回到for,再调用函数得到23,234,2345,23456,234567,2345678
我就想知道我在18楼说的123456 8的结果是怎么来的(代码具体是如何执行的),恕我愚钝哪...
作者: powerbat    时间: 2011-5-15 19:58

“调用函数会得到12,123,1234,12345,123456,1234567,12345678。此时跳出函数”
递归函数也有for啊,这个for取第一个值时,通过递归,就得到了12,123,1234,12345,123456,1234567,12345678,还远远没到跳出的时候。每次递归都要带来一次循环,每个循环体里面又要递归……
作者: wankoilz    时间: 2011-5-16 10:17

本帖最后由 wankoilz 于 2011-5-18 14:30 编辑

感谢powerbat讲解。确实!我之前还以为批处理递归没有这种“堆栈”的效果,结果测试了一下还真如楼上所说:每次call 都带来一次循环,那些被call阻挡的,没来得及执行的代码似乎被放入类似“堆栈”的结构里,在call完毕之后都陆续被执行了。测试如下:
  1. @echo off&setlocal enabledelayedexpansion
  2. call :lp
  3. pause
  4. :lp
  5. for /l %%a in (1,1,5) do (
  6.     echo %%a
  7.     set/an+=1&if !n! equ 3 call :lp
  8. )
复制代码
第一次for:本该执行5次echo%%a,但执行到3的时候被call :lp阻断了(此时echo 4和echo 5被“存”起来了),接着就完整的执行了一次for,完了把存起来的echo 4和echo 5也执行了,所以有如下结果(用空行分隔了一下,方便分析):
  1. 1
  2. 2
  3. 3
  4. 1
  5. 2
  6. 3
  7. 4
  8. 5
  9. 4
  10. 5
复制代码
而且这种存储确实是按照类似“堆栈”的方式,即“后进先出”,从下面代码,的执行结果就可以看出来:
  1. @echo off&setlocal enabledelayedexpansion
  2. call :lp
  3. pause
  4. :lp
  5. for /l %%a in (1,1,5) do (
  6.     echo %%a
  7.     set/an+=1
  8.     if !n! equ 3 call :lp
  9.     if !n! equ 5 call :lp
  10. )
复制代码
结果(用空行分隔了一下,方便分析):
  1. 1
  2. 2
  3. 3
  4. 1
  5. 2
  6. 1
  7. 2
  8. 3
  9. 4
  10. 5
  11. 3
  12. 4
  13. 5
  14. 4
  15. 5
复制代码
第一个for,执行到3的时候被call阻断,输出1,2,3(echo 4和echo 5被保存),然后执行第二次for,执行到2的时候n等于5了,再次call,这时输出1,2(echo 3,echo 4,echo 5被保存),然后是最后一个完整的for,输出1,2,3,4,5。完了执行被保存的call(后保存的先执行),输出3,4,5和4,5。
这样看来15楼的代码是很不错的!




欢迎光临 批处理之家 (http://bbs.bathome.net/) Powered by Discuz! 7.2