发现一位专门用SQL解各种谜题的高人！

newkid · 发表于 2010-6-25 02:31

http://oraqa.com/2009/01/18/how- ... mber-puzzle-in-sql/

求出一个最大的7位数，它的每位各不相同，而且能被各位整除。

How to solve the Largest 7-Digit Number Puzzle in SQL

January 18th, 2009 By Frank Zhou

The following is an interesting problem posted by mathforum.org:

Work out the largest 7-digit number you can applying 2 rules only:

1) every digit in the number must be able to be divided into the number;
2) no digit can be repeated.

———————————————-10G SQL Solution —————————————————
SELECT  str_num
FROM
(SELECT str_num
  FROM
  (SELECT str_num, to_number(substr(str_num,LEVEL,1)) n1
FROM
(SELECT to_number(utl_raw.cast_to_varchar2(utl_raw.reverse(utl_raw.cast_to_raw(
         replace(sys_connect_by_path(n,','),',')))))  str_num
FROM (SELECT LEVEL n FROM dual CONNECT BY LEVEL <10)
WHERE LEVEL = 7
CONNECT BY NOCYCLE PRIOR n != n
AND LEVEL < 8
AND CASE LEVEL
      WHEN 2
THEN CASE WHEN n in (2, 6, 8)
            THEN CASE WHEN MOD(CONNECT_BY_ROOT(n), 2) = 0 THEN 1 END
   WHEN n in (4)
   THEN CASE WHEN MOD(to_number(PRIOR N||N), n) = 0 THEN 1 END
   WHEN n = 5
   THEN CASE WHEN PRIOR N in (5) THEN 1 END
   ELSE 1 END
WHEN 3
THEN CASE WHEN n in (2, 6)
   THEN CASE WHEN MOD(CONNECT_BY_ROOT(n), 2) = 0 THEN 1 END
   WHEN n in (4)
   THEN CASE WHEN MOD(to_number(PRIOR N||N), n) = 0 THEN 1 END
   WHEN n in (8)
   THEN CASE WHEN MOD(to_number(CONNECT_BY_ROOT(n)||PRIOR N||N),n)= 0
      THEN 1 END
            WHEN n = 5
   THEN CASE WHEN CONNECT_BY_ROOT(n) in (5) THEN 1 END
   ELSE 1 END
      WHEN 4
      THEN CASE WHEN n in (2, 4, 6 ,8)
   THEN CASE WHEN MOD(CONNECT_BY_ROOT(n), 2) = 0 THEN 1 END
   WHEN n = 5
               THEN CASE WHEN CONNECT_BY_ROOT(n) in (5) THEN 1 END
   ELSE 1 END
WHEN 5
      THEN CASE WHEN n in (2, 4, 6 ,8)
   THEN CASE WHEN MOD(CONNECT_BY_ROOT(n), 2) = 0 THEN 1 END
   WHEN n = 5
            THEN CASE WHEN CONNECT_BY_ROOT(n) in (5 ) THEN 1 END
   ELSE 1 END
WHEN 6
      THEN CASE WHEN n in (2, 4, 6 ,8)
   THEN CASE WHEN MOD(CONNECT_BY_ROOT(n), 2) = 0 THEN 1 END
   WHEN n = 5
               THEN CASE WHEN CONNECT_BY_ROOT(n) in (5) THEN 1 END
   ELSE 1 END
      WHEN 7
      THEN CASE WHEN n in (2, 4, 6 ,8)
   THEN CASE WHEN MOD(CONNECT_BY_ROOT(n), 2) = 0 THEN 1 END
   WHEN n = 5
   THEN CASE WHEN CONNECT_BY_ROOT(n) in (5) THEN 1 END
   ELSE 1 END
      ELSE 1 END = 1
   )
   CONNECT BY PRIOR str_num = str_num
   AND LEVEL <= length(str_num)
   AND PRIOR DBMS_RANDOM.STRING ('P',20) IS NOT NULL
)
GROUP BY str_num
HAVING count(CASE WHEN mod(str_num, n1) = 0
                  THEN 1 END ) = length(str_num)
ORDER BY str_num DESC
)
WHERE ROWNUM  = 1;

STR_NUM
———-
9867312

我觉得他的写法在两处WHEN n in (4)  THEN CASE WHEN MOD(to_number(PRIOR N||N), n) = 0 THEN 1 END 有错误。

