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

newkid

lastwinner 也来写一个吧！

wang5

这个题目，太简单了，我刚毕业第一年，什么都不懂的时候，就用PLSQL写了一个。

枯木萧萧

看不懂哦
很强大

concentration

declare   @t   table(id   int   identity,num   decimal(10,2))  
  insert   @t   select   @a   union   all   select   @b   union   all   select   @c   union   all   select   @d  
   
  declare   @result   table(str1   varchar(100),str2   varchar(100),result   decimal(10,6))  
  insert   @result   select   rtrim(id)+'#'+rtrim(cast(num   as   int)),rtrim(cast(num   as   int)),num   from   @t  
   
  declare   @i   int  
  set   @i=1  
  while   @i<4  
  begin  
  insert   @result   select   distinct   A.str1+'+'+rtrim(id)+'#'+rtrim(cast(num   as   int)),A.str2+'+'+rtrim(cast(num   as   int)),result+num   from   @result   A,@t   B   where   charindex(rtrim(id)+'#'+rtrim(cast(num   as   int)),str1)=0   
  /*  
  and   not   exists   (select   1   from   @result   where   str2=A.str2+'+'+rtrim(cast(B.num   as   int)))  
  and   not   exists   (select   1   from   @result   where   str2=rtrim(cast(num   as   int))+'+'+A.str2   )  
  */  
  insert   @result   select   distinct   A.str1+'-'+rtrim(id)+'#'+rtrim(cast(num   as   int)),A.str2+'-'+rtrim(cast(num   as   int)),result-num   from   @result   A,@t   B   where   charindex(rtrim(id)+'#'+rtrim(cast(num   as   int)),str1)=0  
     
  insert   @result   select   distinct   case   when   charindex('-',str2)>0   
                                                        then     rtrim(id)+'#'+rtrim(cast(num   as   int))+'-('+A.str1+')'  
                                                        else   rtrim(id)+'#'+rtrim(cast(num   as   int))+'-'+A.str1  
                                                        end,  
                                              case   when   charindex('-',str2)>0   
                                                        then   rtrim(cast(num   as   int))+'-('+A.str2+')'  
                                                        else   rtrim(cast(num   as   int))+'-'+A.str2  
                                                        end  
  ,num-result   from   @result   A,@t   B   where   charindex(rtrim(id)+'#'+rtrim(cast(num   as   int)),str1)=0  
   
  insert   @result   select   distinct   
        case   when   charindex('+',A.str1)>0   or   charindex('-',A.str1)>0   
                  then   '('+A.str1+')*'+rtrim(id)+'#'+rtrim(cast(num   as   int))  
                  else     A.str1+'*'+rtrim(id)+'#'+rtrim(cast(num   as   int))   
                  end,  
        case   when   charindex('+',A.str2)>0   or   charindex('-',A.str2)>0      
                  then   '('+A.str2+')*'+rtrim(cast(num   as   int))  
                  else   A.str2+'*'+rtrim(cast(num   as   int))  
                  end,  
  result*num   from   @result   A,@t   B   where   charindex(rtrim(id)+'#'+rtrim(cast(num   as   int)),str1)=0  
  /*  
  and   not   exists   (select   1   from   @result   where   str2=(case   when   charindex('+',A.str2)>0   or   charindex('-',A.str2)>0      
                  then   '('+A.str2+')*'+rtrim(cast(B.num   as   int))  
                  else   A.str2+'*'+rtrim(cast(B.num   as   int))  
                  end))   
  and   not   exists   (select   1   from   @result   where   str2=(case   when   charindex('+',A.str2)>0   or   charindex('-',A.str2)>0      
                  then   rtrim(cast(B.num   as   int))+'*('+A.str2+')'  
                  else   rtrim(cast(B.num   as   int))+'*'+A.str2  
                  end)   )  
  */  
  insert   @result   select   distinct   
        case   when   (charindex('+',A.str1)>0   or   charindex('-',A.str1)>0)   and   charindex('(',str1)=0   
                  then   '('+A.str1+')/'+rtrim(id)+'#'+rtrim(cast(num   as   int))  
                  else     A.str1+'/'+rtrim(id)+'#'+rtrim(cast(num   as   int))   
                  end,  
        case   when   charindex('+',A.str2)>0   or   charindex('-',A.str2)>0     and   charindex('(',str2)=0      
                  then   '('+A.str2+')/'+rtrim(cast(num   as   int))  
                  else   A.str2+'/'+rtrim(cast(num   as   int))  
                  end,  
  result/num   from   @result   A,@t   B   where   charindex(rtrim(id)+'#'+rtrim(cast(num   as   int)),str1)=0   and   num<>0  
   
  insert   @result   select   distinct   
        case   when   (charindex('+',A.str1)>0   or   charindex('-',A.str1)>0)   and   charindex('(',str1)=0   
                  then   rtrim(id)+'#'+rtrim(cast(num   as   int))+'/('+A.str1+')'  
                  else   rtrim(id)+'#'+rtrim(cast(num   as   int))+'/'+A.str1  
                  end,  
        case   when   ((charindex('+',A.str2)>0   or   charindex('-',A.str2)>0)     and   charindex('(',str2)=0)   or   charindex('/',str2)>0   or   charindex('*',str2)>0  
                  then   rtrim(cast(num   as   int))+'/('+A.str2+')'  
                  else   rtrim(cast(num   as   int))+'/'+A.str2  
                  end,  
  num/result   from   @result   A,@t   B   where   charindex(rtrim(id)+'#'+rtrim(cast(num   as   int)),str1)=0   and   result<>0  
   
  set   @i=@i+1  
  end  
  --select   cast(rtrim(str2)   as   varchar(20))   计算公式   from   @result   order   by   cast(rtrim(str2)   as   varchar(20))  
   
  select   distinct   cast(rtrim(str2)   as   varchar(20))   计算公式   from   @result   where     result=24   and   len(str2)-len(replace(replace(replace(replace(str2,'+',''),'-',''),'*',''),'/',''))=3

