puzzleup2012谜题，请用SQL或PLSQL解答

lastwinner

udfrog 发表于 2012-11-22 16:56
你们是当真有时间啊，我这被流放到日语项目组写sql去了，看不懂啊。。。

快来参加这个活动 http://www.itpub.net/thread-1736930-1-1.html
这个要简单多了

newkid

lastwinner 发表于 2012-11-24 00:13
按我280楼的思路
AB、AC……AF 开头的编码都是一样多的

这个不用说，牛蛙这么聪明，不会一个个去算的。

lastwinner

newkid 发表于 2012-11-24 00:16
这个不用说，牛蛙这么聪明，不会一个个去算的。

我这个不是说给牛蛙的，是说给你的或者说是说给看你回帖的人听的

newkid

#19 Palindromic Number

Using all 10 digits (0-9) only once, one 1-digit, one 2-digit, one 3-digit, and one 4-digit numbers are formed. When these four numbers are multiplied the result is a palindromic number. What can be the maximum value for this palindromic number?

用10个数字(0-9)每个只用一次，构成一个一位数，一个二位数，一个三位数，一个四位数。这四个数字的乘积是回文数。这个回文数最大可能是多少？

除了全排列，还有什么好方法？

ryax

Sub p191()
Dim a(11) As Integer
Dim b(11) As Integer
Dim k As Double
Dim m As Double
Dim n As Double
Dim m1 As Double
Dim m4 As Double
Dim m3 As Double
k = 0
For i = 0 To 9
a(i) = 1
Next i
k = 0
Call f(1, k, a(), b())
Cells(4, 12) = k
End Sub
Sub f(ByVal m As Double, k As Double, a() As Integer, b() As Integer)
If m = 11 Then
n = (1000# * b(7) + 100 * b(8) + 10 * b(9) + b(10)) * (100 * b(4) + 10 * b(5) + b(6)) * (10 * b(2) + b(3)) * b(1)
m4 = n
m3 = 0
'°ÑnµÄÄæÐò·Åµ½m3
Do While n > 9
   m1 = Int(n / 10)
   m2 = n - m1 * 10
   m3 = m3 * 10 + m2
   n = m1
Loop
m3 = m3 * 10 + n
'ÅжÏÊDz»ÊÇ»ØÎÄÊý
If m4 = m3 Then
   If m4 > k Then
   k = m4
   Cells(5, 6) = k
   For i = 1 To 10
      Cells(4, i) = b(i)
      Next i
   End If
End If
Else
   For i = 0 To 9
   If a(i) > 0 Then
      a(i) = a(i) - 1
      b(m) = i
      Call f(m + 1, k, a(), b())
      a(i) = a(i) + 1
   End If
   Next i
End If
End Sub

newkid

用很不雅的暴力法：
WITH t AS (
SELECT REPLACE(SYS_CONNECT_BY_PATH(n,'/'),'/') s
  FROM (SELECT LEVEL-1 n FROM DUAL CONNECT BY LEVEL<=10)
WHERE LEVEL=10
START WITH n>0
CONNECT BY NOCYCLE LEVEL<=10 AND  n<>PRIOR n
)
SELECT SUBSTR(s,1,1)||'*'||SUBSTR(s,2,2)||'*'||SUBSTR(s,4,3)||'*'||SUBSTR(s,7)||'='||p
  FROM (
       SELECT * FROM (
               SELECT s,TO_CHAR(SUBSTR(s,1,1)*SUBSTR(s,2,2)*SUBSTR(s,4,3)*SUBSTR(s,7)) p
                 FROM t
               )
       WHERE p=REVERSE(p)
       ORDER BY TO_NUMBER(p) DESC
       )
WHERE ROWNUM=1;

SUBSTR(S,1,1)||'*'||SUBSTR(S,2,2)||'*'||SUBSTR(S,4,3)||'*'||SUBSTR(S,7)||'='||P
----------------------------------------------------------------------------------
6*58*921*7304=2340990432

Elapsed: 00:01:15.99

lastwinner

newkid 发表于 2012-11-28 23:44
#19 Palindromic Number

Using all 10 digits (0-9) only once, one 1-digit, one 2-digit, one 3-digit ...

基本上只能全排列了，但可以提前做一些过滤，比如若某数尾数为5，则另外三个数中任何一个的尾数不拿是偶数
1位数不可能是0。当然，也不太可能是1（这个纯属猜测，实际计算时还是需要考虑的）
除了1位数，其他数的第一位不能是0，最后一位也不能是0

lastwinner

WITH t1 AS (
SELECT REPLACE(SYS_CONNECT_BY_PATH(n,'/'),'/') s
  FROM (SELECT LEVEL-1 n FROM DUAL CONNECT BY LEVEL<=10)
WHERE LEVEL=10 START WITH n>0 CONNECT BY NOCYCLE LEVEL<=10 AND  n<>PRIOR n
),
t2 as (select TO_NUMBER(SUBSTR(s,1,1)) a, TO_NUMBER(SUBSTR(s,2,2)) b, TO_NUMBER(SUBSTR(s,4,3)) c, TO_NUMBER(SUBSTR(s,7)) d, s
               from t1 where '0' in (SUBSTR(s,5,1), SUBSTR(s,8,1), SUBSTR(s,9,1))
               --instr(SUBSTR(s,5,1)||SUBSTR(s,8,2),'0')>0
               ),
t as (select a,b,c,d,s from t2)
SELECT a||'*'||b||'*'||c||'*'||d||'='||p
  FROM (
       SELECT * FROM (
               SELECT a,b,c,d,s,TO_CHAR(a*b*c*d) p
                 FROM t where 0 not in (mod(a*b,10),mod(a*c,10),mod(a*d,10),
                         mod(c*b,10),mod(d*b,10),mod(c*d,10))
               )
       WHERE p=REVERSE(p)
       ORDER BY TO_NUMBER(p) DESC
       )
WHERE ROWNUM=1;

时间上几乎没改善

〇〇

万里挑一
SQL> WITH t AS (
  2  SELECT REPLACE(SYS_CONNECT_BY_PATH(n,'/'),'/') s
  3    FROM (SELECT LEVEL-1 n FROM DUAL CONNECT BY LEVEL<=10)
  4  WHERE LEVEL=10
  5  START WITH n>0
  6  CONNECT BY NOCYCLE LEVEL<=10 AND  n<>PRIOR n
  7  )
  8  SELECT count(*) --SUBSTR(s,1,1)||'*'||SUBSTR(s,2,2)||'*'||SUBSTR(s,4,3)||'*'||SUBSTR(s,7)||'='||p
  9    FROM (
10         SELECT * FROM (
11                 SELECT s,TO_CHAR(SUBSTR(s,1,1)*SUBSTR(s,2,2)*SUBSTR(s,4,3)*SUBSTR(s,7)) p
12                   FROM t
13                 )
14         WHERE p=REVERSE(p)
15         --ORDER BY TO_NUMBER(p) DESC
16         )
17  WHERE ROWNUM=1;


COUNT(*)--SUBSTR(S,1,1)||'*'||SUBSTR(S,2,2)||'*'||SUBSTR(S,4,3)||'*'||SUBSTR(S,7)||'='||P
-----------------------------------------------------------------------------------------
                                                                                        1

已用时间:  00: 00: 00.04
SQL> SQL> 17
17* WHERE ROWNUM=1
SQL> c/=/>=
17* WHERE ROWNUM>=1
SQL> /

COUNT(*)--SUBSTR(S,1,1)||'*'||SUBSTR(S,2,2)||'*'||SUBSTR(S,4,3)||'*'||SUBSTR(S,7)||'='||P
-----------------------------------------------------------------------------------------
                                                                                      209

已用时间:  00: 01: 07.42
SQL> WITH t AS (
  2  SELECT REPLACE(SYS_CONNECT_BY_PATH(n,'/'),'/') s
  3    FROM (SELECT LEVEL-1 n FROM DUAL CONNECT BY LEVEL<=10)
  4  WHERE LEVEL=10
  5  START WITH n>0
  6  CONNECT BY NOCYCLE LEVEL<=10 AND  n<>PRIOR n
  7  )
  8  SELECT count(*)
  9  from t;

  COUNT(*)
----------
   3265920

已用时间:  00: 00: 56.37

〇〇

似乎都是偶数
17* WHERE ROWNUM<=50
SQL> /

SUBSTR(S,1,1)||'*'||SUBSTR(S,2,2)||'*'||SUBSTR(S,4,3)||'*'||SUBSTR(S,7)||'='||P
------------------------------------------------------------------------------------------------------------------------
6*58*921*7304=2340990432
3*89*602*5417=870696078
8*69*204*7531=848050848
2*57*814*9063=841010148
7*51*963*2408=827848728
3*67*951*4208=804363408
9*74*562*1803=674848476
6*58*207*9341=672888276
6*47*251*9308=658838856
3*97*562*4018=657111756
8*93*142*6057=639909936
9*46*708*2153=631070136
2*71*986*4503=630474036
9*13*854*6207=620191026
4*36*809*5271=614050416
4*63*251*9708=614050416
7*18*962*5043=611272116
8*29*417*5036=487202784
1*63*982*7504=464242464
2*91*436*5807=460797064
1*94*638*7502=449909944
8*92*106*5734=447343744
8*37*516*2904=443545344
6*14*583*9027=442070244
6*38*214*9057=441909144
6*57*428*3019=441909144
3*96*548*2701=426282624
3*91*206*7548=424484424
9*42*703*1586=421454124
1*92*758*6034=420787024
7*39*248*6051=409676904
2*68*739*4051=407141704
8*57*103*6294=295616592
1*79*826*4053=264474462
1*98*356*7204=251333152
7*69*403*1258=244868442
6*09*814*5372=236131632
9*06*814*5372=236131632
2*74*306*5189=234999432
6*37*204*5189=234999432
4*36*791*2058=234414432
6*09*514*8372=232373232
9*06*514*8372=232373232
3*49*201*7856=232121232
3*56*982*1407=232121232
7*49*108*6253=231636132
3*14*962*5708=230626032
8*57*163*2904=215848512
6*74*091*5328=215272512
6*91*074*5328=215272512