标题: [求助]如何求出文本中哪些数相加等于指定的值 [打印本页]
作者: ccwan 时间: 2007-3-3 01:42 标题: [求助]如何求出文本中哪些数相加等于指定的值
我在工作中遇到一个难题，现在发到论坛上，请大家帮忙解决。
现有test.txt，内容为：
4816
4776
4498
4616
4948
4684
4710
5266
4760
5168
4770
5134
5076
4784
5174
4732
4782
4746
4730
5224
5164
4742
4724
4730
4762
4162
4188
4830
4942
4072
4270
4520
4808
5130
4272
4262
4238
4240
4828
4168
4754
4720
4896
4824
5206
4322
3800
4826
4632
5104
5134
4838
3858
5008
4828
5234
4324
5282
5348
5150
4724
4682
4720
5218
4744
4742
4760
5194
4792
4712
4754
4704
我想求出其中哪些数相加结果等于1717804776
4498
4616
4948
4684
4710
5266
4760
5168
4770
5134
5076
4784
5174
4732
4782
4746
4730
5224
5164
4742
4724
4730
4762
4162
4188
4830
4942
4072
4270
4520
4808
5130
4272
4262
4238
4240
4828
4168
4754
4720
4896
4824
5206
4322
3800
4826
4632
5104
5134
4838
3858
5008
4828
5234
4324
5282
5348
5150
4724
4682
4720
5218
4744
4742
4760
5194
4792
4712
4754
4704
要求：如果有多种组合，依次列出；这72个数中每个数在每种组合中只能用一次。
作者: slore 时间: 2007-3-3 01:44
放弃用p吧。
作者: ccwan 时间: 2007-3-3 01:47
我不求效率高，也不在乎是否使用第三方工具，如awk等，只要达到要求就行。
作者: oilio 时间: 2007-3-3 02:16
这个要用p多麻烦啊，而且我的水平现在肯定是想不出来的，呵呵。期待高手解答！
作者: zh159 时间: 2007-3-3 02:36
第一个数据和后面的逐一相加，到第二个时抛弃第一个数......
作者: ccwan 时间: 2007-3-3 04:38
顶起，莫沉了。
作者: NaturalJ0 时间: 2007-3-3 04:56
是不是得把所有组合方式都过一遍
作者: ccwan 时间: 2007-3-3 05:00
应该是的。
要求出所有的组合，最后显示＝所求值的组合。
作者: NaturalJ0 时间: 2007-3-3 05:02
很有意思的一题啊，不过难度好像也不小。
作者: zh159 时间: 2007-3-3 05:38
参照这个在合适的地方加入“if "计算结果" == "171780" ”进行判断
[共同参与][挑战思路] 求一列数所有不同组合的和
作者: slore 时间: 2007-3-3 05:54
第一步要排序
作者: 20080610 时间: 2007-3-3 05:55
72个数排列组合?
恐怕需要N个小时才能出结果.
批处理还没有到这个运算能力
作者: ccwan 时间: 2007-3-3 06:09
re zh159
兄的意思我明白，其实版主那道题本就是为我的疑难而立的，我经过使用之后，没有达到目的，搁置了起来。
近日又要用到了，所以再次提及，希望可以得到解决。
作者: zh159 时间: 2007-3-3 06:13
我用那个试了，半天没出来，考虑vbs之类的吧
作者: NaturalJ0 时间: 2007-3-3 06:18
好像要套很多层的递归啊。
作者: youxi01 时间: 2007-3-3 06:50
同志，好像这72个数中有8个数是重复的：
4730
5134
4828
4724
4720
4742
4760
4754
是不是只要考虑其它的64个数？！5134
4828
4724
4720
4742
4760
4754
作者: ccwan 时间: 2007-3-3 06:54
不是这样的，例如：4078+4078+4078+4052+4650＝20936
如果test.txt中有3个4078的话，允许上式出现。
作者: youxi01 时间: 2007-3-3 07:01
这样就更加加大了难度！
如果只考虑64个不重复的数的话，根据推算，至少需要35个数，至多37个数
作者: ccwan 时间: 2007-3-3 07:05
这是实际应用中的必然情况，也就是说，如果代码不运算重复数的话，只是练一练大家的手，而非解决我的难题了，请谅解。
作者: youxi01 时间: 2007-3-3 07:16
其实，将组合数字的数目排除在了35个到37个之间，如果按照常规的办法的话，组合的可能情况仍然是个极其庞大的数字。
作者: everest79 时间: 2007-3-3 07:18
好像很耗时间，嘻嘻，没测试
SETLOCAL ENABLEDELAYEDEXPANSION
for /f %%i in (data.txt) do (
set /a a1+=1
set _data!a1!=%%i)
for /l %%a in (1,3,%a1%) do (
set /a b=%%a+1
for /l %%b in (!b!,1,!b!) do (
set /a c=!b!+1
for /l %%c in (!c!,1,!c!) do (
set /a d=!c!+1
for /l %%d in (!d!,1,%a1%) do (
set /a z="1/(171780-!_data%%a!-!_data%%b!-!_data%%c!-!_data%%d!)"||echo !_data%%a!+!_data%%b!+!_data%%c!+!_data%%d!^=171780&&set /a _data%%a=0,_data%%b=0,_data%%c=0,_data%%d=0)
)
)
)
set
pause
[ Last edited by everest79 on 2007-3-2 at 06:33 PM ]for /f %%i in (data.txt) do (
set /a a1+=1
set _data!a1!=%%i)
for /l %%a in (1,3,%a1%) do (
set /a b=%%a+1
for /l %%b in (!b!,1,!b!) do (
set /a c=!b!+1
for /l %%c in (!c!,1,!c!) do (
set /a d=!c!+1
for /l %%d in (!d!,1,%a1%) do (
set /a z="1/(171780-!_data%%a!-!_data%%b!-!_data%%c!-!_data%%d!)"||echo !_data%%a!+!_data%%b!+!_data%%c!+!_data%%d!^=171780&&set /a _data%%a=0,_data%%b=0,_data%%c=0,_data%%d=0)
)
)
)
set
pause
作者: everest79 时间: 2007-3-3 07:39
晕，原来是四位数，我看成五位数了
作者: everest79 时间: 2007-3-3 08:15
写不下去，太多
作者: vkill 时间: 2007-3-3 09:20
这么难的题目终于发出来了哦~我是想不出了,期待高手
作者: zhoushijay 时间: 2007-3-3 11:03
光是一道数学题目就可以杀死大片脑细胞了,更别说设计出一 套算法来-_-!
作者: slore 时间: 2007-3-3 21:18
排序后:
3800
3858
4072
4162
4168
4188
4238
4240
4262
4270
4272
4322
4324
4498
4520
4616
4632
4682
4684
4704
4710
4712
4720
4720
4724
4724
4730
4730
4732
4742
4742
4744
4746
4754
4754
4760
4760
4762
4770
4776
4782
4784
4792
4808
4816
4824
4826
4828
4828
4830
4838
4896
4942
4948
5008
5076
5104
5130
5134
5134
5150
5164
5168
5174
5194
5206
5218
5224
5234
5266
5282
5348
最大的38位数之和3858
4072
4162
4168
4188
4238
4240
4262
4270
4272
4322
4324
4498
4520
4616
4632
4682
4684
4704
4710
4712
4720
4720
4724
4724
4730
4730
4732
4742
4742
4744
4746
4754
4754
4760
4760
4762
4770
4776
4782
4784
4792
4808
4816
4824
4826
4828
4828
4830
4838
4896
4942
4948
5008
5076
5104
5130
5134
5134
5150
5164
5168
5174
5194
5206
5218
5224
5234
5266
5282
5348
5348+5282+5266+5234+5224+5218+5206+5194+5174+5168+5164+5150+5134+5134+5130+5104+5076+5008+4948+4942+4896+4838+4830+4828+4828+4826+4824+4816+4808+4792+4784+4782+4776+4770+4762=175264
最小的39位数之和
3800+3858+4072+4162+4168+4188+4238+4240+4262+4270+4272+4322+4324+4498+4520+4616+4632+4682+4684+4704+4710+4712+4720+4720+4724+4724+4730+4730+4732+4742+4742+4744+4746+4754+4754+4760+4760+4762+4770=176548>171780
那么说明什么？只能是38位才可以。（随便算了下最小的38个加起来是171778）
这样位数就限定了！从2的72次方-1次运算减少到396561735952215036840次，约是344*2的60次方。。。虽然很大但是你要知道。。2的72次方是它的12！(≈11.9)的倍！
而且可以进一步减少次数。。。。
作者: slore 时间: 2007-3-3 21:28
最小的38个数之和 和需要的数字差2 （171780-171778＝2）
3800+3858+4072+4162+4168+4188+4238+4240+4262+4270+4272+4322+4324+4498+4520+4616+4632+4682+4684+4704+4710+4712+4720+4720+4724+4724+4730+4730+4732+4742+4742+4744+4746+4754+4754+4760+4760+4762
而第39个数字是4770,和他最接近的数是第38个（我按顺序排的）。而这个数字4762
和4770的差大于2。
也就是说如果把39替换了38那么数字变大了6（171786）。
而这个数字是38个数字第2小的数。以后的数字都大于它！
所以最终的答案出来了！！！！！
无符合要求组合
作者: ccwan 时间: 2007-3-3 21:49
re slore
不会如兄所说没有符合要求组合，因为我是经过一番挑选后求得这一结果，然后出的题目。
作者: slore 时间: 2007-3-3 21:53
| Quote: | |
|
那你的数字是38个么？
你发短消息给我你的那个数字吧。
我觉得分析的没有错误啊。。。不会是计算上的吧～
作者: ccwan 时间: 2007-3-3 21:59
抱歉，我是随意选中一些数，得出一个结果后就发出来的，没有记录是哪些数，但可以肯定是存在这种组合的。
若因为我的疏忽造成真的没有，兄可以自己定义一个值，只要可以完成就行。
作者: slore 时间: 2007-3-3 22:05
随便给一个？那只能是把第39个换成4764...那样就唯一解。。
这个根据情况吧。否则计算量太大了。你看我说的那个累加次数！2的几十次方啊。
方法我觉得最省的就是:
1.排序
2.判断至少和至多的数字个数。
3.枚举这2个里面的数字。。。。
（这个枚举的过程我找下，懒的再想了，但是数字越多，运算就……）
作者: qjbm 时间: 2007-3-4 00:21
又见排列组合！
没有简单算法.
n=数组中数的个数
r=从 1 到 数组中数的个数总和
在nCr中枚举是否有符合条件.....
这种程序写完了也不适合在32位系统上运行...
--------------------------------------
若仅以解决本题可采用qzwqzw兄的递归代码稍加修改.
但计算速度还是要看运气........
@ECHO %DBG% OFF
SETLOCAL ENABLEDELAYEDEXPANSION
SET /A THE=171780
FOR /F %%n IN (TEST.TXT) DO (
SET /A i+=1
SET gn!i!=%%n
)
FOR /L %%j IN (1,1,%i%) DO CALL :REC %%j
GOTO :EOF
:REC
SETLOCAL
CALL SET tmp=%%gn%1%%
SET /A sum+=%tmp%
IF %sum% GTR %THE% GOTO :EOF
SET /A lvl+=1
IF %lvl% GTR 1 (
SET exp=%exp%+%tmp%
SET /A idx+=1
CLS & ECHO 第 !idx! 次计算
IF !sum! EQU %THE% (
ECHO !exp!=%sum%
ECHO 继续计算请按任意键&PAUSE>NUL
)
) ELSE (
SET exp=%tmp%
)
SET /A nxt=%1+1
FOR /L %%j IN (%nxt%,1,%i%) DO CALL :REC %%j
ENDLOCAL & SET idx=%idx%
GOTO :EOF
运气不错!SETLOCAL ENABLEDELAYEDEXPANSION
SET /A THE=171780
FOR /F %%n IN (TEST.TXT) DO (
SET /A i+=1
SET gn!i!=%%n
)
FOR /L %%j IN (1,1,%i%) DO CALL :REC %%j
GOTO :EOF
:REC
SETLOCAL
CALL SET tmp=%%gn%1%%
SET /A sum+=%tmp%
IF %sum% GTR %THE% GOTO :EOF
SET /A lvl+=1
IF %lvl% GTR 1 (
SET exp=%exp%+%tmp%
SET /A idx+=1
CLS & ECHO 第 !idx! 次计算
IF !sum! EQU %THE% (
ECHO !exp!=%sum%
ECHO 继续计算请按任意键&PAUSE>NUL
)
) ELSE (
SET exp=%tmp%
)
SET /A nxt=%1+1
FOR /L %%j IN (%nxt%,1,%i%) DO CALL :REC %%j
ENDLOCAL & SET idx=%idx%
GOTO :EOF
在进行103次计算时得到第一种结果:
4816+4776+4498+4616+4948+4684+4710+5266+4760+5168+4770+5134+5076+4784+5174+4732+4782+4746+4730+5224+5164+4742+4724+4730+4762+4162+4188+4830+4942+4072+4270+4520+4808+5130+4238+5104=171780
还是那句话,此题不宜在32位系统环境下解决.下面的附件是在22万次计算后得到的321种结果!!!!!!
[ Last edited by qjbm on 2007-3-3 at 02:29 PM ]
附件 1:结果.txt (2007-3-4 03:29, 60.98 K, 下载附件所需积分 1点 ,下载次数： 9)
作者: youxi01 时间: 2007-3-4 01:21
TO 26F：
如果考虑重复数字的话，
最大的数字组合只要35个，而非38个！
最小的数字组合需要38个
所以，真正的数字个数有35，36，37，38等情况。
如果按照常规办法的话，根据排列组合规律，数字将会极其庞大！我已经宣布退出，期待高手。
作者: slore 时间: 2007-3-4 01:31
| Quote: | |
|
哦，知道意思了。。。。。。。。。。
[ Last edited by slore on 2007-3-3 at 12:47 PM ]
作者: youxi01 时间: 2007-3-4 03:12
不是吧，效率这么低，那等我老了，都可能还没全部运算完
作者: 20080610 时间: 2007-3-4 03:41
理想状况下从这些结果里筛选.
72!/35!(72-35)!+72!/36!(72-36)!+72!/37!(72-37)!+72!/38!(72-38)!
作者: qjbm 时间: 2007-3-4 03:48
72!/35!(72-35)!+72!/36!(72-36)!+72!/37!(72-37)!+72!/38!(72-38)!
n=数组中数的个数
r=从 35 到 38
在nCr中枚举是否有符合条件.....
一样的.海量计算模式!!
作者: 20080610 时间: 2007-3-4 03:50
批处理应该是完成不料的...
作者: slore 时间: 2007-3-4 05:26
放弃了……
枚举的代码写出来了……运算的太慢了。
没响应……关闭了。。数太多了。。
作者: Primalchaos 时间: 2007-3-4 05:28
楼上何不将代码公布，让我们学习一下？
作者: slore 时间: 2007-3-4 05:41
不是用p写……
P运算的话更慢……
就是递归之类……网上搜索下 组合 递归。。算法很多的，dephi的，c的，vb的……
作者: Primalchaos 时间: 2007-3-4 06:19
那么兄可以给出c语言的代码吗？
作者: slore 时间: 2007-3-4 06:35
http://topic.csdn.net/t/20031003/10/2322382.html
http://www.ycgczj.com.cn/53677.html
思路貌似基本是递归回溯
作者: youxi01 时间: 2007-3-4 07:34
不知道为什么，我写的一段代码，测出的36个数字组合要比32F的组数多的多？！
代码比32F的效率要高，但还是很不够，正在测试，稍候发布。
作者: youxi01 时间: 2007-3-4 07:48
代码如下,欢迎测试，指正。
@echo off
setlocal enabledelayedexpansion
set num=0
for /f %%n in (test.txt) do (
set /a i+=1
set gn!i!=%%n
)
for /l %%i in (1,1,36) do call :rec %%i
pause
goto :eof
:rec
setlocal
set tmp=!gn%1!
set/a flag+=1
if %flag% EQU 1 (set str=%tmp%) else set str=%str%+%tmp%
set/a sum=%sum%+%tmp%
set /a nxt1=%1+1,nxt2=%1+36
if %nxt2% gtr 72 set/a nxt2=72
set /a lvl+=1
if %lvl% lss 36 (
for /l %%j in (%nxt1%,1,%nxt2%) do call :rec %%j
) else (
set/a idx+=1
title 正在检测第 %idx% 组数 已检测出 %num% 组数
if %sum% EQU 171780 echo %str%=171780 在第 %idx% 组数 & set/a num+=1
)
endlocal & set idx=%idx% & set num=%num%
说明：本段代码给出的是针对36个数字组合时的情况，其它情况不在考虑范围内，有需要请自行更改。setlocal enabledelayedexpansion
set num=0
for /f %%n in (test.txt) do (
set /a i+=1
set gn!i!=%%n
)
for /l %%i in (1,1,36) do call :rec %%i
pause
goto :eof
:rec
setlocal
set tmp=!gn%1!
set/a flag+=1
if %flag% EQU 1 (set str=%tmp%) else set str=%str%+%tmp%
set/a sum=%sum%+%tmp%
set /a nxt1=%1+1,nxt2=%1+36
if %nxt2% gtr 72 set/a nxt2=72
set /a lvl+=1
if %lvl% lss 36 (
for /l %%j in (%nxt1%,1,%nxt2%) do call :rec %%j
) else (
set/a idx+=1
title 正在检测第 %idx% 组数 已检测出 %num% 组数
if %sum% EQU 171780 echo %str%=171780 在第 %idx% 组数 & set/a num+=1
)
endlocal & set idx=%idx% & set num=%num%
[ Last edited by youxi01 on 2007-3-4 at 07:50 AM ]
作者: qjbm 时间: 2007-3-5 06:10
| Quote: | |
|
压缩了递归数组范围的同时,也压缩了找到结果的可能性.
作者: Climbing 时间: 2007-3-5 06:36
用高级语言实现起来都比较困难，就不用提批处理了，效率太低了。
作者: electronixtar 时间: 2007-3-11 07:42
| Quote: | |
|
排序，然后筛选 个位数和十位数 相加为 80 的组合(因为结果要求为171780)。筛选完后再求组合。
作者: qjbm 时间: 2007-3-16 04:57
| Quote: | |
|
在没引用qzwqzw的代码之前,这样的想法就已经尝试过,
代码写到中途才发现在编写 筛选 [ 组合中后两位和为 80 ] 时纯粹为走弯路.
因为筛选也是需要 枚举 排列组合.....呵呵....
为什么不直接给出结果呢?既如此,排序又有何用呢...呵呵.....