深夜独霸, 轮到我出个题目了——算24点的SQL解法

hyee

SELECT decode(ROWNUM, 1, '+', 2, '-', 3, '*', '-') r
这个确实是笔误。这套算法确实没有覆盖到所有
如果不算除法，其实拆开，确实只有((a b) c) d(a b) (c d)这两种，
因为通过connect方法，(a b)(c d)可以是(a c)(b d),(a d)(b c),四种元素的排序不是顺序的，
比如开始是1 2 3 4记录，后来又有2 3 4 1记录,那么((a b) c) d则覆盖了((a b) c) d和a ((b c) d)这两种
四种元素最后的组合只会有3+1和2+2这两种。

如果算除法，那么还缺少 a/(b c d),a/(b c) d等几种，即除数是其他多个元素的组合，这可以在loop中覆盖到，稍微改点就好了。

使用select from dual会导致大量的引擎切换，并增加解析数和可能引发热点快，所以用PL/SQL.

我在我原来的帖子上改了一下，不确定有没有其他漏的算法。如果有漏的，请把那四个参数给一下，谢谢。
另一种不用execute immediate的算法:

create or replace type T_TBL_CHARS is table of varchar2(50);
/
CREATE OR REPLACE FUNCTION FML(A INT, B INT, C INT, D INT) RETURN T_tbl_CHARS
    PIPELINED IS
    t  T_tbl_CHARS := T_tbl_CHARS('', '', '', '', '', '', '');
    t2 T_tbl_CHARS;
    FUNCTION calc(p_Statement VARCHAR2) RETURN VARCHAR2 IS
        X   NUMBER;
        Y   NUMBER;
        Opr VARCHAR2(1);
        FUNCTION Init(p_Ocurr PLS_INTEGER) RETURN NUMBER IS
            v_Item VARCHAR2(30) := regexp_substr(p_Statement, ':?[0-9\.\-]+', 1, p_Ocurr);
        BEGIN
            RETURN CASE WHEN v_Item LIKE ':%' THEN t(substr(v_Item, 2)) ELSE v_Item END;
        END;
    BEGIN
        X   := Init(1);
        Y   := Init(2);
        Opr := t(ascii(regexp_substr(p_Statement, '[xyz]')) - 115);
        x   := CASE Opr WHEN '+' THEN x + y WHEN '-' THEN x - y WHEN '/' THEN x / y ELSE x * y END;
        RETURN trunc(x, 2);
    END;

    FUNCTION eval(p_expression VARCHAR2) RETURN VARCHAR2 IS
        v_Result NUMBER;
        v_Exps   VARCHAR2(50) := '(' || p_expression || ')';
        v_Piece  VARCHAR2(50);
    BEGIN
        BEGIN
            LOOP
                v_Piece := Regexp_Substr(v_Exps, '\([^()]+\)');
                EXIT WHEN v_Piece IS NULL;
                v_Exps := REPLACE(v_Exps, v_Piece, calc(v_Piece));
            END LOOP;
            v_Result := v_Exps;
        EXCEPTION WHEN OTHERS THEN NULL;
        END;
        v_Exps := p_expression;
        FOR i IN 1 .. 4 LOOP
            v_Exps := REPLACE(v_Exps, ':' || (i), t(i));
        END LOOP;
        FOR i IN 5 .. 7 LOOP
            v_Exps := REPLACE(v_Exps, chr(115 + i), t(i));
        END LOOP;
        RETURN v_Exps || ' = ' || nvl('' || v_Result, '#err') || ' ';
    END;
