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

DragonBill

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

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

DragonBill

定义算法类
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_ARR    CONTAINER,
        TAB_NUM        TAB_COLLECT,
        TAB_OP         TAB_COLLECT,
        VAR_TAB_EXP    TAB_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 FUNCTION  FindContainer(con CONTAINER) RETURN INT
);
/

DragonBill

这个是算法类的实现, 有点长

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 (I <> J AND I <> M AND I <> N AND
                                                    J <> M AND J <> N AND M <> N) 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 FUNCTION  FindContainer(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;
/

DragonBill

数字和操作符组合抽象类
CREATE OR REPLACE TYPE GAME_24_EXPRESS AS OBJECT
(
        VAR_Express    VARCHAR2(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;
/

DragonBill

排列 ((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;
/

DragonBill

具体实现类, 排列(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;
/

DragonBill

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_TP    FORMULA_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;
/

DragonBill

一个小Demo
BEGIN
        DBMS_OUTPUT.ENABLE(500000);
        PLAY_24(1,3,8,9);
END;
/

junsansi

彩~~~~~~~~~

DragonBill

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