cow977

太难了，这是算法的题目。

newkid

用自定义函数求值使得SQL简短一些:

CREATE OR REPLACE FUNCTION f_op (p_n1 NUMBER, p_op VARCHAR2, p_n2 NUMBER) RETURN NUMBER
AS
BEGIN
   RETURN CASE WHEN p_op = '+' THEN p_n1 + p_n2
               WHEN p_op = '-' THEN p_n1 - p_n2
               WHEN p_op = '*' THEN p_n1 * p_n2
               WHEN p_op = '/' AND p_n2<>0 THEN p_n1 / p_n2
               ELSE NULL
          END;

END f_op;
/


WITH vw_tmp AS (
     SELECT a.n  as a
           ,o1.o as o1
           ,b.n  as b
           ,o2.o as o2
           ,c.n  as c
           ,o3.o as o3
           ,d.n  as d
       from t24 a, t24 b,t24 c,t24 d,o24 o1,o24 o2,o24 o3
      WHERE a.rowid NOT IN (b.rowid,c.rowid,d.rowid)
            AND b.rowid NOT IN (c.rowid,d.rowid)
            AND c.rowid<>d.rowid
     )
    ,vw_tmp2 AS (       ---- ((a b) c) d
    SELECT '(('||a||o1||b||')'||o2||c||')'||o3||d as formula
          ,f_op(f_op(f_op(a,o1,b),o2,c),o3,d) result
     FROM vw_tmp
    UNION ALL     ---- (a (b c)) d
    SELECT '('||a||o1||'('||b||o2||c||'))'||o3||d as formula
          ,f_op(f_op(a,o1,f_op(b,o2,c)),o3,d) as result
     FROM vw_tmp
    UNION ALL ---- (a b) (c d)
    SELECT '('||a||o1||b||')'||o2||'('||c||o3||d||')' as formula
          ,f_op(f_op(a,o1,b),o2,f_op(c,o3,d)) as result
     FROM vw_tmp
    UNION ALL  ---- a ((b c) d)
    SELECT a||o1||'(('||b||o2||c||')'||o3||d||')' as formula
          ,f_op(a,o1,f_op(f_op(b,o2,c),o3,d)) as result
     FROM vw_tmp
    UNION ALL ---- a (b (c d))
    SELECT a||o1||'('||b||o2||'('||c||o3||d||'))' as formula
          ,f_op(a,o1,f_op(b,o2,f_op(c,o3,d))) as result
     FROM vw_tmp
   )
SELECT formula,result FROM vw_tmp2
WHERE result=24;
/




