Board logo

标题: [挑战]批处理求集合的交集与并集 [打印本页]

作者: 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、因为通过判断变量是否被赋值来排序,而系统有变量名个数的限制,从而导致实际能检测到的数值范围进一步缩小,具体范围尚未测试出来。

  代码:
  1. @echo off
  2. set A={1,[3,6],10,[20,30],[32,60],[200,3000],5000,[6000,8000],9000,9500}
  3. set B={2,5,31,[300,500],[8000,9000],9500}
  4. md tmp 2>nul
  5. pushd tmp 2>nul||exit
  6. setlocal enabledelayedexpansion
  7. echo %time%
  8. call :expand_num A %A:~1,-1%
  9. call :expand_num B %B:~1,-1%
  10. set /p=A∪B={<nul
  11. call :A∪B A B
  12. :—B
  13. :: 生成非B集合数据文本
  14. for /f "delims==" %%i in ('set num_ 2^>nul') do set %%i=
  15. for /f %%i in (B.txt) do set num_%%i=0
  16. (for /l %%i in (1,1,%max_B%) do (
  17.     if not defined num_%%i echo %%i
  18. ))>—B.txt
  19. findstr /beg:—B.txt A.txt>tmpA—B↑.txt
  20. set /p=A交非B={<nul
  21. call :format_str A —B
  22. popd
  23. pause
  24. exit
  25. :A∪B
  26. :: 合并两文本,对每个数值赋值,然后从1开始检测哪些数值已经被赋值,由小到大写入临时文件
  27. copy %1.txt+%2.txt tmp%1%2.txt>nul
  28. if %max_A% gtr %max_B% (
  29.     set max=%max_A%
  30. ) else set max=%max_B%
  31. for /f "delims==" %%i in ('set num_ 2^>nul') do set %%i=
  32. for /f %%i in (tmp%1%2.txt) do set num_%%i=0
  33. (for /l %%i in (1,1,%max%) do (
  34.     if defined num_%%i echo %%i
  35. ))>tmp%1%2↑.txt
  36. :format_str
  37. :: 检测相邻两行数值的差值是否为1,若为1,则是连续数;若不为1,则数值不连续
  38. set /p num=<tmp%1%2↑.txt
  39. set begin=
  40. for /f %%i in (tmp%1%2↑.txt) do (
  41.     if %%i neq !num! (
  42.         set /a diff=%%i-!num!
  43.         call :judge_range %%i !num! !diff!
  44.     )
  45.     set num=%%i
  46. )
  47. if defined begin (
  48.     set /p=[!begin!,%num%]}<nul
  49. ) else set /p=%num%}<nul
  50. echo,&echo %time%
  51. goto :eof
  52. :expand_num
  53. :: 把字符串格式化,然后按顺序展开
  54. set begin=&set end=
  55. (for /f "tokens=1*" %%i in ("%*") do (
  56.     for %%x in (%%j) do (
  57.         set str=%%x
  58.         if "!str:~0,1!"=="[" (
  59.             set num_begin=!str:~1!&set begin=yes
  60.         )
  61.         if "!str:~-1!"=="]" (
  62.             set num_end=!str:~0,-1!&set end=yes
  63.         )
  64.         if not defined begin echo %%x
  65.         if defined end (
  66.             for /l %%y in (!num_begin!,1,!num_end!) do echo %%y
  67.             set begin=&set end=
  68.         )
  69.         set max_%1=%%x
  70.     )
  71. ))>%1.txt
  72. goto :eof
  73. :judge_range
  74. :: 判断数值范围的临界值,根据临界值输出格式化字符串
  75. if %3 equ 1 (
  76.     if not defined begin set begin=%2
  77. ) else (
  78.     if defined begin (
  79.         set /p=[!begin!,%2],<nul
  80.         set begin=
  81.     ) else (
  82.         set /p=%2,<nul
  83.     )
  84. )
  85. 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

