用OO的思想实现24点算法初探

显示全部楼层 · 2008-4-11 18:37:24

下午有点空, 抽时间考虑了一下24算法能否用OO的观点来实现.
最初想到的是将+ - * /四种方法用四个FINAL MEMBER PROCEDURE实现,
后来一想直接用OPEN CURSOR FOR SELECT || EXPRESS的方法岂不更好?
遂放弃这一念头. 观察了一下, 发现整个需求中变化的是:
数字或操作符的排列以及数字和操作符的组合.
似乎有点靠策略模式的谱, 画了一下UML图, 发现可以把数字或操作符的排列算法做成一个抽象类,
数字和操作符的组合做成一个抽象类.
数字或操作符的排列算法无非两种: 1, 是对数字或操作符全排列;
2, 是先对数字两两排列, 取其操作后的结果再与剩下的数字两两排列,
这个涉及递归, 想想就麻烦

, 故先不实现它, 仅考虑第一种情况, 呵呵

再考虑数字和操作符的组合, 无非 newkid 在其贴子里列出的五种情况, 这个好办, 一个超类, 五个子类.
下面看具体的实现.

千问 · 2008-4-11 18:37:24

定义算法类
CREATE TYPE CONTAINER AS VARRAY(4) OF VARCHAR2(5);
/
CREATE TYPE TAB_COLLECT AS TABLE OF CONTAINER;
/
CREATE TYPE TAB_EXPRESS AS TABLE OF VARCHAR2(100);
/
CREATE OR REPLACE TYPE ARITHMETIC_24 AS OBJECT
(

VAR_NUM_ARRCONTAINER,

TAB_NUMTAB_COLLECT,

TAB_OP TAB_COLLECT,

VAR_TAB_EXPTAB_EXPRESS,

CONSTRUCTOR FUNCTION ARITHMETIC_24(num1 NUMBER, num2 NUMBER,

num3 NUMBER, num4 NUMBER)

RETURN SELF AS RESULT,

FINAL MEMBER PROCEDURE GenNumArr,

FINAL MEMBER PROCEDURE GenOpArr,

FINAL MEMBER PROCEDURE SaveFormula(Formula VARCHAR2),

FINAL MEMBER PROCEDURE ShowAllFormula,

FINAL MEMBER FUNCTIONFindContainer(con CONTAINER) RETURN INT
);
/

千问 · 2008-4-11 18:37:24

这个是算法类的实现, 有点长
CREATE OR REPLACE TYPE BODY ARITHMETIC_24 AS

CONSTRUCTOR FUNCTION ARITHMETIC_24(num1 NUMBER, num2 NUMBER,

num3 NUMBER, num4 NUMBER)

RETURN SELF AS RESULT AS

BEGIN

VAR_NUM_ARR := CONTAINER(num1,num2,num3,num4);

TAB_NUM := TAB_COLLECT();

TAB_OP:= TAB_COLLECT();

VAR_TAB_EXP := TAB_EXPRESS();

RETURN;

END;

FINAL MEMBER PROCEDURE GenNumArr AS

BEGIN

FOR I IN VAR_NUM_ARR.FIRST..VAR_NUM_ARR.LAST LOOP

FOR J IN VAR_NUM_ARR.FIRST..VAR_NUM_ARR.LAST LOOP

FOR M IN VAR_NUM_ARR.FIRST..VAR_NUM_ARR.LAST LOOP

FOR N IN VAR_NUM_ARR.FIRST..VAR_NUM_ARR.LAST LOOP

IF (IJ AND IM AND IN AND

JM AND JN AND MN) THEN

TAB_NUM.EXTEND;

TAB_NUM(TAB_NUM.LAST) := CONTAINER(VAR_NUM_ARR(I),VAR_NUM_ARR(J),

VAR_NUM_ARR(M),VAR_NUM_ARR(N));

END IF;

END LOOP;

END LOOP;

END LOOP;

END LOOP;

END;

FINAL MEMBER PROCEDURE GenOpArr AS

ARR_OP
CONTAINER := CONTAINER('+','-','*','/');

TMP_CON
CONTAINER;

BEGIN

FOR I IN ARR_OP.FIRST..ARR_OP.LAST LOOP

FOR J IN ARR_OP.FIRST..ARR_OP.LAST LOOP

FOR M IN ARR_OP.FIRST..ARR_OP.LAST LOOP

FOR N IN ARR_OP.FIRST..ARR_OP.LAST LOOP

TMP_CON := CONTAINER(ARR_OP(I),ARR_OP(J),ARR_OP(M),ARR_OP(N));

IF (FindContainer(TMP_CON) = 0) THEN

TAB_OP.EXTEND;

TAB_OP(TAB_OP.LAST) := TMP_CON;

END IF;

END LOOP;

END LOOP;

END LOOP;

END LOOP;

END;

FINAL MEMBER FUNCTIONFindContainer(con CONTAINER) RETURN INT AS

BEGIN

IF TAB_OP.COUNT = 0 THEN RETURN 0; END IF;

FOR I IN TAB_OP.FIRST..TAB_OP.LAST LOOP

IF (TAB_OP(I)(1) = con(1) AND TAB_OP(I)(2) = con(2) AND

TAB_OP(I)(3) = con(3) AND TAB_OP(I)(4) = con(4)) THEN

RETURN 1;

END IF;

END LOOP;

RETURN 0;

END;

FINAL MEMBER PROCEDURE SaveFormula(Formula VARCHAR2) AS

FLAG
INT;

BEGIN

IF (VAR_TAB_EXP.COUNT = 0) THEN

VAR_TAB_EXP.EXTEND;

VAR_TAB_EXP(VAR_TAB_EXP.LAST) := Formula;

ELSE

FLAG := 0;