WITH v24 AS (SELECT id,n,MAX(SYS_CONNECT_BY_PATH(n,',')) OVER() as sorted
                   ,REGEXP_REPLACE(MAX(SYS_CONNECT_BY_PATH(n,',')) OVER(),'[^,]+','',1,id) AS sorted_ex
               FROM (SELECT ROWNUM id, n FROM (SELECT * FROM t24 ORDER BY n))
              START WITH id=1 CONNECT BY id=PRIOR id+1
             )
    ,vw_tmp AS (
     SELECT a.n  as a
           ,o1.o as o1
           ,b.n  as b
           ,o2.o as o2
           ,c.n  as c
           ,o3.o as o3
           ,d.n  as d
           ,a.sorted
           ,a.sorted_ex as a_ex
           ,d.sorted_ex as d_ex
           ,o1.o||o2.o||o3.o as op
           ,DECODE(o1.o,'+',1,'-',1,2) AS p1
           ,DECODE(o2.o,'+',1,'-',1,2) AS p2
           ,DECODE(o3.o,'+',1,'-',1,2) AS p3
       from v24 a, v24 b,v24 c,v24 d,o24 o1,o24 o2,o24 o3
      WHERE a.id NOT IN (b.id,c.id,d.id)
            AND b.id NOT IN (c.id,d.id)
            AND c.id<>d.id
     )
    ,vw_tmp2 AS (  ---- ((a b) c) d
    SELECT CASE WHEN p2<p3 THEN '(' END
           ||CASE WHEN p1<p2 THEN '(' END
           ||CASE WHEN op IN ('***','+++') THEN REGEXP_SUBSTR(sorted,'[^,]',1,1)
                  WHEN o1||o2 IN ('**','++') THEN REGEXP_SUBSTR(d_ex,'[^,]',1,1)
                  WHEN o1 IN ('*','+') THEN TO_CHAR(LEAST(a,b))
                  ELSE TO_CHAR(a)
             END
           ||o1
           ||CASE WHEN op IN ('***','+++') THEN REGEXP_SUBSTR(sorted,'[^,]',1,2)
                  WHEN o1||o2 IN ('**','++') THEN REGEXP_SUBSTR(d_ex,'[^,]',1,2)
                  WHEN o1 IN ('*','+') THEN TO_CHAR(GREATEST(a,b))
                  ELSE TO_CHAR(b)
             END
           ||CASE WHEN p1<p2 THEN ')' END
           ||o2
           ||CASE WHEN op IN ('***','+++') THEN REGEXP_SUBSTR(sorted,'[^,]',1,3)
                  WHEN o1||o2 IN ('**','++') THEN REGEXP_SUBSTR(d_ex,'[^,]',1,3)
                  ELSE TO_CHAR(c)
             END
           ||CASE WHEN p2<p3 THEN ')' END
           ||o3
           ||CASE WHEN op IN ('***','+++') THEN REGEXP_SUBSTR(sorted,'[^,]',1,4)
                  ELSE TO_CHAR(d)
             END
           as formula
          ,f_op(f_op(f_op(a,o1,b),o2,c),o3,d) result
     FROM vw_tmp
    UNION ALL    ---- (a (b c)) d
    SELECT CASE WHEN p1<p3 THEN '(' END
           ||a
           ||o1
           ||CASE WHEN p2<p1 OR p2=p1 AND o1 IN ('/','-') THEN '(' END
           ||CASE WHEN o2 IN ('*','+') THEN LEAST(b,c)
                  ELSE b
             END
           ||o2
           ||CASE WHEN o2 IN ('*','+') THEN GREATEST(b,c)
                  ELSE c
             END
           ||CASE WHEN p2<p1 OR p2=p1 AND o1 IN ('/','-') THEN ')' END
           ||CASE WHEN p1<p3 THEN ')' END
           ||o3
           ||d as formula
          ,f_op(f_op(a,o1,f_op(b,o2,c)),o3,d) as result
     FROM vw_tmp
    WHERE o1 NOT IN ('*','+')        -- 如果'*','+'则与((a b) c) d等价
    UNION ALL   ---- a ((b c) d)
    SELECT a
           ||o1
           ||CASE WHEN p3<p1 OR p3=p1 AND o1 IN ('/','-') THEN '(' END
           ||CASE WHEN p2<p3 THEN '(' END
           ||CASE WHEN o2||o3 IN ('**','++') THEN REGEXP_SUBSTR(a_ex,'[^,]',1,1)
                  WHEN o2 IN ('*','+') THEN TO_CHAR(LEAST(b,c))
                  ELSE TO_CHAR(b)
             END
           ||o2
           ||CASE WHEN o2||o3 IN ('**','++') THEN REGEXP_SUBSTR(a_ex,'[^,]',1,2)
                  WHEN o2 IN ('*','+') THEN TO_CHAR(GREATEST(b,c))
                  ELSE TO_CHAR(c)
             END
           ||CASE WHEN p2<p3 THEN ')' END
           ||o3
           ||CASE WHEN o2||o3 IN ('**','++') THEN REGEXP_SUBSTR(a_ex,'[^,]',1,3)
                  ELSE TO_CHAR(d)
             END
           ||CASE WHEN p3<p1 OR p3=p1 AND o1 IN ('/','-') THEN ')' END
           as formula
          ,f_op(a,o1,f_op(f_op(b,o2,c),o3,d)) as result
     FROM vw_tmp
    WHERE o1 NOT IN ('*','+') -- 如果'*','+'则与((a b) c) d等价
    UNION ALL  ---- a (b (c d))
    SELECT a
           ||o1
           ||CASE WHEN p2<p1 OR p2=p1 AND o1 IN ('/','-') THEN '(' END
           ||b
           ||o2
           ||CASE WHEN p3<p2 OR p2=p3 AND o2 IN ('/','-') THEN '(' END
           ||CASE WHEN o3 IN ('*','+') THEN LEAST(c,d)
                  ELSE c
             END
           ||o3
           ||CASE WHEN o3 IN ('*','+') THEN GREATEST(c,d)
                  ELSE d
             END
           ||CASE WHEN p3<p2 OR p2=p3 AND o2 IN ('/','-') THEN ')' END
           ||CASE WHEN p2<p1 OR p2=p1 AND o1 IN ('/','-') THEN ')' END
           as formula
          ,f_op(a,o1,f_op(b,o2,f_op(c,o3,d))) as result
     FROM vw_tmp
    WHERE o1 NOT IN ('*','+') AND o2 NOT IN ('*','+')  -- 如果 o1='*','+'则与(a (b c)) d等价,如果 o2='*','+'则与a ((b c) d)等价
    UNION ALL    ---- (a b) (c d)
    SELECT CASE WHEN p1<p2 THEN '(' END
           ||CASE WHEN op IN ('+*+','*+*') THEN REGEXP_SUBSTR(sorted,'[^,]',1,1) --排序
                  WHEN o1 IN ('*','+') THEN TO_CHAR(LEAST(a,b))
                  ELSE TO_CHAR(a)
             END
           ||o1
           ||CASE WHEN op IN ('+*+','*+*') THEN REGEXP_SUBSTR(sorted,'[^,]',1,2)
                  WHEN o1 IN ('*','+') THEN TO_CHAR(GREATEST(a,b))
                  ELSE TO_CHAR(b)
             END
           ||CASE WHEN p1<p2 THEN ')' END
           ||o2
           ||CASE WHEN p3<p2 OR p2=p3 AND o2 IN ('/','-') THEN '(' END
           ||CASE WHEN op IN ('+*+','*+*') THEN REGEXP_SUBSTR(sorted,'[^,]',1,3)
                  WHEN o3 IN ('*','+') THEN TO_CHAR(LEAST(c,d))
                  ELSE TO_CHAR(c)
             END
           ||o3
           ||CASE WHEN op IN ('+*+','*+*') THEN REGEXP_SUBSTR(sorted,'[^,]',1,4)
                  WHEN o3 IN ('*','+') THEN TO_CHAR(GREATEST(c,d))
                  ELSE TO_CHAR(d)
             END
           ||CASE WHEN p3<p2 OR p2=p3 AND o2 IN ('/','-') THEN ')' END
           as formula
          ,f_op(f_op(a,o1,b),o2,f_op(c,o3,d)) as result
     FROM vw_tmp
    WHERE NOT (p1=p2 OR p2=p3 AND o2 IN ('+','*')) AND op<>'+*-'         ---  op='+*-' 等价于  op='-*+'
   )
SELECT DISTINCT formula FROM vw_tmp2
WHERE result=24;

fannec

不错，学习了。

iamclq

太复杂了，SQL有点费解

yangi1314

太强了，顶一个，学习中。。。

DragonBill

嗯, 这个贴得留个名