BEGIN
    SELECT DISTINCT sys_connect_by_path(x, ',') ||
                    substr(sys_connect_by_path(r, ','), 1, 7) || '-' BULK COLLECT
    INTO   T2
    FROM   (SELECT decode(rownum, 1, a, 2, b, 3, c, d) x, rownum r1
            FROM   dual
            CONNECT BY rownum <= 4),
           (SELECT decode(ROWNUM, 1, '+', 2, '-', 3, '*', '/') r
            FROM   dual
            CONNECT BY ROWNUM <= 4)
    WHERE  LEVEL = 4
    CONNECT BY NOCYCLE PRIOR r1 != r1;

    FOR r IN 1 .. T2.COUNT LOOP
        FOR i IN 1 .. 7 LOOP
            t(i) := rtrim(regexp_substr(T2(R), '[^,]+,', 1, i), ',');
        END LOOP;   
        PIPE ROW(eval('((:1x:2)y:3)z:4'));--((a,b),c),d
        PIPE ROW(eval('(:1x(:2y:3))z:4'));--(a,(b,c)),d
        PIPE ROW(eval('(:1x:2)y(:3z:4)'));--(a,b),(c,d)
        PIPE ROW(eval(':1x((:2y:3)z:4)'));--a,((b,c),d)
        PIPE ROW(eval(':1x(:2y(:3z:4))'));--a,(b,(c,d))
    END LOOP;
    RETURN;
END;

SQL>SELECT * FROM TABLE(fml(1,2,3,4)) WHERE COLUMN_VALUE LIKE '%= 24 '
COLUMN_VALUE
------------------------------
(1+3)*(4+2) = 24
((1*2)*4)*3 = 24
(1*(2*4))*3 = 24
(1*2)*(4*3) = 24
1*((2*4)*3) = 24
1*(2*(4*3)) = 24
((3+1)+2)*4 = 24
(3+(1+2))*4 = 24
((3*1)*2)*4 = 24

[ 本帖最后由 hyee 于 2008-12-2 16:14 编辑 ]

xiaoyi0326

学习了,还处在路上

newkid

原帖由 hyee 于 2008-12-2 10:30 发表

使用select from dual会导致大量的引擎切换，并增加解析数和可能引发热点快，所以用PL/SQL.

据说10G对DUAL作了优化，不会有你说的问题。如果用DUAL则大量的解析求值工作让SQL做掉了。

你的方法其实和我#76的写法很像。但你把括号套上去又解析回来很辛苦，里面还用了诸如t(ascii(regexp_substr(p_Statement, '[xyz]')) - 115)这样很难读的东西。我直接用嵌套函数调用。

顺序和我总结的五种一样，没有漏掉的。

zhangweicai74

如看天书

琉南

wxga_tj

达人真多，学习

freedom2k

这么早出个这么牛的题目啊

iamlomen

mark!

snail506891

算法有点恼火

gg152326

这是我写的，不知道怎么去重复，呵呵，初学
SELECT DISTINCT *
FROM (
   SELECT c,decode(o3,'+',r02+n4,'-',r02-n4,'*',r02*n4,r02/n4)r03--,n1,n2,n3,n4
   FROM (
      SELECT c,decode(o2,'+',r01+n3,'-',r01-n3,'*',r01*n3,r01/n3)r02,n1,n2,n3,n4,o3
      FROM (
         SELECT '(('||m1||o1||m2||')'||o2||m3||')'||o3||m4 c,decode(o1,'+',n1+n2,'-',n1-n2,'*',n1*n2,n1/n2)r01,n1,n2,n3,n4,o2,o3
         FROM(
            SELECT t1.val m1,t2.val m2,t3.val m3,t4.val m4,t1.val n1,t2.val n2,t3.val n3,t4.val n4,o1.op o1,o2.op o2,o3.op o3
            FROM(SELECT NAME,val FROM z_test)t1,--name是用来显示公式的，后来觉得没必要，显示val就ok了
                (SELECT NAME,val FROM z_test)t2,
                (SELECT NAME,val FROM z_test)t3,
                (SELECT NAME,val FROM z_test)t4,
                z_op o1,--存储符号
                z_op o2,
                z_op o3
            WHERE t1.NAME<>t2.NAME AND t1.NAME <> t3.NAME AND t1.NAME <> t4.NAME AND t2.NAME <> t3.NAME AND t2.NAME <> t4.NAME AND t3.NAME <> t4.NAME
         ) t
      ) t
   ) t
) t
WHERE r03 = 24;