有点难搞,只做了个并集的,效率不错,不知道是否通用,还待测试~~~
  1. @echo off&setlocal enabledelayedexpansion
  2. set A={1,[3,6],10,[20,30],[32,60],[200,3000],5000,[6000,8000],9000,9500}
  3. set B={2,5,31,[300,500],[8000,9000],9500}
  4. ::拆分A 和 B的数据集
  5. set/a n=0,m=0
  6. set Av=!a:[=]!
  7. set Av=!Av:]="!
  8. for %%a in (%Av:~1,-1%) do (
  9. set a!n!=%%~a
  10. set/a n+=1
  11. )
  12. set Bv=!B:[=]!
  13. set Bv=!Bv:]="!
  14. for %%a in (%Bv:~1,-1%) do (
  15. set B!m!=%%~a
  16. set/a m+=1
  17. )
  18. ::设置上限
  19. set /a A!n!=2000000000
  20. set /a B!m!=2000000000
  21. ::根据a和b总项数来确定循环次,根据并集规则,进行判断重组
  22. set/a mn=m+n,n=0,m=0
  23. for /l %%a in (0,1,!mn!) do (
  24. for /f "tokens=1,2" %%m in ("!m! !n!") do (
  25. for /f "delims=," %%x in ("!A%%n!") do (
  26. for /f "delims=," %%o in ("!B%%m!") do (
  27. if %%x gtr %%o (set var=!B%%m!&set cur=m) else (set var=!A%%n!&set cur=n)
  28. for /f "tokens=1,2 delims=," %%1 in ("!var!,!var!") do (
  29. if !next! lss %%1 (
  30. if !fa! equ !end! (set aUb=!aUb!,!fa!) else (set aUb=!aUb!,[!fa!,!end!])
  31. set fa=%%1
  32. )
  33. set ben=%%1
  34. if !end! lss %%2 set end=%%2
  35. )))
  36. set /a !cur!=!cur!+1,next=end+1
  37. )
  38. )
  39. echo;并集计算:
  40. echo;AUB={!aUb:~2!}
  41. pause
复制代码

作者: batman    时间: 2010-4-15 09:53

我也跟一个并集的,自我感觉效率还可以:
  1. @echo off&setlocal enabledelayedexpansion
  2. 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"
  3. for %%a in (%num%) do (
  4.     for /f "tokens=1,2 delims=-" %%b in ("%%a") do (
  5.         if "%%c" equ "" (
  6.            if not defined _%%b set "_%%b=a"
  7.            ) else (
  8.            for /l %%d in (%%b,1,%%c) do if not defined _%%d set "_%%d=a"
  9.         )
  10.     )
  11. )
  12. for /l %%a in (1,1,10000) do (
  13.     if defined _%%a (
  14.        set "str=%%a"&set /a strs=str+1
  15.        if not defined _!strs! (
  16.           if not defined flag (
  17.              set "nums=!nums!%%a,"
  18.              ) else (
  19.              set "nums=!nums!%%a],"&set "flag="
  20.           )
  21.           ) else (
  22.           if not defined flag set "nums=!nums![%%a,"&set "flag=a"
  23.        )
  24.     )
  25. )
  26. echo A和B的并集:{!nums:~,-1!}&pause>nul
复制代码

[ 本帖最后由 batman 于 2010-4-15 09:55 编辑 ]
作者: netbenton    时间: 2010-4-15 13:07

