标题: [挑战]批处理求集合的交集与并集 [打印本页]
作者: zhouyongjun 时间: 2010-4-14 15:26 标题: [挑战]批处理求集合的交集与并集
如题
集合A、B为有限集,即A、B中元素为有限个数,且为正整数、最大值不超过100000。
A={1,[3,6],10,[20,30],[32,60],[200,3000],5000,[6000,8000],9000,9500}
B={2,5,31,[300,500],[8000,9000],9500}
求A∪B、A交非B 的集合。
A∪B={[1,6],10,[20,60],[200,3000],5000,[6000,9000],9500}
A交非B={1,[3,4],6,10,[20,30],[32,60],[200,299],[501,3000],5000,[6000,7999]}
要求:
1.结果如上例所示,连续元素必须采用闭区间(“[]”)表示;
2.同一集合中,各元素不能重复,例如不能{[2,3],[3,4]},应为{[2,4]};
3.上面集合所包含元素单纯为举例,不能就题解题;
4.方法不限,效率第一。
PS:闭区间即为包括边界;题中交代集合元素为正整数,所以(20,30)表示为[21,29],不考虑开区间
交集(∩):以属于A且属于B的元素为元素的集合称为A与B的交(集),记作A∩B(或B∩A),读作“A交B”(或“B交A”),即A∩B={x|x∈A,且x∈B}
并集(∪):以属于A或属于B的元素为元素的集合称为A与B的并(集),记作A∪B(或B∪A),读作“A并B”(或“B并A”),即A∪B={x|x∈A,或x∈B}
非B:为B的补集即1-100000中除开B以外的元素。
现把集合元素上限改为100000以降低难度;若不考虑上限也能解出,可忽略上限。
[ 本帖最后由 zhouyongjun 于 2010-4-14 20:16 编辑 ]
作者: namejm 时间: 2010-4-14 16:46
十多年没碰这些集合符号了,都有点忘记了这些符号的含义,楼主最好能在顶楼说一下各种符号的具体含义,比如我对 [20,30] 和 [20-30] 之间的差别都不甚了解。
另,这些集合中是否可能存在 (20,30) 这种不包含边界数值的情形?请一并明示。
作者: zhouyongjun 时间: 2010-4-14 17:01 标题: 回复 2楼 的帖子
[20-30]是我书写错误,现已改正
作者: namejm 时间: 2010-4-14 20:53
尝试着用纯批处理写了段代码。
思路:
1、把每个集合展开,列举集合中的每一个数,分别放入临时文件A.txt和B.txt,并求出每一集合中的最大数值max_A和max_B;
2、求合集时:
① 先把展开的数据放入同一临时文件tmpAB.txt,以tmpAB.txt中每行数据为变量名的一部分,对变量 num_%%i 赋值,从而得到变量名合集;
② 求出max_A和max_B中的最大值max,然后,检测从1到max的变量 num_%%i 是否已被赋值,把已经赋值过的数字输出到临时文件tmpAB↑.txt,从而得到升序排列的A和B的交集数据文本;
③ 读取tmpAB↑.txt中的数据,按照格式输出A和B的和集表达式;
3、求A交非B的交集时:
① 读取B.txt,对每一行数据赋值,赋值方法同第2点第②小点,然后,从1到max_B列举数值,把那些没有赋值过的数据输出到临时文件 —B.txt ;
② 用 findstr /beg:—B.txt A.txt 得到按照升序排列的A交非B的数据文本 tmpA—B↑.txt
③ 按照格式输出交集表达式
使用限制:
1、应为使用了 set /a 操作,可处理的数值范围为 1~2^32-1;
2、因为通过判断变量是否被赋值来排序,而系统有变量名个数的限制,从而导致实际能检测到的数值范围进一步缩小,具体范围尚未测试出来。
代码:- @echo off
- set A={1,[3,6],10,[20,30],[32,60],[200,3000],5000,[6000,8000],9000,9500}
- set B={2,5,31,[300,500],[8000,9000],9500}
- md tmp 2>nul
- pushd tmp 2>nul||exit
- setlocal enabledelayedexpansion
-
- echo %time%
- call :expand_num A %A:~1,-1%
- call :expand_num B %B:~1,-1%
-
- set /p=A∪B={<nul
- call :A∪B A B
-
- :—B
- :: 生成非B集合数据文本
- for /f "delims==" %%i in ('set num_ 2^>nul') do set %%i=
- for /f %%i in (B.txt) do set num_%%i=0
- (for /l %%i in (1,1,%max_B%) do (
- if not defined num_%%i echo %%i
- ))>—B.txt
- findstr /beg:—B.txt A.txt>tmpA—B↑.txt
-
- set /p=A交非B={<nul
- call :format_str A —B
- popd
- pause
- exit
-
- :A∪B
- :: 合并两文本,对每个数值赋值,然后从1开始检测哪些数值已经被赋值,由小到大写入临时文件
- copy %1.txt+%2.txt tmp%1%2.txt>nul
- if %max_A% gtr %max_B% (
- set max=%max_A%
- ) else set max=%max_B%
- for /f "delims==" %%i in ('set num_ 2^>nul') do set %%i=
- for /f %%i in (tmp%1%2.txt) do set num_%%i=0
- (for /l %%i in (1,1,%max%) do (
- if defined num_%%i echo %%i
- ))>tmp%1%2↑.txt
-
- :format_str
- :: 检测相邻两行数值的差值是否为1,若为1,则是连续数;若不为1,则数值不连续
- set /p num=<tmp%1%2↑.txt
- set begin=
- for /f %%i in (tmp%1%2↑.txt) do (
- if %%i neq !num! (
- set /a diff=%%i-!num!
- call :judge_range %%i !num! !diff!
- )
- set num=%%i
- )
- if defined begin (
- set /p=[!begin!,%num%]}<nul
- ) else set /p=%num%}<nul
- echo,&echo %time%
- goto :eof
-
- :expand_num
- :: 把字符串格式化,然后按顺序展开
- set begin=&set end=
- (for /f "tokens=1*" %%i in ("%*") do (
- for %%x in (%%j) do (
- set str=%%x
- if "!str:~0,1!"=="[" (
- set num_begin=!str:~1!&set begin=yes
- )
- if "!str:~-1!"=="]" (
- set num_end=!str:~0,-1!&set end=yes
- )
- if not defined begin echo %%x
- if defined end (
- for /l %%y in (!num_begin!,1,!num_end!) do echo %%y
- set begin=&set end=
- )
- set max_%1=%%x
- )
- ))>%1.txt
- goto :eof
-
- :judge_range
- :: 判断数值范围的临界值,根据临界值输出格式化字符串
- if %3 equ 1 (
- if not defined begin set begin=%2
- ) else (
- if defined begin (
- set /p=[!begin!,%2],<nul
- set begin=
- ) else (
- set /p=%2,<nul
- )
- )
- goto :eof
复制代码
由于有大量的 set /a 操作,速度比较慢,当数据量增大时尤其明显,暂时只把功能完成,尚未优化。
作者: 523066680 时间: 2010-4-14 21:59
我看到题目我畏惧了,看到寂寞大师出马了,我佩服了!
(关于寂寞二字属个人言论,并非真正本名,切勿模仿 )
[ 本帖最后由 523066680 于 2010-4-14 22:00 编辑 ]
作者: neorobin 时间: 2010-4-14 23:22
看到题目我起劲了, 回一个楼主, 关于 "非B", 对集合是补运算吧, 而 "非" 是逻辑运算
作者: neorobin 时间: 2010-4-14 23:34 标题: 回复 4楼 的帖子
提到了 "列举集合中的每一个数", 这样是不能高效的, 建议思路是, 将每个集合当成若干个子集来处理, 每个子集都有一个下限和一个上限, 求运算时, 依序对两个操作数 集合 的两个子集 的 4 个上下限进行比较, 依据运算生成结果 集合 的子集的上下限, 直到结果集合的全部子集上下限都生成, 最后再来一个 "相邻" 子集合并, 即 如 [3,19] 和 [20, 37] 就合并成 [3,37], 当然这个合并不是必要的, 其中子集处理中, 即使是一个 单独的数, 也可以看成一个集合, 如 1 看成 [1,1], 这样就去除了单独数的特殊性.
作者: zhouyongjun 时间: 2010-4-15 00:20 标题: 回复 7楼 的帖子
我也采用过这个办法,跟你的思路完全一样,以数组的形式用set排序,后面判断时感觉很复杂,只能求出部分情况。
这个问题我是从工作中延伸出来的,最初我便是采用定义变量法,思路和jm的略同但不采用临时文件,区间大时效率甚低,想了很久没好办法,特发出来大家讨论一下。
作者: netbenton 时间: 2010-4-15 02:35
有点难搞,只做了个并集的,效率不错,不知道是否通用,还待测试~~~- @echo off&setlocal enabledelayedexpansion
- set A={1,[3,6],10,[20,30],[32,60],[200,3000],5000,[6000,8000],9000,9500}
- set B={2,5,31,[300,500],[8000,9000],9500}
-
-
- ::拆分A 和 B的数据集
- set/a n=0,m=0
-
- set Av=!a:[=]!
- set Av=!Av:]="!
-
- for %%a in (%Av:~1,-1%) do (
- set a!n!=%%~a
- set/a n+=1
- )
-
- set Bv=!B:[=]!
- set Bv=!Bv:]="!
-
-
- for %%a in (%Bv:~1,-1%) do (
- set B!m!=%%~a
- set/a m+=1
- )
-
-
- ::设置上限
- set /a A!n!=2000000000
- set /a B!m!=2000000000
-
-
- ::根据a和b总项数来确定循环次,根据并集规则,进行判断重组
- set/a mn=m+n,n=0,m=0
- for /l %%a in (0,1,!mn!) do (
- for /f "tokens=1,2" %%m in ("!m! !n!") do (
- for /f "delims=," %%x in ("!A%%n!") do (
- for /f "delims=," %%o in ("!B%%m!") do (
-
- if %%x gtr %%o (set var=!B%%m!&set cur=m) else (set var=!A%%n!&set cur=n)
-
- for /f "tokens=1,2 delims=," %%1 in ("!var!,!var!") do (
- if !next! lss %%1 (
- if !fa! equ !end! (set aUb=!aUb!,!fa!) else (set aUb=!aUb!,[!fa!,!end!])
- set fa=%%1
- )
-
- set ben=%%1
- if !end! lss %%2 set end=%%2
- )))
-
- set /a !cur!=!cur!+1,next=end+1
- )
- )
- echo;并集计算:
- echo;AUB={!aUb:~2!}
-
- pause
复制代码
作者: batman 时间: 2010-4-15 09:53
我也跟一个并集的,自我感觉效率还可以:- @echo off&setlocal enabledelayedexpansion
- set "num=1 3-6 10 20-30 32-60 200-3000 5000 6000-8000 9000 9500 2 5 31 300-500 8000-9000 9500"
- for %%a in (%num%) do (
- for /f "tokens=1,2 delims=-" %%b in ("%%a") do (
- if "%%c" equ "" (
- if not defined _%%b set "_%%b=a"
- ) else (
- for /l %%d in (%%b,1,%%c) do if not defined _%%d set "_%%d=a"
- )
- )
- )
- for /l %%a in (1,1,10000) do (
- if defined _%%a (
- set "str=%%a"&set /a strs=str+1
- if not defined _!strs! (
- if not defined flag (
- set "nums=!nums!%%a,"
- ) else (
- set "nums=!nums!%%a],"&set "flag="
- )
- ) else (
- if not defined flag set "nums=!nums![%%a,"&set "flag=a"
- )
- )
- )
- echo A和B的并集:{!nums:~,-1!}&pause>nul
复制代码
[ 本帖最后由 batman 于 2010-4-15 09:55 编辑 ]
作者: netbenton 时间: 2010-4-15 13:07
交集处理,在并集处理的模版改为交集的处理而已,没有多少变化。- @echo off&setlocal enabledelayedexpansion
- set A={1,[3,6],10,[20,30],[32,60],[200,3000],5000,[6000,8002],9000,9500}
- set B={2,5,31,[45,49],55,[300,500],[8000,9000],9500}
- ::为了处理更多的情况,在楼主的例子上加了一些数据
-
-
- ::拆分A 和 B的数据集
- set/a n=0,m=0
-
- set Av=!a:[=]!
- set Av=!Av:]="!
-
- for %%a in (%Av:~1,-1%) do (
- set a!n!=%%~a
- set/a n+=1
- )
-
- set Bv=!B:[=]!
- set Bv=!Bv:]="!
-
-
- for %%a in (%Bv:~1,-1%) do (
- set B!m!=%%~a
- set/a m+=1
- )
-
-
- ::设置上限
- set /a A!n!=2000000000
- set /a B!m!=2000000000
-
-
- ::根据a和b总项数来确定循环次,根据交集规则,进行判断重组
- set/a mn=m+n,n=0,m=0
- for /l %%a in (0,1,!mn!) do (
- for /f "tokens=1,2" %%m in ("!m! !n!") do (
- for /f "delims=," %%x in ("!A%%n!") do (
- for /f "delims=," %%o in ("!B%%m!") do (
-
- if %%x gtr %%o (set var=!B%%m!&set cur=m) else (set var=!A%%n!&set cur=n)
-
- for /f "tokens=1,2 delims=," %%1 in ("!var!,!var!") do (
- if !end! geq %%1 (
- if !end! geq %%2 (
- if %%1 equ %%2 (set aNb=!aNb!,%%1) else (set aNb=!aNb!,[%%1,%%2])
- ) else (
- if %%1 equ !end! (set aNb=!aNb!,%%1) else (set aNb=!aNb!,[%%1,!end!])
- )
- )
- if !end! lss %%2 set ben=%%1&set end=%%2
-
- )))
-
- set /a !cur!=!cur!+1
- )
- )
-
- echo;交集计算:
- echo;aNb={!aNb:~1!}
-
- pause
复制代码
作者: zhouyongjun 时间: 2010-4-15 23:11
这两天学习gawk,尝试用gawk来处理一下,虽然是枚举速度还是比纯P的枚举快很多。
其实工作中我的上限不会超过10000,用gawk还是很快的。枚举还有个好处就是代码很健壮,比如不用考虑原集合里元素的顺序,同一集合出现重复元素的错误也可以避免。- @echo off
- ::下面代码只包括核心部分,其他处理已被忽略
-
- ::先把A、B转换成如下形式
- set A=1-1,3-6,10-10,20-30,32-60,200-3000,5000-5000,6000-8000,9000-9000,9500-9500
- set B=2-2,5-5,31-31,300-500,8000-9000,9500-9500
- ::求A交非B
- echo %A%,交非,%B%|gawk "BEGIN{FS=\"-\";RS=\",\";ORS=\",\"}{{if($0==\"交非\"){m=1}}{if(m!=1){for(i=$1;i<=$2;i++)a[i]=i}}{if(m==1){for(i=$1;i<=$2;i++)delete a[i]}}}END{x=asort(a,z);for(j=1;j<=x;j++){if(z[j-1]!=z[j]-1||j==1){print \"[\"z[j]}if(z[j+1]!=z[j]+1)print z[j]\"]\"}}"
- echo;
- ::求A∪B
- echo %A%,%B%|gawk "BEGIN{FS=\"-\";RS=\",\";ORS=\",\"}{{for(i=$1;i<=$2;i++)a[i]=i}}END{x=asort(a,z);for(j=1;j<=x;j++){if(z[j-1]!=z[j]-1||j==1){print \"[\"z[j]}if(z[j+1]!=z[j]+1)print z[j]\"]\"}}"
- echo;
- ::获取结果后去掉末尾的逗号,把用区间形式的独数重新表示
- pause
复制代码
作者: batman 时间: 2010-4-16 09:17
新方法:
先将A、B集合中的数字进行排序,结果中也包括了子集合符号,其中集合开始用*-表示,集合结束用-*表示,然后再进行判断,效率自是提高了很多:- @echo off&setlocal enabledelayedexpansion
- set "a=1 3-6 10 20-30 32-60 200-3000 5000 6000-8000 9000 9500 2 5 31 300-500 8000-9000 9500"
- for %%a in (%a:-= %) do (
- set /a n+=1
- for %%b in (%a:-= %) do if %%a geq %%b set /a _%%a+=1
- set ".!_%%a!=%%a"
- )
- for /l %%a in (1,1,%n%) do set "num=!num! !.%%a!"
- for %%a in (%a%) do (
- for /f "tokens=1,2 delims=-" %%b in ("%%a") do (
- if "%%c" neq "" (
- set "#%%b=%%b-"&set "#%%c=-%%c"
- ) else (
- set "#%%b=%%b"
- )
- )
- )
- set /p=排序后为:<nul&set /a n=0,m=1
- for %%a in (%num%) do set /p=!#%%a! <nul&set /a n+=1&set "$!n!=!#%%a!"
- for %%a in (%num%) do (
- set "str=!#%%a!"&set /a m+=1,strs=!str:-=!+1
- if "!str:-=!" equ "!str!" (
- if not defined #!strs! (
- if not defined flag set "nums=!nums!%%a,"
- ) else (
- if not defined flag set "nums=!nums![%%a,"&set "flag=a"
- )
- ) else (
- if "!str:~-1,1!" equ "-" (
- if not defined flag set "nums=!nums![%%a,"&set "flag=a"
- ) else (
- for %%b in (!m!) do (
- set "var=!$%%b!"
- if "!var:~,1!" neq "-" if not defined #!strs! if defined flag set "nums=!nums!%%a],"&set "flag="
- )
- )
- )
- )
- echo.&echo.&echo AB集合的并集为:{!nums:~,-1!}
- pause>nul
复制代码
[ 本帖最后由 batman 于 2010-4-16 09:58 编辑 ]
作者: qzwqzw 时间: 2010-4-16 15:46
哦,so sorry
我说的不是4的问题
而是以下的集合会出错
set "a=1 3-6 10 20-30 32-60 200-3000 5000 6000-7999 9002 9500 2 5 31 300-500 8000-9001 9500"
作者: neorobin 时间: 2010-4-16 20:52
先做个并集的, 以后再抽空做个交集的, 补集难度较小, 暂不支持元素重复, 逆序排列- @echo off&setlocal enabledelayedexpansion
- set /p debug=要以调试方式运行吗?[y/n][直接回车=n]:
-
- set LMin=1
- :getLUFlag
- set /a "LMin<<=1"
- if %LMin% lss 0 set /a UMax=-(LMin+1)&goto :endLUFlag
- goto :getLUFlag
- :endLUFlag
- echo 小于全集下限的标志数值=%LMin%, 大于全集上限的标志数值=%UMax%
-
- set "X={[-71,-54],[3,6],10,[20,30], [32,60],[200, 3000 ],5000,[6000,8000],9000,9500}"
- set "Y={-66,-33,2,5,31,[300,500],[8000,9000],9500, 9876, 9932}"
- (call :initSet X&call :outputSet X&call :initSet Y&call :outputSet Y)
- (call :Union X Y XUY&call :outputSet XUY)
- echo 任意键退出&pause>nul
- exit /b
-
- :initSet
- set "%1=!%1: =!" & set "%1=!%1:{=!" & set "%1=!%1:}=!"
- set "pnt%1=0" & set "flag=CN"
- for %%i in (!%1!) do (
- set "tt=%%i"
- if "!tt:~0,1!"=="[" (
- if "!flag!" equ "L" (echo 集合%1语法错误:%%i&pause&goto :err)
- set "flag=L"
- set /a pnt%1+=1&set "%1L!pnt%1!=!tt:~1!"
- ) else if "!tt:~-1!"=="]" (
- if "!flag!" neq "L" (echo 集合%1语法错误:%%i&pause&goto :err)
- set "flag=R"
- set "%1U!pnt%1!=!tt:~0,-1!"
- ) else if "!flag!" equ "L" (echo 集合%1语法错误:%%i&pause&goto :err
- ) else set /a pnt%1+=1&set "%1L!pnt%1!=!tt!"&set "%1U!pnt%1!=!tt!"&set "flag=CN"
- )
- set /a pnt%1+=1&set "%1L!pnt%1!=!UMax!"&set "%1U!pnt%1!=!UMax!"
- exit /b
-
- :Union A B A∪B
- (call :copySet %1 A&call :copySet %2 B)
- set /a "pntA=1,pntB=1,pntR=0"&(set RL0=%LMin%&set RU0=%LMin%)
-
- :UnionLoop
- if "!RL%pntR%!"=="!UMax!" echo 并集完成&goto :returnUnionValue
- :UnionSch1
- if !AU%pntA%! leq !RU%pntR%! set /a "pntA+=1"&goto :UnionSch1
- if !AL%pntA%! leq !RU%pntR%! set "RU!pntR!=!AU%pntA%!"
- :UnionSch2
- if !BU%pntB%! leq !RU%pntR%! set /a "pntB+=1"&goto :UnionSch2
- if !BL%pntB%! leq !RU%pntR%! set "RU!pntR!=!BU%pntB%!"
-
- set "intersec=Y"
- if !AL%pntA%! gtr !BU%pntB%! (set "intersec=N") else (
- if !BL%pntB%! gtr !AU%pntA%! set "intersec=N")
-
- set /a pntR+=1
- (call :min !AL%pntA%! !BL%pntB%! RL!pntR!)
- if "!intersec!"=="Y" (call :max !AU%pntA%! !BU%pntB%! RU!pntR!) else (
- call :min !AU%pntA%! !BU%pntB%! RU!pntR!)
-
- if /i "!debug!"=="y" (
- echo pntA=!pntA!,pntB=!pntB!,pntR=!pntR!,intersec=!intersec!
- call :outputSet R
- )
- goto :UnionLoop
-
- :returnUnionValue
- (call :copySet R %3)
- exit /b
-
- :copySet src dest
- for /l %%i in (1 1 10000) do (
- if "!%1L%%i!"=="" (exit /b) else (set %2L%%i=!%1L%%i!&set %2U%%i=!%1U%%i!)
- )
- exit /b
-
- :min a b min (a,b 以串值调用, min 以变量名调用)
- if %1 lss %2 (set %3=%1) else (set %3=%2)
- exit /b
-
- :max a b max (a,b 以串值调用, max 以变量名调用)
- if %1 gtr %2 (set %3=%1) else (set %3=%2)
- exit /b
-
- :outputSet
- set /p=%1=<nul
- for /l %%i in (1 1 10000) do (
- if "!%1L%%i!"=="" (echo &exit /b) else set /p=[!%1L%%i!,!%1U%%i!],<nul
- )
- exit /b
-
- :err
- echo 错误, 任意键退出&pause
- exit /b
复制代码
作者: sgaizxt001 时间: 2010-4-17 08:48
哎,看帖不仔细。悔过
[ 本帖最后由 sgaizxt001 于 2010-4-17 09:07 编辑 ]
作者: neorobin 时间: 2010-4-17 21:52
交, 并, 补 完全求解, 但不考虑集合描述中 元素重复, 逆序排列- @echo off&setlocal enabledelayedexpansion
- (set LOut=')&(set UOut=Z)& rem 在集合最后面加一个假子集 [UOut, UOut] 作为尾部标志
- rem echo 小于全集下限的标志=%LOut%, 大于全集上限的标志=%UOut%
- call :getUniverseLU& rem echo 全集U={[!universeL!,!universeU!]}
-
- set "I={[1,100000]}"& rem 题目指定的小全集
- set "X={1,[3,6],10,[20,30],[32,60],[200,3000],5000,[6000,8000],9000,9500}"
- set "Y={2,5,31,[300,500],[8000,9000],9500}"
- (call :initSet I) & (call :initSet X) & (call :initSet Y)
- (call :outputSet X) & (call :outputSet Y)
-
- call :Union X Y X∪Y
- call :Complement Y Y1
- call :Inter I Y1 _Y
- call :Inter X _Y X∩_Y
-
- call :Simplify X∪Y
- call :outputSet X∪Y
- call :Simplify X∩_Y
- call :outputSet X∩_Y
-
- echo 任意键退出&pause>nul
- exit /b
-
- :Union A B A∪B
- (call :copySet %1 A&call :copySet %2 B&call :clearSet R)
- set /a "pntA=1,pntB=1,pntR=0"&(set RL0=%LOut%&set RU0=%LOut%)
- :UnionLoop
- if "!RL%pntR%!"=="!UOut!" (call :copySet R %3)&exit /b
- :UnionSch1
- if !AU%pntA%! leq !RU%pntR%! set /a "pntA+=1"&goto :UnionSch1
- if !AL%pntA%! leq !RU%pntR%! set "RU!pntR!=!AU%pntA%!"
- :UnionSch2
- if !BU%pntB%! leq !RU%pntR%! set /a "pntB+=1"&goto :UnionSch2
- if !BL%pntB%! leq !RU%pntR%! set "RU!pntR!=!BU%pntB%!"
-
- set "intersec=Y"
- if !AL%pntA%! gtr !BU%pntB%! (set "intersec=N") else (
- if !BL%pntB%! gtr !AU%pntA%! set "intersec=N")
- set /a "pntR+=1"
- (call :min !AL%pntA%! !BL%pntB%! RL!pntR!)
- if "!intersec!"=="Y" (call :max !AU%pntA%! !BU%pntB%! RU!pntR!) else (
- call :min !AU%pntA%! !BU%pntB%! RU!pntR!)
- goto :UnionLoop
- exit /b
-
- :Inter A B A∩B
- (call :copySet %1 A&call :copySet %2 B&call :clearSet R)
- set /a "pntA=1,pntB=1,pntR=0"&(set RL0=%LOut%&set RU0=%LOut%)
- :InterLoop
- if "!RL%pntR%!"=="!UOut!" (call :copySet R %3)&exit /b
- :InterSch1
- if !AU%pntA%! lss !BL%pntB%! set /a "pntA+=1"&goto :InterSch1
- :InterSch2
- if !BU%pntB%! lss !AL%pntA%! set /a "pntB+=1"&goto :InterSch2
- if !AU%pntA%! lss !BL%pntB%! goto :InterSch1
-
- set /a "pntR+=1"
- (call :max !AL%pntA%! !BL%pntB%! RL!pntR!)
- (call :min !AU%pntA%! !BU%pntB%! RU!pntR!)
-
- if !AU%pntA%! lss !BU%pntB%! (set /a "pntA+=1") else set /a "pntB+=1"
- goto :InterLoop
- exit /b
-
- :copySet src dest
- call :clearSet %2
- for /l %%i in (1 1 10000) do (
- if "!%1L%%i!"=="" (exit /b) else (set %2L%%i=!%1L%%i!&set %2U%%i=!%1U%%i!)
- )
- exit /b
-
- :min a b min (a,b 以串值调用, min 以变量名调用)
- if %1 lss %2 (set %3=%1) else (set %3=%2)
- exit /b
-
- :max a b max (a,b 以串值调用, max 以变量名调用)
- if %1 gtr %2 (set %3=%1) else (set %3=%2)
- exit /b
-
- :outputSet
- (set lastout=')
- set /p=%1={<nul
- if "!%1L1!"=="" echo }&exit /b
- for /l %%i in (1 1 10000) do (
- if "!%1L%%i!"=="" (if %%i neq 1 (echo }) else echo })&exit /b
- if "!%1L%%i!"=="!UOut!" (
- (if %%i neq 1 (echo }) else echo })&exit /b
- ) else if !%1L%%i! gtr !lastout! (
- if !%1L%%i! neq !%1U%%i! (
- set /p=[!%1L%%i!,!%1U%%i!],<nul
- ) else set /p=!%1L%%i!,<nul
- (set lastout=!%1U%%i!)
- )
- )
- exit /b
-
- :clearSet
- for /l %%i in (1 1 10000) do (
- if "!%1L%%i!"=="" (exit /b) else (set %1L%%i=&set %1U%%i=)
- )
- exit /b
-
- :err
- echo 错误, 任意键退出&pause
- exit /b
-
- :getUniverseLU
- set "universeL=1"
- :get_uniLU
- set /a "universeL<<=1"
- if %universeL% lss 0 (set /a "universeU=-(universeL+1), universeL=0"&exit /b) else goto :get_uniLU
- exit /b
-
- :Complement A compA
- (call :copySet %1 A&call :clearSet R)
- (set /a pntA=0, pntN=pntA+1, pntR=0)
- if !AL1! neq !universeL! (
- set tL=!universeL!& set /a "tU=AL1-1"
- ) else (
- set /a "pntA+=1"
- if !AU1! lss !universeU! (
- set /a "tL=AU1+1"
- if "!AL2!" neq "!UOut!" (set /a tU=AL2-1) else set "tU=!universeU!"
- ) else ( rem 补为空
- (set /a "pntR+=1"&set RL!pntR!=!UOut!&set RU!pntR!=!UOut!)&(call :copySet R %2)&exit /b
- )
- )
- :ComplementLoop
- if !tU! geq !tL! (
- (set /a "pntR+=1"&set RL!pntR!=!tL!&set RU!pntR!=!tU!)
- if !tU! geq !universeU! (
- (set /a "pntR+=1"&set RL!pntR!=!UOut!&set RU!pntR!=!UOut!)&(call :copySet R %2)&exit /b
- )
- )
- set /a "pntA+=1, pntN=pntA+1"
- set /a "tL=AU!pntA!+1"
- if !AL%pntN%!==!UOut! (set "tU=!universeU!") else set /a "tU=!AL%pntN%!-1"
- goto :ComplementLoop
- exit /b
-
- :Simplify A 仅用于最后输出之前(不再做任何运算), 将相邻子集合并
- (call :copySet %1 A)&(set /a pntA=0, pntN=pntA+1)&set "AU0=!LOut!"
- :SimplifyLoop
- if "!AL%pntN%!"=="!UOut!" (call :copySet A %1)&exit /b
- set /a "tt=AL!pntN!-1"
- if "!AU%pntA%!" equ "!tt!" (
- set "AU!pntA!=!AU%pntN%!"
- set /a "pntN+=1"
- ) else set /a "pntA=pntN,pntN+=1"
- goto :SimplifyLoop
- exit /b
-
- :initSet
- set "%1=!%1: =!" & set "%1=!%1:{=!" & set "%1=!%1:}=!"
- set "pnt%1=0" & set "flag=CN"
- for %%i in (!%1!) do (
- set "tt=%%i"
- if "!tt:~0,1!"=="[" (
- if "!flag!" equ "L" (echo 集合%1语法错误:%%i&pause&goto :err)
- set "flag=L"
- set /a pnt%1+=1&set "%1L!pnt%1!=!tt:~1!"
- ) else if "!tt:~-1!"=="]" (
- if "!flag!" neq "L" (echo 集合%1语法错误:%%i&pause&goto :err)
- set "flag=R"
- set "%1U!pnt%1!=!tt:~0,-1!"
- ) else if "!flag!" equ "L" (echo 集合%1语法错误:%%i&pause&goto :err
- ) else set /a pnt%1+=1&set "%1L!pnt%1!=!tt!"&set "%1U!pnt%1!=!tt!"&set "flag=CN"
- )
- set /a pnt%1+=1&set "%1L!pnt%1!=!UOut!"&set "%1U!pnt%1!=!UOut!"
- exit /b
复制代码
[ 本帖最后由 neorobin 于 2010-4-17 22:35 编辑 ]
欢迎光临 批处理之家 (http://bbs.bathome.net/) |
Powered by Discuz! 7.2 |