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

sotom

题都看不明白的路过.

youshang44

1. DECLARE
   
2.   val NUMBER;
   
3. BEGIN
   
4.   FOR str IN (SELECT e.val5 || t4.n val6
   
5.                 FROM t24 t4,
   
6.                      (SELECT CASE
   
7.                                WHEN o3.o IN ('*', '/') THEN
   
8.                                 '(' || d.val4 || ')' || o3.o
   
9.                                ELSE
   
10.                                 d.val4 || o3.o
    
11.                              END val5
    
12.                         FROM o24 o3,
    
13.                              (SELECT c.val3 || t3.n val4
    
14.                                 FROM t24 t3,
    
15.                                      (SELECT b.val2 || o2.o val3
    
16.                                         FROM o24 o2,
    
17.                                              (SELECT CASE
    
18.                                                        WHEN substr(a.val1,
    
19.                                                                    -1) IN ('+',
    
20.                                                                            '-') THEN
    
21.                                                         a.val1 || t2.n || ')'
    
22.                                                        ELSE
    
23.                                                         a.val1 || t2.n
    
24.                                                      END val2
    
25.                                                 FROM t24 t2,
    
26.                                                      (SELECT CASE
    
27.                                                                WHEN o1.o IN ('+', '-') THEN
    
28.                                                                 '(' || t1.n || o1.o
    
29.                                                                ELSE
    
30.                                                                 t1.n || o1.o
    
31.                                                              END val1
    
32.                                                         FROM t24 t1,
    
33.                                                              o24 o1) a) b) c) d) e)
    
34.   LOOP
    
35.     EXECUTE IMMEDIATE 'select ' || str.val6 || ' from dual'
    
36.       INTO val;
    
37.     IF val = 24 THEN
    
38.       dbms_output.put_line(to_char(str.val6));
    
39.     END IF;
    
40.   END LOOP;
    
41. END;
    

复制代码

youshang44

1. create table t24 (n number);
   
2. INSERT INTO t24 VALUES (1);
   
3. INSERT INTO t24 VALUES (2);
   
4. INSERT INTO t24 VALUES (3);
   
5. INSERT INTO t24 VALUES (4);
   
6. 
   
7. create table o24 (o varchar2 (1));
   
8. INSERT INTO o24 VALUES ('+');
   
9. INSERT INTO o24 VALUES ('-');
   
10. INSERT INTO o24 VALUES ('*');
    
11. INSERT INTO o24 VALUES ('/');
    
12. 
    
13. COMMIT;

复制代码

newkid

楼上的动态SQL可以用dbms_aw.eval_number方法来取代求值。

lastwinner

lastwinner 发表于 2008-10-2 17:42
逆向思路啊
24与其中一个数操作的结果，用另外三个数来获得
24与 其中两个数操作的结果 的结果，用另 ...

思考了一下，想出了逆向的思路，印象中以前也提过
翻翻帖子，果不其然，跟三年前还是一个思路，不过，我仍然不会写这样复杂的东东，太耗脑筋了@_@

lugionline

这个不难吧
定义操作符  a+b, a-b, a*b, a/b, b-a, b/a
四张牌就两种情况 3，1 或者 2，2
三张牌就是1，2或者 2，1 两种情况

完全去重不大可能，部分还是可行的

newkid

lugionline 发表于 2012-3-7 21:24
这个不难吧
定义操作符  a+b, a-b, a*b, a/b, b-a, b/a
四张牌就两种情况 3，1 或者 2，2

你来露一手？
好久不见，弃暗投明了没有？还在用SQLSERVER?

lugionline

自然是T-SQL，明天扔上来，我写的比较慢

lugionline

其实三张卡的情况只有2,1，不需要1，2，因为定义了6个操作符

四张牌 = 两张牌(初始)  递归 * [操作符 * （一张牌 或者 两张牌）] ,就算是五张牌也毫无压力吧 ，如果六张牌就需要预算 三张牌

1. With
   
2. CARDS (n) As
   