交集处理,在并集处理的模版改为交集的处理而已,没有多少变化。
  1. @echo off&setlocal enabledelayedexpansion
  2. set A={1,[3,6],10,[20,30],[32,60],[200,3000],5000,[6000,8002],9000,9500}
  3. set B={2,5,31,[45,49],55,[300,500],[8000,9000],9500}
  4. ::为了处理更多的情况,在楼主的例子上加了一些数据
  5. ::拆分A 和 B的数据集
  6. set/a n=0,m=0
  7. set Av=!a:[=]!
  8. set Av=!Av:]="!
  9. for %%a in (%Av:~1,-1%) do (
  10. set a!n!=%%~a
  11. set/a n+=1
  12. )
  13. set Bv=!B:[=]!
  14. set Bv=!Bv:]="!
  15. for %%a in (%Bv:~1,-1%) do (
  16. set B!m!=%%~a
  17. set/a m+=1
  18. )
  19. ::设置上限
  20. set /a A!n!=2000000000
  21. set /a B!m!=2000000000
  22. ::根据a和b总项数来确定循环次,根据交集规则,进行判断重组
  23. set/a mn=m+n,n=0,m=0
  24. for /l %%a in (0,1,!mn!) do (
  25. for /f "tokens=1,2" %%m in ("!m! !n!") do (
  26. for /f "delims=," %%x in ("!A%%n!") do (
  27. for /f "delims=," %%o in ("!B%%m!") do (
  28. if %%x gtr %%o (set var=!B%%m!&set cur=m) else (set var=!A%%n!&set cur=n)
  29. for /f "tokens=1,2 delims=," %%1 in ("!var!,!var!") do (
  30. if !end! geq %%1 (
  31. if !end! geq %%2 (
  32. if %%1 equ %%2 (set aNb=!aNb!,%%1) else (set aNb=!aNb!,[%%1,%%2])
  33. ) else (
  34. if %%1 equ !end! (set aNb=!aNb!,%%1) else (set aNb=!aNb!,[%%1,!end!])
  35. )
  36. )
  37. if !end! lss %%2 set ben=%%1&set end=%%2
  38. )))
  39. set /a !cur!=!cur!+1
  40. )
  41. )
  42. echo;交集计算:
  43. echo;aNb={!aNb:~1!}
  44. pause
复制代码

作者: zhouyongjun    时间: 2010-4-15 23:11

这两天学习gawk,尝试用gawk来处理一下,虽然是枚举速度还是比纯P的枚举快很多。
其实工作中我的上限不会超过10000,用gawk还是很快的。枚举还有个好处就是代码很健壮,比如不用考虑原集合里元素的顺序,同一集合出现重复元素的错误也可以避免。
  1. @echo off
  2. ::下面代码只包括核心部分,其他处理已被忽略
  3. ::先把A、B转换成如下形式
  4. set A=1-1,3-6,10-10,20-30,32-60,200-3000,5000-5000,6000-8000,9000-9000,9500-9500
  5. set B=2-2,5-5,31-31,300-500,8000-9000,9500-9500
  6. ::求A交非B
  7. 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]\"]\"}}"
  8. echo;
  9. ::求A∪B
  10. 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]\"]\"}}"
  11. echo;
  12. ::获取结果后去掉末尾的逗号,把用区间形式的独数重新表示
  13. pause
复制代码

作者: batman    时间: 2010-4-16 09:17

新方法:
  先将A、B集合中的数字进行排序,结果中也包括了子集合符号,其中集合开始用*-表示,集合结束用-*表示,然后再进行判断,效率自是提高了很多:
  1. @echo off&setlocal enabledelayedexpansion
  2. 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"
  3. for %%a in (%a:-= %) do (
  4.     set /a n+=1
  5.     for %%b in (%a:-= %) do if %%a geq %%b set /a _%%a+=1
  6.   set ".!_%%a!=%%a"
  7. )
  8. for /l %%a in (1,1,%n%) do set "num=!num! !.%%a!"
  9. for %%a in (%a%) do (
  10.     for /f "tokens=1,2 delims=-" %%b in ("%%a") do (
  11.         if "%%c" neq "" (
  12.            set "#%%b=%%b-"&set "#%%c=-%%c"
  13.            ) else (
  14.            set "#%%b=%%b"
  15.         )
  16.     )
  17. )
  18. set /p=排序后为:<nul&set /a n=0,m=1
  19. for %%a in (%num%) do set /p=!#%%a! <nul&set /a n+=1&set "$!n!=!#%%a!"
  20. for %%a in (%num%) do (
  21.     set "str=!#%%a!"&set /a m+=1,strs=!str:-=!+1
  22.     if "!str:-=!" equ "!str!" (
  23.        if not defined #!strs! (
  24.           if not defined flag set "nums=!nums!%%a,"
  25.           ) else (
  26.           if not defined flag set "nums=!nums![%%a,"&set "flag=a"
  27.        )
  28.        ) else (
  29.        if "!str:~-1,1!" equ "-" (
  30.           if not defined flag set "nums=!nums![%%a,"&set "flag=a"
  31.           ) else (
  32.           for %%b in (!m!) do (
  33.               set "var=!$%%b!"
  34.               if "!var:~,1!" neq "-" if not defined #!strs! if defined flag set "nums=!nums!%%a],"&set "flag="
  35.           )
  36.        )
  37.     )
  38. )
  39. echo.&echo.&echo AB集合的并集为:{!nums:~,-1!}
  40. 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