我的11GR2解法：
WITH n AS (SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
,t(d1,d2,d3,d4,d5,d6,d7,num,lvl) AS (
SELECT n,0,0,0,0,0,0,TO_CHAR(n),1 FROM n
UNION ALL
SELECT d1
   ,DECODE(lvl,1,n,d2)
   ,DECODE(lvl,2,n,d3)
   ,DECODE(lvl,3,n,d4)
   ,DECODE(lvl,4,n,d5)
   ,DECODE(lvl,5,n,d6)
   ,DECODE(lvl,6,n,d7)
   ,CAST(n||num AS VARCHAR2(7))
   ,lvl+1
  FROM t,n
WHERE INSTR(TO_CHAR(num),TO_CHAR(n))=0
   AND lvl<8
   AND (n=5 AND d1 IN (0,5)
         OR n IN (1,3,7,9)
         OR n IN (2,6) AND d1 IN (2,4,6,8,0)
         OR n=4 AND d1 IN (2,4,6,8,0) AND (lvl=1
                                          OR MOD(d2*10+d1,4)=0
                                          )
         OR n=8 AND d1 IN (2,4,6,8,0) AND (lvl=1
                                          OR lvl=2 AND MOD(n*1000+d2*10+d1,8)=0
                                          OR lvl>2 AND MOD(d3*1000+d2*10+d1,8)=0
                                          )
         )
)
SELECT * FROM (
SELECT num FROM t
WHERE lvl=7
   AND MOD(num,d1)=0 AND MOD(num,d2)=0 AND MOD(num,d3)=0 AND MOD(num,d4)=0 AND MOD(num,d5)=0
   AND MOD(num,d6)=0 AND MOD(num,d7)=0
ORDER BY num DESC
)
WHERE ROWNUM=1;

NUM
----------------------------------------
9781632

[ 本帖最后由 newkid 于 2010-6-25 02:36 编辑 ]

newkid · 发表于 2010-6-25 03:00

这个比较普通：
http://oraqa.com/2008/12/18/how- ... duct-puzzle-in-sql/

找出1-9构成的两个数，比如1234 和 56789，使得它们的乘积最大。

How to solve the Find Maximum Possible Product Puzzle in SQL

December 18th, 2008 By Frank Zhou

The following is an interesting problem posted by mathforum.org:

Use all the digits from 1 to 9 without repeating, to form two numbers such that their product is maximum. A digit used should be unique across both the numbers. For example, the numbers formed could be 1234 and 56789.

—————————————— SQL Solution——————————————————
SELECT n1, n2, product as MAX_PRODUCT
FROM
(SELECT max(n1 * n2 ) over ( ) max_product, n1, n2, n1 * n2 product
FROM
(
  WITH DATA AS
  (SELECT replace(sys_connect_by_path(num, ','), ',') str_num
FROM (SELECT LEVEL num FROM dual CONNECT BY LEVEL <10)
WHERE LEVEL = 9
START WITH num = 9
CONNECT BY NOCYCLE PRIOR num != num
AND LEVEL <= 9
  )
  SELECT to_number(substr(str_num,0,LEVEL)) n1, to_number(substr(str_num,LEVEL+1)) n2
  FROM DATA
  CONNECT BY PRIOR str_num = str_num
AND LEVEL <= length(str_num)-1
  AND PRIOR DBMS_RANDOM.STRING ('P',20) IS NOT NULL
)
)
WHERE max_product = product;

      N1                N2                MAX_PRODUCT
----------             ----------             -----------
   9642             87531                   843973902

第二个CONNECT BY用了奇怪的PRIOR DBMS_RANDOM.STRING ('P',20) IS NOT NULL(假如不这么做就会报错）
我给他修改一下，速度快了很多：
SELECT n1, n2, product as MAX_PRODUCT
FROM
(SELECT max(n1 * n2 ) over ( ) max_product, n1, n2, n1 * n2 product
FROM
(
  WITH DATA AS
  (SELECT replace(sys_connect_by_path(num, ','), ',') str_num
FROM (SELECT LEVEL num FROM dual CONNECT BY LEVEL <10)
WHERE LEVEL = 9
START WITH num = 9
CONNECT BY NOCYCLE PRIOR num != num
AND LEVEL <= 9
  )
  SELECT to_number(substr(str_num,1,rn)) n1, to_number(substr(str_num,rn+1)) n2
  FROM DATA,(SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=8)
)
)
WHERE max_product = product;

newkid · 发表于 2010-6-25 05:25

11楼理解有问题，用translate是不行的。

newkid · 发表于 2010-6-25 06:06

11楼：
WITH w AS (
SELECT word
   ,UPPER(SUBSTR(word,rn,1)) c
   ,rn
  FROM dictionary, (SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=(SELECT MAX(LENGTH(word)) FROM dictionary))
WHERE rn<=LENGTH(word)
)
,l AS (SELECT w1.word w1,w2.word w2
  FROM w w1,w w2
WHERE LENGTH(w1.word)=LENGTH(w2.word) AND w1.rn=w2.rn
   AND w1.word<>w2.word
GROUP BY w1.word,w2.word
HAVING COUNT(CASE WHEN w1.c=w2.c THEN 1 END)=MAX(LENGTH(w1.word))-1
)
SELECT *
  FROM (
SELECT SYS_CONNECT_BY_PATH(w1,',')||','||:end_str
FROM l
WHERE UPPER(w2) = UPPER(:end_str)
START WITH UPPER(w1) = UPPER(:begin_str)
CONNECT BY NOCYCLE w1 = PRIOR w2 AND UPPER(PRIOR w2) != UPPER(:end_str)
ORDER BY LEVEL
)
WHERE ROWNUM=1;

SYS_CONNECT_BY_PATH(W1,',')||','||:END_STR
-------------------------------------------------
,HEAD,heal,teal,tell,tall,tail

newkid · 发表于 2010-6-25 07:58

http://oraqa.com/2008/10/12/how- ... opes-puzzle-in-sql/

How to solve the 1000 $1 Bills in 10 Envelopes Puzzle in SQL
October 12th, 2008 By Frank Zhou

有1000张1元钞票，装入10个信封，要求满足1-1000的任何金额都可以用这几个信封凑出来。

The following is an interesting problem posted by mathforum.org:

You are given 1000 one dollar bills and 10 envelopes. Put the bills
into the envelopes in such a way that someone can ask you for any
amount of money from $1 to $1000 (examples $532, $619, $88, etc.)
and you can give it to them through a combination of the envelopes.

The following SQL pattern can be used to solve this puzzle, it also proves
that the result is correct.

————————————————–10G SQL Solution————————————————

SELECT ROW_NUMBER () OVER (ORDER BY num) envelope_num,
      num dollars,
      MIN from_min,
      MAX to_max,
      cnt combo_cnt
FROM (WITH DATA AS
            (SELECT num
               FROM (SELECT CASE
                              WHEN SUM (num) OVER (ORDER BY num) > 1000
                                 THEN num
                                       - (  SUM (num) OVER (ORDER BY num)
                                          - 1000
                                          )
                              ELSE num
                           END AS num
                        FROM (SELECT    POWER (2, LEVEL - 1) AS num
                                    FROM DUAL
                              CONNECT BY POWER (2, LEVEL - 1) <= 1000))),
            data_check AS
            (SELECT MAX (num) MAX,
                     MIN (num) MIN,
                     COUNT (*) cnt
               FROM (SELECT DISTINCT SUM
                                       (TO_NUMBER (REGEXP_SUBSTR (str,
                                                                  '[^,]+',
                                                                  1,
                                                                  LEVEL
                                                                  )
                                                   )
                                       ) num
                                 FROM (SELECT    SYS_CONNECT_BY_PATH (num,
                                                                     ','
                                                                     ) str
                                             FROM (SELECT num
                                                   FROM DATA)
                                       CONNECT BY PRIOR num < num)
                           CONNECT BY PRIOR str = str
                                 AND REGEXP_SUBSTR (str, '[^,]+', 1, LEVEL) IS NOT NULL
                                 AND PRIOR DBMS_RANDOM.STRING ('p', 20) IS NOT NULL
                           GROUP BY str))
      SELECT MAX,
               MIN,
               cnt,
               num
         FROM data_check FULL OUTER JOIN DATA ON (data_check.MIN = DATA.num
                                                )
               )
ORDER BY num NULLS FIRST;

SQL> /

ENVELOPE_NUM DOLLARS    FROM_MIN    TO_MAX    COMBO_CNT
------------ ---------- ---------- ---------- ----------
1             1             1       1000       1000
2             2
3             4
4             8
5          16
6          32
7          64
8          128
9          256
10          489

10 rows selected.

Elapsed: 00:00:00.43

其实这是人脑找到的答案，不能算是SQL找出来的，SQL只是验证而已。我用的另一种验证方法：

WITH DATA AS (SELECT num,MAX(num) OVER() m
            FROM (SELECT CASE
                              WHEN SUM (num) OVER (ORDER BY num) > 1000
                                 THEN num
                                    - (  SUM (num) OVER (ORDER BY num)
                                       - 1000
                                       )
                              ELSE num
                           END AS num
                     FROM (SELECT POWER (2, LEVEL - 1) AS num
                           FROM DUAL
                           CONNECT BY POWER (2, LEVEL - 1) <= 1000
                           )
                  )
            )
,TO_CHECK AS (SELECT ROWNUM n FROM DUAL CONNECT BY ROWNUM <=1000)
SELECT n
  FROM (
SELECT n,num
  FROM TO_CHECK, DATA
WHERE (CASE WHEN n>m THEN n-m ELSE n END)>num-1 AND BITAND((CASE WHEN n>m THEN n-m ELSE n END),num)>0 AND num < m
      OR (n>m AND num=m)
)
GROUP BY n HAVING SUM(num) != n

或者：

WITH DATA AS (SELECT num,MAX(num) OVER() m
            FROM (SELECT CASE
                              WHEN SUM (num) OVER (ORDER BY num) > 1000
                                 THEN num
                                    - (  SUM (num) OVER (ORDER BY num)
                                       - 1000
                                       )
                              ELSE num
                           END AS num
                     FROM (SELECT POWER (2, LEVEL - 1) AS num
                           FROM DUAL
                           CONNECT BY POWER (2, LEVEL - 1) < = 1000
                           )
                  )
            )
,TO_CHECK AS (SELECT ROWNUM n FROM DUAL CONNECT BY ROWNUM  <=1000)
SELECT num FROM DATA
WHERE NOT EXISTS (
SELECT n
  FROM (
SELECT n,num
  FROM TO_CHECK, DATA
WHERE (CASE WHEN n>m THEN n-m ELSE n END)>num-1 AND BITAND((CASE WHEN n>m THEN n-m ELSE n END),num)>0 AND num < m
      OR (n>m AND num=m)
)
GROUP BY n HAVING SUM(num) != n
)
;