3. (
   
4.         --Select 1 Union All Select 2 Union All Select 3 Union All Select 4
   
5.         --Select 1 Union All Select 4 Union All Select 5 Union All Select 6
   
6.         --Select 3 Union All Select 5 Union All Select 6 Union All Select 9
   
7.         --Select 2 Union All Select 7 Union All Select 8 Union All Select 9
   
8.         Select 5 Union All Select 5 Union All Select 5 Union All Select 5
   
9.         --Select 4 Union All Select 4 Union All Select 10 Union All Select 10
   
10.         --Select 3 Union All Select 3 Union All Select 8 Union All Select 8
    
11. 
    
12.         -- WIKI 中的经典题目
    
13.         --Select 1 Union All Select 5 Union All Select 5 Union All Select 5
    
14.        
    
15.         --Select 2 Union All Select 4 Union All Select 10 Union All Select 10
    
16.         --Select 2 Union All Select 5 Union All Select 5 Union All Select 10
    
17.         --Select 2 Union All Select 7 Union All Select 7 Union All Select 10
    
18.         --Select 3 Union All Select 3 Union All Select 7 Union All Select 7
    
19.         --Select 4 Union All Select 4 Union All Select 7 Union All Select 7
    
20.         --Select 2 Union All Select 2 Union All Select 11 Union All Select 11
    
21.         --Select 2 Union All Select 2 Union All Select 13 Union All Select 13
    
22.         --Select 1 Union All Select 3 Union All Select 4 Union All Select 6
    
23.         --Select 2 Union All Select 3 Union All Select 5 Union All Select 12
    
24.        
    
25.         --Select 1 Union All Select 3 Union All Select 9 Union All Select 10
    
26.         --Select 7 Union All Select 8 Union All Select 8 Union All Select 10
    
27.         --Select 9 Union All Select 11 Union All Select 12 Union All Select 12
    
28.         --Select 1 Union All Select 2 Union All Select 7 Union All Select 7
    
29.         --Select 3 Union All Select 8 Union All Select 8 Union All Select 10
    
30.         --Select 4 Union All Select 8 Union All Select 8 Union All Select 11
    
31.         --Select 5 Union All Select 10 Union All Select 10 Union All Select 13
    
32.         --Select 1 Union All Select 5 Union All Select 11 Union All Select 11
    
33.         --Select 1 Union All Select 6 Union All Select 11 Union All Select 13
    
34.         --Select 1 Union All Select 7 Union All Select 13 Union All Select 13
    
35. ),
    
36. OP (ID, OPER, PRIO) As
    
37. (
    
38.         Select 1, '+', 1 Union
    
39.         Select 2, '-', 1 Union
    
40.         Select 3, '*', 0 Union
    
41.         Select 4, '/', 0 Union
    
42.         Select 5, '-', 1 Union -- b - a
    
43.         Select 6, '/', 0       -- b / a
    
44. ),
    
45. CARD1 (EXPR, VAL, PRIO, MASK, USED, OPER) As
    
46. (
    
47.         Select Cast(n As Varchar), Cast(n As Decimal(18, 4)), 0,
    
48.         Power(2, ROW_NUMBER() Over (Order By n) - 1), 1, '' From CARDS
    
49. ),
    
50. CARD2 (EXPR, VAL, PRIO, MASK, USED, OPER) As
    
51. (
    
52.         Select Distinct
    
53.                 C1.EXPR + OP.OPER + C2.EXPR,
    
54.                 Cast(Case OP.ID
    
55.                 When 1 Then C1.VAL + C2.VAL
    
56.                 When 2 Then C1.VAL - C2.VAL
    
57.                 When 3 Then C1.VAL * C2.VAL
    
58.                 When 4 Then Case When C2.VAL = 0 Then Power(20, 4) Else C1.VAL / C2.VAL End
    
59.                 End As Decimal(18, 4)) VAL,
    
60.                 OP.PRIO,
    
61.                 C1.MASK | C2.MASK MASK,
    
62.                 C1.USED + C2.USED,
    
63.                 OP.OPER
    
64.         From CARD1 C1, OP, CARD1 C2
    
65.         Where (C1.MASK & C2.MASK) = 0
    
66.                 And OP.ID In (1,2,3,4)
    
67.                 And (OP.ID Not In (1,3) Or (C1.MASK < C2.MASK))
    
68. ),
    
69. CARD12 (EXPR, VAL, PRIO, MASK, USED, OPER) As
    
70. (
    
71.         Select EXPR, VAL, PRIO, MASK, USED, OPER From CARD1
    
72.         Union
    
73.         Select EXPR, VAL, PRIO, MASK, USED, OPER From CARD2
    
74. ),
    