先做个并集的, 以后再抽空做个交集的, 补集难度较小, 暂不支持元素重复, 逆序排列
  1. @echo off&setlocal enabledelayedexpansion
  2. set /p debug=要以调试方式运行吗?[y/n][直接回车=n]:
  3. set LMin=1
  4. :getLUFlag
  5.   set /a "LMin<<=1"
  6.   if %LMin% lss 0 set /a UMax=-(LMin+1)&goto :endLUFlag
  7. goto :getLUFlag
  8. :endLUFlag
  9. echo 小于全集下限的标志数值=%LMin%, 大于全集上限的标志数值=%UMax%
  10. set "X={[-71,-54],[3,6],10,[20,30],  [32,60],[200,  3000  ],5000,[6000,8000],9000,9500}"
  11. set "Y={-66,-33,2,5,31,[300,500],[8000,9000],9500, 9876, 9932}"
  12. (call :initSet X&call :outputSet X&call :initSet Y&call :outputSet Y)
  13. (call :Union X Y XUY&call :outputSet XUY)
  14. echo 任意键退出&pause>nul
  15. exit /b
  16. :initSet
  17. set "%1=!%1: =!" & set "%1=!%1:{=!" & set "%1=!%1:}=!"
  18. set "pnt%1=0" & set "flag=CN"
  19. for %%i in (!%1!) do (
  20.   set "tt=%%i"
  21.   if "!tt:~0,1!"=="[" (
  22.     if "!flag!" equ "L" (echo 集合%1语法错误:%%i&pause&goto :err)
  23.     set "flag=L"
  24.     set /a pnt%1+=1&set "%1L!pnt%1!=!tt:~1!"
  25.   ) else if "!tt:~-1!"=="]" (
  26.     if "!flag!" neq "L" (echo 集合%1语法错误:%%i&pause&goto :err)
  27.     set "flag=R"
  28.     set "%1U!pnt%1!=!tt:~0,-1!"  
  29.   ) else if "!flag!" equ "L"  (echo 集合%1语法错误:%%i&pause&goto :err
  30.   ) else set /a pnt%1+=1&set "%1L!pnt%1!=!tt!"&set "%1U!pnt%1!=!tt!"&set "flag=CN"
  31. )
  32. set /a pnt%1+=1&set "%1L!pnt%1!=!UMax!"&set "%1U!pnt%1!=!UMax!"
  33. exit /b
  34. :Union A B A∪B
  35. (call :copySet %1 A&call :copySet %2 B)
  36. set /a "pntA=1,pntB=1,pntR=0"&(set RL0=%LMin%&set RU0=%LMin%)
  37. :UnionLoop
  38. if "!RL%pntR%!"=="!UMax!" echo 并集完成&goto :returnUnionValue
  39. :UnionSch1
  40. if !AU%pntA%! leq !RU%pntR%! set /a "pntA+=1"&goto :UnionSch1
  41. if !AL%pntA%! leq !RU%pntR%! set "RU!pntR!=!AU%pntA%!"
  42. :UnionSch2
  43. if !BU%pntB%! leq !RU%pntR%! set /a "pntB+=1"&goto :UnionSch2
  44. if !BL%pntB%! leq !RU%pntR%! set "RU!pntR!=!BU%pntB%!"
  45. set "intersec=Y"
  46. if !AL%pntA%! gtr !BU%pntB%! (set "intersec=N") else (
  47.   if !BL%pntB%! gtr !AU%pntA%! set "intersec=N")
  48. set /a pntR+=1
  49. (call :min !AL%pntA%! !BL%pntB%! RL!pntR!)
  50. if "!intersec!"=="Y" (call :max !AU%pntA%! !BU%pntB%! RU!pntR!) else (
  51.   call :min !AU%pntA%! !BU%pntB%! RU!pntR!)
  52. if /i "!debug!"=="y" (
  53.   echo pntA=!pntA!,pntB=!pntB!,pntR=!pntR!,intersec=!intersec!
  54.   call :outputSet R
  55. )
  56. goto :UnionLoop
  57. :returnUnionValue
  58. (call :copySet R %3)
  59. exit /b
  60. :copySet src dest
  61. for /l %%i in (1 1 10000) do (
  62.   if "!%1L%%i!"=="" (exit /b) else (set %2L%%i=!%1L%%i!&set %2U%%i=!%1U%%i!)
  63. )
  64. exit /b
  65. :min a b min (a,b 以串值调用, min 以变量名调用)
  66. if %1 lss %2 (set %3=%1) else (set %3=%2)
  67. exit /b
  68. :max a b max (a,b 以串值调用, max 以变量名调用)
  69. if %1 gtr %2 (set %3=%1) else (set %3=%2)
  70. exit /b
  71. :outputSet
  72. set /p=%1=<nul
  73. for /l %%i in (1 1 10000) do (
  74.   if "!%1L%%i!"=="" (echo  &exit /b) else set /p=[!%1L%%i!,!%1U%%i!],<nul
  75. )
  76. exit /b
  77. :err
  78. echo 错误, 任意键退出&pause
  79. exit /b
