sgaizxt001

哎，看帖不仔细。悔过

[ 本帖最后由 sgaizxt001 于 2010-4-17 09:07 编辑 ]

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