FOR I IN VAR_TAB_EXP.FIRST..VAR_TAB_EXP.LAST LOOP

IF (VAR_TAB_EXP(I) = Formula) THEN

FLAG := 1;

EXIT;

END IF;

END LOOP;

IF (0 = FLAG) THEN

VAR_TAB_EXP.EXTEND;

VAR_TAB_EXP(VAR_TAB_EXP.LAST) := Formula;

END IF;

END IF;

END;

FINAL MEMBER PROCEDURE ShowAllFormula

AS

BEGIN

FOR I IN VAR_TAB_EXP.FIRST..VAR_TAB_EXP.LAST LOOP

DBMS_OUTPUT.PUT_LINE(VAR_TAB_EXP(I));

END LOOP;

END;
END;
/

千问 · 2008-4-11 18:37:24

数字和操作符组合抽象类
CREATE OR REPLACE TYPE GAME_24_EXPRESS AS OBJECT
(

VAR_ExpressVARCHAR2(100),

FINAL MEMBER FUNCTION CalExpress RETURN NUMBER
)NOT FINAL NOT INSTANTIABLE;
/

CREATE OR REPLACE TYPE BODY GAME_24_EXPRESS AS

FINAL MEMBER FUNCTION CalExpress RETURN NUMBER AS

TYPE CurTyp IS REF CURSOR;

myCur CurTyp;

RTN_VAL
NUMBER;

BEGIN

OPEN myCur FOR 'SELECT ' || VAR_Express || ' FROM DUAL';

FETCH myCur INTO RTN_VAL;

CLOSE myCur;

RETURN RTN_VAL;

EXCEPTION WHEN OTHERS THEN

RETURN NULL;

END;
END;
/

千问 · 2008-4-11 18:37:24

排列 ((a b) c) d, 具体实现类
CREATE OR REPLACE TYPE GAME_24_1 UNDER GAME_24_EXPRESS
(

--((a b) c) d

CONSTRUCTOR FUNCTION GAME_24_1(NUM_ARR CONTAINER, OP_ARR CONTAINER) RETURN SELF AS RESULT
);
/

CREATE OR REPLACE TYPE BODY GAME_24_1 AS

--((a b) c) d

CONSTRUCTOR FUNCTION GAME_24_1(NUM_ARR CONTAINER, OP_ARR CONTAINER)

RETURN SELF AS RESULT AS

BEGIN

VAR_Express := '((' || NUM_ARR(1) || OP_ARR(1) || NUM_ARR(2) || ')' || OP_ARR(2) ||

NUM_ARR(3) || ')' || OP_ARR(3) || NUM_ARR(4);

RETURN;

END;
END;
/

千问 · 2008-4-11 18:37:24

具体实现类, 排列(a (b c)) d
CREATE OR REPLACE TYPE GAME_24_2 UNDER GAME_24_EXPRESS
(

--(a (b c)) d

CONSTRUCTOR FUNCTION GAME_24_2(NUM_ARR CONTAINER, OP_ARR CONTAINER) RETURN SELF AS RESULT
);
/

CREATE OR REPLACE TYPE BODY GAME_24_2 AS

--(a (b c)) d

CONSTRUCTOR FUNCTION GAME_24_2(NUM_ARR CONTAINER, OP_ARR CONTAINER)

RETURN SELF AS RESULT AS

BEGIN

VAR_Express := '(' || NUM_ARR(1) || OP_ARR(1) || '(' || NUM_ARR(2) || OP_ARR(2) ||

NUM_ARR(3) || '))' || OP_ARR(3) || NUM_ARR(4);

RETURN;

END;
END;
/

千问 · 2008-4-11 18:37:24

Client User
CREATE OR REPLACE PROCEDURE PLAY_24(N1 INT, N2 INT, N3 INT, N4 INT) AS

TYPE FORMULA_TP IS TABLE OF GAME_24_EXPRESS;

VAR_FORMULA_TPFORMULA_TP;

VAR_ARITHMETIC_24 ARITHMETIC_24;
BEGIN

VAR_ARITHMETIC_24 := ARITHMETIC_24(N1,N2,N3,N4);

VAR_ARITHMETIC_24.GenNumArr;

VAR_ARITHMETIC_24.GenOpArr;

FOR M IN VAR_ARITHMETIC_24.TAB_NUM.FIRST..VAR_ARITHMETIC_24.TAB_NUM.LAST LOOP

FOR N IN VAR_ARITHMETIC_24.TAB_OP.FIRST..VAR_ARITHMETIC_24.TAB_OP.LAST LOOP

VAR_FORMULA_TP := FORMULA_TP(GAME_24_1(VAR_ARITHMETIC_24.TAB_NUM(M),

VAR_ARITHMETIC_24.TAB_OP(N)),

GAME_24_2(VAR_ARITHMETIC_24.TAB_NUM(M),

VAR_ARITHMETIC_24.TAB_OP(N)));

FOR K IN VAR_FORMULA_TP.FIRST..VAR_FORMULA_TP.LAST LOOP

IF (VAR_FORMULA_TP(K).CalExpress = 24) THEN

VAR_ARITHMETIC_24.SaveFormula(VAR_FORMULA_TP(K).VAR_Express);

END IF;

END LOOP;

END LOOP;

END LOOP;

VAR_ARITHMETIC_24.ShowAllFormula;
END;
/

千问 · 2008-4-11 18:37:24

一个小Demo
BEGIN

DBMS_OUTPUT.ENABLE(500000);

PLAY_24(1,3,8,9);
END;
/

千问 · 2008-4-11 18:37:24

彩~~~~~~~~~

千问 · 2008-4-11 18:37:24

这种方法目前还存在不少问题, 至少在算法类中感觉还有些不对劲, 在此权当抛砖, 以求宝玉,
欢迎各位指正