复制代码

作者: sgaizxt001    时间: 2010-4-17 08:48

哎,看帖不仔细。悔过

[ 本帖最后由 sgaizxt001 于 2010-4-17 09:07 编辑 ]
作者: neorobin    时间: 2010-4-17 21:52

交, 并, 补 完全求解, 但不考虑集合描述中 元素重复, 逆序排列
  1. @echo off&setlocal enabledelayedexpansion
  2. (set LOut=')&(set UOut=Z)& rem 在集合最后面加一个假子集 [UOut, UOut] 作为尾部标志
  3. rem echo 小于全集下限的标志=%LOut%, 大于全集上限的标志=%UOut%
  4. call :getUniverseLU& rem echo 全集U={[!universeL!,!universeU!]}
  5. set "I={[1,100000]}"& rem 题目指定的小全集
  6. set "X={1,[3,6],10,[20,30],[32,60],[200,3000],5000,[6000,8000],9000,9500}"
  7. set "Y={2,5,31,[300,500],[8000,9000],9500}"
  8. (call :initSet I) & (call :initSet X) & (call :initSet Y)
  9. (call :outputSet X) & (call :outputSet Y)
  10. call :Union X Y X∪Y
  11. call :Complement Y Y1
  12. call :Inter I Y1 _Y
  13. call :Inter X _Y X∩_Y
  14. call :Simplify X∪Y
  15. call :outputSet X∪Y
  16. call :Simplify X∩_Y
  17. call :outputSet X∩_Y
  18. echo 任意键退出&pause>nul
  19. exit /b
  20. :Union A B A∪B
  21. (call :copySet %1 A&call :copySet %2 B&call :clearSet R)
  22. set /a "pntA=1,pntB=1,pntR=0"&(set RL0=%LOut%&set RU0=%LOut%)
  23. :UnionLoop
  24. if "!RL%pntR%!"=="!UOut!" (call :copySet R %3)&exit /b
  25. :UnionSch1
  26. if !AU%pntA%! leq !RU%pntR%! set /a "pntA+=1"&goto :UnionSch1
  27. if !AL%pntA%! leq !RU%pntR%! set "RU!pntR!=!AU%pntA%!"
  28. :UnionSch2
  29. if !BU%pntB%! leq !RU%pntR%! set /a "pntB+=1"&goto :UnionSch2
  30. if !BL%pntB%! leq !RU%pntR%! set "RU!pntR!=!BU%pntB%!"
  31. set "intersec=Y"
  32. if !AL%pntA%! gtr !BU%pntB%! (set "intersec=N") else (
  33.   if !BL%pntB%! gtr !AU%pntA%! set "intersec=N")
  34. set /a "pntR+=1"
  35. (call :min !AL%pntA%! !BL%pntB%! RL!pntR!)
  36. if "!intersec!"=="Y" (call :max !AU%pntA%! !BU%pntB%! RU!pntR!) else (
  37.   call :min !AU%pntA%! !BU%pntB%! RU!pntR!)
  38. goto :UnionLoop
  39. exit /b
  40. :Inter A B A∩B
  41. (call :copySet %1 A&call :copySet %2 B&call :clearSet R)
  42. set /a "pntA=1,pntB=1,pntR=0"&(set RL0=%LOut%&set RU0=%LOut%)
  43. :InterLoop
  44. if "!RL%pntR%!"=="!UOut!" (call :copySet R %3)&exit /b
  45. :InterSch1
  46. if !AU%pntA%! lss !BL%pntB%! set /a "pntA+=1"&goto :InterSch1
  47. :InterSch2
  48. if !BU%pntB%! lss !AL%pntA%! set /a "pntB+=1"&goto :InterSch2
  49. if !AU%pntA%! lss !BL%pntB%! goto :InterSch1
  50. set /a "pntR+=1"
  51. (call :max !AL%pntA%! !BL%pntB%! RL!pntR!)
  52. (call :min !AU%pntA%! !BU%pntB%! RU!pntR!)
  53. if !AU%pntA%! lss !BU%pntB%! (set /a "pntA+=1") else set /a "pntB+=1"
  54. goto :InterLoop
  55. exit /b
  56. :copySet src dest
  57. call :clearSet %2
  58. for /l %%i in (1 1 10000) do (
  59.   if "!%1L%%i!"=="" (exit /b) else (set %2L%%i=!%1L%%i!&set %2U%%i=!%1U%%i!)
  60. )
  61. exit /b
  62. :min a b min (a,b 以串值调用, min 以变量名调用)
  63. if %1 lss %2 (set %3=%1) else (set %3=%2)
  64. exit /b
  65. :max a b max (a,b 以串值调用, max 以变量名调用)
  66. if %1 gtr %2 (set %3=%1) else (set %3=%2)
  67. exit /b
  68. :outputSet
  69. (set lastout=')
  70. set /p=%1={<nul
  71. if "!%1L1!"=="" echo }&exit /b
  72. for /l %%i in (1 1 10000) do (
  73.   if "!%1L%%i!"=="" (if %%i neq 1 (echo }) else echo })&exit /b
  74.   if "!%1L%%i!"=="!UOut!" (
  75.     (if %%i neq 1 (echo }) else echo })&exit /b
  76.   ) else if !%1L%%i! gtr !lastout! (
  77.     if !%1L%%i! neq !%1U%%i! (
  78.       set /p=[!%1L%%i!,!%1U%%i!],<nul
  79.     ) else set /p=!%1L%%i!,<nul
  80.     (set lastout=!%1U%%i!)
  81.   )
  82. )
  83. exit /b
  84. :clearSet
  85. for /l %%i in (1 1 10000) do (
  86.   if "!%1L%%i!"=="" (exit /b) else (set %1L%%i=&set %1U%%i=)
  87. )
  88. exit /b
  89. :err
  90. echo 错误, 任意键退出&pause
  91. exit /b
  92. :getUniverseLU
  93. set "universeL=1"
  94. :get_uniLU
  95.   set /a "universeL<<=1"
  96.   if %universeL% lss 0 (set /a "universeU=-(universeL+1), universeL=0"&exit /b) else goto :get_uniLU
  97. exit /b
  98. :Complement A compA
  99. (call :copySet %1 A&call :clearSet R)
  100. (set /a pntA=0, pntN=pntA+1, pntR=0)
  101. if !AL1! neq !universeL! (
  102.   set tL=!universeL!& set /a "tU=AL1-1"
  103. ) else (
  104.   set /a "pntA+=1"
  105.   if !AU1! lss !universeU! (
  106.     set /a "tL=AU1+1"
  107.     if "!AL2!" neq "!UOut!" (set /a tU=AL2-1) else set "tU=!universeU!"
  108.   ) else ( rem 补为空
  109.     (set /a "pntR+=1"&set RL!pntR!=!UOut!&set RU!pntR!=!UOut!)&(call :copySet R %2)&exit /b
  110.   )
  111. )
  112. :ComplementLoop
  113. if !tU! geq !tL! (
  114.   (set /a "pntR+=1"&set RL!pntR!=!tL!&set RU!pntR!=!tU!)
  115.   if !tU! geq !universeU! (
  116.     (set /a "pntR+=1"&set RL!pntR!=!UOut!&set RU!pntR!=!UOut!)&(call :copySet R %2)&exit /b
  117.   )
  118. )
  119. set /a "pntA+=1, pntN=pntA+1"
  120. set /a "tL=AU!pntA!+1"
  121. if !AL%pntN%!==!UOut! (set "tU=!universeU!") else set /a "tU=!AL%pntN%!-1"
  122. goto :ComplementLoop
  123. exit /b
  124. :Simplify A 仅用于最后输出之前(不再做任何运算), 将相邻子集合并
  125. (call :copySet %1 A)&(set /a pntA=0, pntN=pntA+1)&set "AU0=!LOut!"
  126. :SimplifyLoop
  127. if "!AL%pntN%!"=="!UOut!" (call :copySet A %1)&exit /b
  128. set /a "tt=AL!pntN!-1"
  129. if "!AU%pntA%!" equ "!tt!" (
  130.   set "AU!pntA!=!AU%pntN%!"
  131.   set /a "pntN+=1"
  132. ) else set /a "pntA=pntN,pntN+=1"
  133. goto :SimplifyLoop
  134. exit /b
  135. :initSet
  136. set "%1=!%1: =!" & set "%1=!%1:{=!" & set "%1=!%1:}=!"
  137. set "pnt%1=0" & set "flag=CN"
  138. for %%i in (!%1!) do (
  139.   set "tt=%%i"
  140.   if "!tt:~0,1!"=="[" (
  141.     if "!flag!" equ "L" (echo 集合%1语法错误:%%i&pause&goto :err)
  142.     set "flag=L"
  143.     set /a pnt%1+=1&set "%1L!pnt%1!=!tt:~1!"
  144.   ) else if "!tt:~-1!"=="]" (
  145.     if "!flag!" neq "L" (echo 集合%1语法错误:%%i&pause&goto :err)
  146.     set "flag=R"
  147.     set "%1U!pnt%1!=!tt:~0,-1!"  
  148.   ) else if "!flag!" equ "L"  (echo 集合%1语法错误:%%i&pause&goto :err
  149.   ) else set /a pnt%1+=1&set "%1L!pnt%1!=!tt!"&set "%1U!pnt%1!=!tt!"&set "flag=CN"
  150. )
  151. set /a pnt%1+=1&set "%1L!pnt%1!=!UOut!"&set "%1U!pnt%1!=!UOut!"
  152. exit /b
复制代码

[ 本帖最后由 neorobin 于 2010-4-17 22:35 编辑 ]




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