neorobin

看到题目我起劲了, 回一个楼主, 关于 "非B", 对集合是补运算吧, 而 "非" 是逻辑运算

neorobin

提到了 "列举集合中的每一个数", 这样是不能高效的, 建议思路是, 将每个集合当成若干个子集来处理, 每个子集都有一个下限和一个上限, 求运算时, 依序对两个操作数 集合 的两个子集 的 4 个上下限进行比较, 依据运算生成结果 集合 的子集的上下限, 直到结果集合的全部子集上下限都生成, 最后再来一个 "相邻" 子集合并, 即 如 [3,19] 和 [20, 37] 就合并成 [3,37], 当然这个合并不是必要的, 其中子集处理中, 即使是一个 单独的数, 也可以看成一个集合, 如 1 看成 [1,1], 这样就去除了单独数的特殊性.

neorobin

先做个并集的, 以后再抽空做个交集的, 补集难度较小, 暂不支持元素重复, 逆序排列

@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
复制代码

neorobin

交, 并, 补 完全求解, 但不考虑集合描述中 元素重复, 逆序排列

@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 编辑 ]