75. POINT (EXPR, VAL, PRIO, MASK, USED, OPER) As
    
76. (
    
77.         Select Cast(EXPR As Varchar), VAL, PRIO, MASK, USED, OPER From CARD2
    
78.         Union All
    
79.         Select
    
80.                 Cast(Case When OP.ID Not In (5, 6) Then
    
81.                         Case When C1.OPER <> '' And C1.PRIO > OP.PRIO
    
82.                         Then '(' + C1.EXPR + ')' Else C1.EXPR End
    
83.                         + OP.OPER +
    
84.                         Case When C2.OPER <> '' And (C2.PRIO > OP.PRIO Or (C2.PRIO = OP.PRIO And OP.ID Not In (1, 3)))
    
85.                         Then '(' + C2.EXPR + ')' Else C2.EXPR End
    
86.                 Else
    
87.                         Case When C2.OPER <> '' And C2.PRIO > OP.PRIO
    
88.                         Then '(' + C2.EXPR + ')' Else C2.EXPR End
    
89.                         + OP.OPER +
    
90.                         Case When C1.OPER <> '' And (C1.PRIO > OP.PRIO Or (C1.PRIO = OP.PRIO And OP.ID Not In (1, 3)))
    
91.                         Then '(' + C1.EXPR + ')' Else C1.EXPR End
    
92.                 End As Varchar) EXPR,
    
93.                 Cast(Case OP.ID
    
94.                 When 1 Then C1.VAL + C2.VAL
    
95.                 When 2 Then C1.VAL - C2.VAL
    
96.                 When 3 Then C1.VAL * C2.VAL
    
97.                 When 4 Then Case When C2.VAL = 0 Then Power(20, 4) Else C1.VAL / C2.VAL End
    
98.                 When 5 Then C2.VAL - C1.VAL
    
99.                 When 6 Then Case When C1.VAL = 0 Then Power(20, 4) Else C2.VAL / C1.VAl End
    
100.                 End As Decimal(18, 4)) VAL,
     
101.                 OP.PRIO,
     
102.                 C1.MASK | C2.MASK MASK,
     
103.                 C1.USED + C2.USED,
     
104.                 OP.OPER
     
105.         From POINT C1, OP, CARD12 C2
     
106.         Where (C1.MASK & C2.MASK) = 0
     
107.                 And
     
108.                 (
     
109.                                 (C1.USED = 2 And C2.USED = 1)
     
110.                         Or        (C1.USED = 2 And C2.USED = 2)
     
111.                         Or        (C1.USED = 3 And C2.USED = 1)
     
112.                 )
     
113.                 And C2.VAL <> Power(20, 4)
     
114.                 And
     
115.                 (        -- 尽量去重
     
116.                                 OP.ID In (2,4,5,6)   -- - /
     
117.                         Or (C1.USED > C2.USED) -- + * 但是操作数不同
     
118.                         Or (C1.USED = C2.USED And C1.MASK < C2.MASK) -- + × 操作数相同，取一边
     
119.                 )
     
120. ),
     
121. POINT24 (EXPR) As
     
122. (
     
123.         Select Distinct EXPR From POINT
     
124.         Where        Abs(VAL - 24) < 0.04 -- 20*20*0.0001 最大可能误差
     
125.                 and MASK = 1 + 2 + 4 + 8
     
126. )
     
127. Select * From POINT24 Order By EXPR
     

复制代码

newkid

替你翻译成ORACLE语法（11GR2以上）：

