标题: [共同参与][挑战思路] 求一列数所有不同组合的和 [打印本页]
作者: namejm 时间: 2006-12-30 10:40 标题: [共同参与][挑战思路] 求一列数所有不同组合的和
给出一个纯数值文本，一行一条记录，无空行，求这一列数值所有不同组合的和(行号相同而数值出现顺序不同的组合视为同一组合)，要求输出格式为 n1+n2+n3=sum。
比如文本内容为：
1
2
3
4
5
要求输出的格式为(次序可以打乱)：2
3
4
5
1+2=3
1+3=4
1+4=5
1+5=6
2+3=5
2+4=6
2+5=7
3+4=7
3+5=8
4+5=9
1+2+3=6
1+2+4=7
1+2+5=8
1+3+4=8
1+3+5=9
1+4+5=10
2+3+4=9
2+3+5=11
3+4+5=12
1+2+3+4=10
1+2+3+5=11
1+3+4+5=13
2+3+4+5=14
1+2+3+4+5=15
1+2+3=6 和 2+1+3=6 视作同一组合。1+3=4
1+4=5
1+5=6
2+3=5
2+4=6
2+5=7
3+4=7
3+5=8
4+5=9
1+2+3=6
1+2+4=7
1+2+5=8
1+3+4=8
1+3+5=9
1+4+5=10
2+3+4=9
2+3+5=11
3+4+5=12
1+2+3+4=10
1+2+3+5=11
1+3+4+5=13
2+3+4+5=14
1+2+3+4+5=15
[ Last edited by namejm on 2006-12-29 at 09:55 PM ]
作者: lxmxn 时间: 2006-12-30 10:47
不明白是什么意思？举个简单的例子？
作者: pengfei 时间: 2006-12-30 10:54
namejm兄的意思是一个文本中每一行都有一个数字(大概二十个数), 要计算出这些数字所有可能的和.
test.txt
1
2
3
要求用批处理处理后的结果为:2
3
1+2=3
1+3=4
2+3=5
1+2+3=6
1+3=4
2+3=5
1+2+3=6
作者: a9319751 时间: 2006-12-30 19:53
@echo off
SETLOCAL ENABLEDELAYEDEXPANSION
for /f "tokens=1,2 delims=:" %%i in ('findstr /n . 1.txt') do (
set /a n%%i=%%j
set /a nnum=%%i
)
if "nnum" == "1" echo %n1%=%n1% && goto :eof
:num
set sum=
set sumf=
set /a num+=1
set /a num_1=%num%+1
set /a nnum_1=%nnum%-1
for /l %%i in (%num% 1 %nnum%) do (
call set /a sum=!sum!+%%n%%i%%
call set sumf=!sumf!+%%n%%i%%
if "!sumf!" == "+!sum!" (set sumf=!sumf:~1!) ELSE (echo !sumf!=!sum!)
)
for /l %%i in (%num_1% 1 %nnum_1%) do (
call set /a sum=!sum!-%%n%%i%%
call set sumf=!sumf:+%%n%%i%%=!
echo !sumf!=!sum!)
)
if %num% lss %nnum% goto :num
pause
代码并不完善，下面这个替换不知道应该怎么写，希望大家指正SETLOCAL ENABLEDELAYEDEXPANSION
for /f "tokens=1,2 delims=:" %%i in ('findstr /n . 1.txt') do (
set /a n%%i=%%j
set /a nnum=%%i
)
if "nnum" == "1" echo %n1%=%n1% && goto :eof
:num
set sum=
set sumf=
set /a num+=1
set /a num_1=%num%+1
set /a nnum_1=%nnum%-1
for /l %%i in (%num% 1 %nnum%) do (
call set /a sum=!sum!+%%n%%i%%
call set sumf=!sumf!+%%n%%i%%
if "!sumf!" == "+!sum!" (set sumf=!sumf:~1!) ELSE (echo !sumf!=!sum!)
)
for /l %%i in (%num_1% 1 %nnum_1%) do (
call set /a sum=!sum!-%%n%%i%%
call set sumf=!sumf:+%%n%%i%%=!
echo !sumf!=!sum!)
)
if %num% lss %nnum% goto :num
pause
call set sumf=!sumf:+%%n%%i%%=!
作者: Primalchaos 时间: 2006-12-31 04:53
顶起来！想知道。
作者: 无奈何 时间: 2006-12-31 05:38
a9319751 兄的代码错误较多，发现的错误有丢失了组合、重复、部分计算结果错误等。
namejm 兄提出的这个问题，非常复杂。我一直没有找到好的方法，现在我能完成的最好情况也丢失 4 组组合，我知道问题出在哪里，苦于没有办法转换成有效的批处理语句。
先帖一下代码，以后有时间再完善吧，希望能看到哪位兄弟完成这个题目。
| Quote: | |
|
输出结果：
1 + 2 = 3
1 + 2 + 3 = 6
1 + 3 = 4
1 + 2 + 3 + 4 = 10
1 + 3 + 4 = 8
1 + 4 = 5
1 + 2 + 3 + 4 + 5 = 15
1 + 3 + 4 + 5 = 13
1 + 4 + 5 = 10
1 + 5 = 6
2 + 3 = 5
2 + 3 + 4 = 9
2 + 4 = 6
2 + 3 + 4 + 5 = 14
2 + 4 + 5 = 11
2 + 5 = 7
3 + 4 = 7
3 + 4 + 5 = 12
3 + 5 = 8
4 + 5 = 9
丢失项：1 + 2 + 3 = 6
1 + 3 = 4
1 + 2 + 3 + 4 = 10
1 + 3 + 4 = 8
1 + 4 = 5
1 + 2 + 3 + 4 + 5 = 15
1 + 3 + 4 + 5 = 13
1 + 4 + 5 = 10
1 + 5 = 6
2 + 3 = 5
2 + 3 + 4 = 9
2 + 4 = 6
2 + 3 + 4 + 5 = 14
2 + 4 + 5 = 11
2 + 5 = 7
3 + 4 = 7
3 + 4 + 5 = 12
3 + 5 = 8
4 + 5 = 9
1+2+4=7
1+2+5=8
1+3+5=9
2+3+5=11
1+2+5=8
1+3+5=9
2+3+5=11
作者: youxi01 时间: 2006-12-31 12:24
也贴一段效率不怎样高的代码：
@echo off
setlocal enabledelayedexpansion
for /f %%i in (test.txt) do (
set flag=%%i
REM ===========================
REM 删除重复行；
Rem ===========================
if not defined !flag! (
set %%i=A
REM ===========================
REM 获取文件行数；
Rem ===========================
set /a CYC_num_+=1
set str=%%i !str!))
REM ===========================
REM 设置下个for循环次数；
Rem ===========================
set /a CYC_num=%CYC_num_%-3
call :test str
for /l %%i in (1 1 %CYC_num%) do call :test Res
pause>nul
:test
for /f "delims== tokens=2" %%i in ('set %1') do (
set tem=%%i
for %%a in (%%i) do (
set flag=!tem:%%a =!
if not defined !flag! (
set var=
set num=
set /a a+=1
set Res!a!=!tem:%%a =!
call :Get_SUM %%Res!a!%%
set !flag!=A
)
)
)
goto :eof
:Get_SUM
if not "%1"=="" (
set var=%1+!var!
set /a num+=%1
shift
goto :Get_SUM)
echo !var:~0,-1!=!num!
说明：文本文件test.txt中的数字至少需要不重复的三行！setlocal enabledelayedexpansion
for /f %%i in (test.txt) do (
set flag=%%i
REM ===========================
REM 删除重复行；
Rem ===========================
if not defined !flag! (
set %%i=A
REM ===========================
REM 获取文件行数；
Rem ===========================
set /a CYC_num_+=1
set str=%%i !str!))
REM ===========================
REM 设置下个for循环次数；
Rem ===========================
set /a CYC_num=%CYC_num_%-3
call :test str
for /l %%i in (1 1 %CYC_num%) do call :test Res
pause>nul
:test
for /f "delims== tokens=2" %%i in ('set %1') do (
set tem=%%i
for %%a in (%%i) do (
set flag=!tem:%%a =!
if not defined !flag! (
set var=
set num=
set /a a+=1
set Res!a!=!tem:%%a =!
call :Get_SUM %%Res!a!%%
set !flag!=A
)
)
)
goto :eof
:Get_SUM
if not "%1"=="" (
set var=%1+!var!
set /a num+=%1
shift
goto :Get_SUM)
echo !var:~0,-1!=!num!
作者: dbc6013 时间: 2006-12-31 21:49
| Quote: | |
|
这个问题我非常关注，能讲一下思路吗？
其他高手也可以讲一下，
在这里先谢过了。
作者: qzwqzw 时间: 2007-1-1 02:31
此类问题使用递归算法思路要清晰的多
多层循环虽然也可以实现，不过非常难于编写和阅读
下面是一个递归的例子
@echo off
setlocal enabledelayedexpansion
for /f %%n in (test.txt) do (
set /a i+=1
set gn!i!=%%n
)
set gn
pause
for /l %%j in (1,1,%i%) do call :rec %%j
pause
goto :eof
:rec
setlocal
call set tmp=%%gn%1%%
set /a sum+=%tmp%
set /a lvl+=1
if %lvl% gtr 1 (
set exp=%exp%+%tmp%
set /a idx+=1
echo !idx!:!exp!=%sum%
) 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
[ Last edited by qzwqzw on 2006-12-31 at 01:48 PM ]setlocal enabledelayedexpansion
for /f %%n in (test.txt) do (
set /a i+=1
set gn!i!=%%n
)
set gn
pause
for /l %%j in (1,1,%i%) do call :rec %%j
pause
goto :eof
:rec
setlocal
call set tmp=%%gn%1%%
set /a sum+=%tmp%
set /a lvl+=1
if %lvl% gtr 1 (
set exp=%exp%+%tmp%
set /a idx+=1
echo !idx!:!exp!=%sum%
) 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
作者: Primalchaos 时间: 2007-1-1 02:52
佩服！不但实现结果，还能显示到底有多少组组合
作者: ccwan 时间: 2007-1-1 03:42
几位的代码确实精彩，蕴含着智慧和厚重的知识积累，是我学习的榜样。
作者: weapfe 时间: 2007-1-1 04:20 标题: 九楼的代码好像也．．．
如题．我的test.txt的内容为：
１
２
３
运行结果是：
gn1=1
gn2=2
gn3=3
请按任意键继续. . .
1:1+2=3
2:1+2+3=6
3:1+3=4
4:2+3=5
请按任意键继续. . .
不知是．．．．
作者: tghksj 时间: 2007-1-1 04:43
9楼 qzwqzw
我只能加两分,你的代码拿回家仔细看...
没看出来排除重复组合部分啊?
--------------------
我先慢慢看,
现在第一个pause之前完全理解了.....
---------------------
在 :rec 这转不出来了.............
谁能告诉我那个 %1 是怎么回事吗????
------------------------------------
知道 += 是怎么回事了........原来和C差不多....
------------------------------------
......
ECHO ON了之后
代码对着结果顺下来一遍.....
:rec 还是不大理解....
-------------------------
再看,一定看明白了~学C的时候递归就没学好,这次一定努力一下.......
----------------------
明白了......看懂了!
[ Last edited by tghksj on 2007-1-1 at 11:58 AM ]
作者: flamey 时间: 2007-1-1 04:55
加错分了！！！！
作者: tao0610 时间: 2007-1-5 08:49
几天假期多了不少好东西....
9楼的递归确实是妙,但考虑到效率最好避开FOR的嵌套和CALL递归.
不支持重复数.
@echo off&setlocal enabledelayedexpansion
set n=1
for /f %%n in (test.txt) do (
set /a i+=1
set str!i!=%%n
)
set str
pause&echo.
:loop
set/a n+=1
if not defined str%n% goto end
for /f "tokens=1* delims==" %%a in ('set result 2^>nul') do (
set/a x+=1
set result!x!=%%b+!str%n%!
)
set/a f=n-1
if not defined flag!str%n%! for /l %%j in (1,1,%f%) do (
set/a x+=1
set result!x!=!str%%j!+!str%n%!
)
set/a flag!str%n%!+=1
goto :loop
:end
for /f "tokens=1* delims==" %%a in ('set result 2^>nul') do (
set/a id+=1
set/a %%a=%%b
echo !id!:%%b=!%%a!
)
pause&goto :eof
set n=1
for /f %%n in (test.txt) do (
set /a i+=1
set str!i!=%%n
)
set str
pause&echo.
:loop
set/a n+=1
if not defined str%n% goto end
for /f "tokens=1* delims==" %%a in ('set result 2^>nul') do (
set/a x+=1
set result!x!=%%b+!str%n%!
)
set/a f=n-1
if not defined flag!str%n%! for /l %%j in (1,1,%f%) do (
set/a x+=1
set result!x!=!str%%j!+!str%n%!
)
set/a flag!str%n%!+=1
goto :loop
:end
for /f "tokens=1* delims==" %%a in ('set result 2^>nul') do (
set/a id+=1
set/a %%a=%%b
echo !id!:%%b=!%%a!
)
pause&goto :eof
作者: qasa 时间: 2007-1-5 15:20
9楼的代码思路好强，一定要加分。
慢慢分释下这段代码.
作者: lxmxn 时间: 2007-1-5 23:55
15楼的代码运行的效率的确比9楼的高不少，两个都值得学习，加分。
作者: pengfei 时间: 2007-1-7 13:13
好久没来, 原来这个问题已经完美解决了, 9楼qzwqzw兄的递归确实是解决此问题的最好算法, 而15楼tao0610兄的改进代码效率大为提高, 兴奋中, 一个字强...
最初和namejm兄讨论时也写过一段, 不过丢失了一些组合项, 后来也想过不少算法, 最终发现只有递归才能很好的解决丢失项的问题. 递归要用到一种数据结构栈. 批处理不可能实现这种栈的数据结构, 最后对这种算法也就不了了之.
qzwqzw兄对算法的研究确实够深的, 佩服, 刚来没仔细看代码, 有时间好好消化一下.
作者: jmz573515 时间: 2007-1-8 00:01
不知道哪位高手能不能用VBS写一个出来，谢谢！
作者: zhclvip 时间: 2007-1-26 07:40 标题: VBS也来捧场
dim msg,ss,ans
ss="12345"
For k=2 to len(ss)
Combine ss,k,""
next
arr=split(left(msg,Len(msg)-1),";")
for j=0 to ubound(arr)
rep="":res=0
for k=1 to len(arr(j))
rep=rep&mid(arr(j),k,1)&"+"
res=res + Cstr(mid(arr(j),k,1))
next
ans=ans&Cstr(j+1)&":"&Left(rep,Len(rep)-1)&"="&CStr(res)&vbCrLf
next
msgbox ans,0,"结果"
Sub Combine(sar,num,str)
If num=0 Then
msg=msg&str&";"
Else
For i=1 To Len(sar)
Call Combine(Right(sar,Len(sar)-i),num-1,str&Mid(sar,i,1))
Next
End If
End Sub
作者: jmz573515 时间: 2007-1-26 07:51
好，学习了。
作者: hngaoshou 时间: 2007-2-1 02:54
高
小弟要开始消化了