With
CARDS (n) As
(
--Select 1 FROM DUAL Union All Select 2 FROM DUAL Union All Select 3 FROM DUAL Union All Select 4     FROM DUAL
--Select 1 FROM DUAL Union All Select 4 FROM DUAL Union All Select 5 FROM DUAL Union All Select 6     FROM DUAL
--Select 3 FROM DUAL Union All Select 5 FROM DUAL Union All Select 6 FROM DUAL Union All Select 9     FROM DUAL
--Select 2 FROM DUAL Union All Select 7 FROM DUAL Union All Select 8 FROM DUAL Union All Select 9     FROM DUAL
   Select 5 FROM DUAL Union All Select 5 FROM DUAL Union All Select 5 FROM DUAL Union All Select 5     FROM DUAL
--Select 4 FROM DUAL Union All Select 4 FROM DUAL Union All Select 10 FROM DUAL Union All Select 10   FROM DUAL
--Select 3 FROM DUAL Union All Select 3 FROM DUAL Union All Select 8 FROM DUAL Union All Select 8     FROM DUAL
-- WIKI 中的经典题目
--Select 1 FROM DUAL Union All Select 5 FROM DUAL Union All Select 5 FROM DUAL Union All Select 5     FROM DUAL
--Select 2 FROM DUAL Union All Select 4 FROM DUAL Union All Select 10 FROM DUAL Union All Select 10   FROM DUAL
--Select 2 FROM DUAL Union All Select 5 FROM DUAL Union All Select 5 FROM DUAL Union All Select 10    FROM DUAL
--Select 2 FROM DUAL Union All Select 7 FROM DUAL Union All Select 7 FROM DUAL Union All Select 10    FROM DUAL
--Select 3 FROM DUAL Union All Select 3 FROM DUAL Union All Select 7 FROM DUAL Union All Select 7     FROM DUAL
--Select 4 FROM DUAL Union All Select 4 FROM DUAL Union All Select 7 FROM DUAL Union All Select 7     FROM DUAL
--Select 2 FROM DUAL Union All Select 2 FROM DUAL Union All Select 11 FROM DUAL Union All Select 11   FROM DUAL
--Select 2 FROM DUAL Union All Select 2 FROM DUAL Union All Select 13 FROM DUAL Union All Select 13   FROM DUAL
--Select 1 FROM DUAL Union All Select 3 FROM DUAL Union All Select 4 FROM DUAL Union All Select 6     FROM DUAL
--Select 2 FROM DUAL Union All Select 3 FROM DUAL Union All Select 5 FROM DUAL Union All Select 12    FROM DUAL
--Select 1 FROM DUAL Union All Select 3 FROM DUAL Union All Select 9 FROM DUAL Union All Select 10    FROM DUAL
--Select 7 FROM DUAL Union All Select 8 FROM DUAL Union All Select 8 FROM DUAL Union All Select 10    FROM DUAL
--Select 9 FROM DUAL Union All Select 11 FROM DUAL Union All Select 12 FROM DUAL Union All Select 12  FROM DUAL
--Select 1 FROM DUAL Union All Select 2 FROM DUAL Union All Select 7 FROM DUAL Union All Select 7     FROM DUAL
--Select 3 FROM DUAL Union All Select 8 FROM DUAL Union All Select 8 FROM DUAL Union All Select 10    FROM DUAL
--Select 4 FROM DUAL Union All Select 8 FROM DUAL Union All Select 8 FROM DUAL Union All Select 11    FROM DUAL
--Select 5 FROM DUAL Union All Select 10 FROM DUAL Union All Select 10 FROM DUAL Union All Select 13  FROM DUAL
--Select 1 FROM DUAL Union All Select 5 FROM DUAL Union All Select 11 FROM DUAL Union All Select 11   FROM DUAL
--Select 1 FROM DUAL Union All Select 6 FROM DUAL Union All Select 11 FROM DUAL Union All Select 13   FROM DUAL
--Select 1 FROM DUAL Union All Select 7 FROM DUAL Union All Select 13 FROM DUAL Union All Select 13   FROM DUAL
),
OP (ID, OPER, PRIO) As
(
        Select 1, '+', 1 FROM DUAL Union
        Select 2, '-', 1 FROM DUAL Union
        Select 3, '*', 0 FROM DUAL Union
        Select 4, '/', 0 FROM DUAL Union
        Select 5, '-', 1 FROM DUAL Union -- b - a
        Select 6, '/', 0 FROM DUAL       -- b / a
),
CARD1 (EXPR, VAL, PRIO, MASK, USED, OPER) As
(
        Select Cast(n As Varchar2(10)), Cast(n As Decimal(18, 4)), 0,
        Power(2, ROW_NUMBER() Over (Order By n) - 1), 1, '' From CARDS
),
CARD2 (EXPR, VAL, PRIO, MASK, USED, OPER) As
(
        Select Distinct
                C1.EXPR || OP.OPER || C2.EXPR,
                Cast(Case OP.ID
                When 1 Then C1.VAL + C2.VAL
                When 2 Then C1.VAL - C2.VAL
                When 3 Then C1.VAL * C2.VAL
                When 4 Then Case When C2.VAL = 0 Then Power(20, 4) Else C1.VAL / C2.VAL End ----可以在WHERE里面过滤掉除数为0的情况
                End As Decimal(18, 4)) VAL,
                OP.PRIO,
                C1.MASK + C2.MASK MASK,
                C1.USED + C2.USED,      --------- counter 用了多少操作数
                OP.OPER
        From CARD1 C1, OP, CARD1 C2
        Where BITAND(C1.MASK, C2.MASK) = 0
                And OP.ID In (1,2,3,4)
                And (OP.ID Not In (1,3) Or (C1.MASK < C2.MASK))
),
CARD12 (EXPR, VAL, PRIO, MASK, USED, OPER) As
(
        Select EXPR, VAL, PRIO, MASK, USED, OPER From CARD1
        Union
        Select EXPR, VAL, PRIO, MASK, USED, OPER From CARD2
),
POINT (EXPR, VAL, PRIO, MASK, USED, OPER) As
(
        Select Cast(EXPR As Varchar2(10)), VAL, PRIO, MASK, USED, OPER From CARD2
        Union All
        Select
                Cast(Case When OP.ID Not In (5, 6) Then
                        Case When C1.OPER IS NOT NULL And C1.PRIO > OP.PRIO
                        Then '(' || C1.EXPR || ')' Else C1.EXPR End
                        || OP.OPER ||
                        Case When C2.OPER IS NOT NULL And (C2.PRIO > OP.PRIO Or (C2.PRIO = OP.PRIO And OP.ID Not In (1, 3)))
                        Then '(' || C2.EXPR || ')' Else C2.EXPR End
                Else
                        Case When C2.OPER IS NOT NULL And C2.PRIO > OP.PRIO
                        Then '(' || C2.EXPR || ')' Else C2.EXPR End
                        || OP.OPER ||
                        Case When C1.OPER IS NOT NULL And (C1.PRIO > OP.PRIO Or (C1.PRIO = OP.PRIO And OP.ID Not In (1, 3)))
                        Then '(' || C1.EXPR || ')' Else C1.EXPR End
                End As Varchar2(10)) EXPR,
                Cast(Case OP.ID
                When 1 Then C1.VAL + C2.VAL
                When 2 Then C1.VAL - C2.VAL
                When 3 Then C1.VAL * C2.VAL
                When 4 Then Case When C2.VAL = 0 Then Power(20, 4) Else C1.VAL / C2.VAL End  ----可以在WHERE里面过滤掉除数为0的情况
                When 5 Then C2.VAL - C1.VAL
                When 6 Then Case When C1.VAL = 0 Then Power(20, 4) Else C2.VAL / C1.VAl End
                End As Decimal(18, 4)) VAL,
                OP.PRIO,
                C1.MASK + C2.MASK MASK,
                C1.USED + C2.USED,
                OP.OPER
        From POINT C1, OP, CARD12 C2
        Where BITAND (C1.MASK, C2.MASK) = 0
                --And       ------- 既然有MASK, 可以去掉
                --(
                --                (C1.USED = 2 And C2.USED = 1)
                --        Or        (C1.USED = 2 And C2.USED = 2)
                --        Or        (C1.USED = 3 And C2.USED = 1)
                --)
                And C2.VAL <> Power(20, 4)
                And
                (        -- 尽量去重
                                OP.ID In (2,4,5,6)   -- - /
                        Or (C1.USED > C2.USED) -- + * 但是操作数不同 --------- 用一个 C1.MASK < C2.MASK 就可以了
                        Or (C1.USED = C2.USED And C1.MASK < C2.MASK) -- + × 操作数相同，取一边
                )
),
POINT24 (EXPR) As
(
        Select Distinct EXPR From POINT
        Where        Abs(VAL - 24) < 0.04 -- 20*20*0.0001 最大可能误差
                and MASK = 1 + 2 + 4 + 8
)
Select * From POINT24 Order By EXPR

加了几个注，不明白你为什会那样处理除数为零的情况，另外USED的引入也没有必要。
这个递归的思路我前面也试图使用过，但是递归SQL里面只能引用最近的一层数据，所以写不出N个操作数的通用解法。