Puzzleup 2010 比赛快开始了，大家用SQL解答啊

newkid

#8:

Generating Numbers



Applying the steps below, you will generate a number, on the condition that every digit of a number produced in each step is different from its other digits.

1. Write down a number with one, two or three digits.
2. Delete at most three consecutive digits and in the places of the deleted digits place the square of the number formed by these digits.
3. For the number you get, repeat steps two and three. If you cannot get a number that satisfies the conditions, stop.

What is the largest number that can be generated through this mechanism?

Example: 307, 3(07), 349, 3(4)9, 3169, ...

lastwinner

原帖由 newkid 于 10-9-1 21:51 发表
#8:

Generating Numbers



Applying the steps below, you will generate a number, on the condition that every digit of a number produced in each step is different from its other digits.

1. Write down a number with one, two or three digits.
2. Delete at most three consecutive digits and in the places of the deleted digits place the square of the number formed by these digits.
3. For the number you get, repeat steps two and three. If you cannot get a number that satisfies the conditions, stop.

What is the largest number that can be generated through this mechanism?

Example: 307, 3(07), 349, 3(4)9, 3169, ...

#8  数字生成
依照下列步骤，你将可以生成一个数字，在每一步中，该数中新生成的每一位都和该数字其他的位不一样：
1、随便写个1或2或3位数
2、最多删除该数中连续的三位（比如14235中，235为连续的三位，而123并不是连续的，中间隔了一个4），并将删除部分替换为其平方数
3、从2中你将得到一个新数字，重复前两个步骤直到你再也不能获得一个满足条件的数字

根据上述规则，你能得到的最大的数字是什么？


举个例子：
307，将07删除并替换为其平方，得349
349，将4 cut并paste其平方，得3169
………………

lastwinner

这个题要用到数字平方的常识
比如一个数不断的平方平方再平方……，最终其尾数只可能是0、1、5、6
而0×0＝0，1×1＝1，所以题中没必要尝试去单独删0或者1

dingjun123

对于连续的最多删除3位，然后将删除数字替换为其平方数，变成新数字，每个数字的每一位还有其他的不一样

我晕，这不是大海捞针嘛，伤脑细胞啊

lastwinner

5的平方25
25的偶数次方，结尾一定是25
6^2=36
36^2=1296

于是可以利用这样的特性，来重复使用5和6


而任何数的平方的末位数都不可能是7、8、3、2这四个数
所以可以考虑将其作为首先写下其中的三个数
另外只有0的平方才能得到尾数是0的数，为了充分利用0～9这10个数字，0也要做考虑
2、3、7、8虽然不可能是平方数的末位数，但是有可能是平方数的倒数第二位数、倒数第三位数
比如6^2=36, 17^2 = 289


我决定了，我将7和0首先写上，0写在末位，明天开始尝试，嘿嘿

newkid

递归暴力法：


WITH p AS (
SELECT pos,l
   FROM (SELECT ROWNUM pos FROM DUAL CONNECT BY ROWNUM<=10),(SELECT ROWNUM l FROM DUAL CONNECT BY ROWNUM<=3)
  )
,t (str,len,path) AS (
SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') ,LEVEL,REPLACE(SYS_CONNECT_BY_PATH(n,','),',')
  FROM (SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
START WITH n>0
CONNECT BY NOCYCLE LEVEL<=3
UNION ALL
SELECT SUBSTR(str,1,p.pos-1)||TO_CHAR(SUBSTR(str,p.pos,p.l)*SUBSTR(str,p.pos,p.l))||SUBSTR(str,p.pos+p.l)
       ,LENGTH(SUBSTR(str,1,p.pos-1)||TO_CHAR(SUBSTR(str,p.pos,p.l)*SUBSTR(str,p.pos,p.l))||SUBSTR(str,p.pos+p.l))
       ,path||','||SUBSTR(str,1,p.pos-1)||TO_CHAR(SUBSTR(str,p.pos,p.l)*SUBSTR(str,p.pos,p.l))||SUBSTR(str,p.pos+p.l)
   FROM t,p
  WHERE p.pos+p.l-1<=t.len
        AND LENGTH(TRANSLATE('1234567890','$'||SUBSTR(str,1,p.pos-1)||TO_CHAR(SUBSTR(str,p.pos,p.l)*SUBSTR(str,p.pos,p.l))||SUBSTR(str,p.pos+p.l),'$'))
            = 10 - LENGTH(SUBSTR(str,1,p.pos-1)||TO_CHAR(SUBSTR(str,p.pos,p.l)*SUBSTR(str,p.pos,p.l))||SUBSTR(str,p.pos+p.l))
)
CYCLE str SET cycle_flag TO 'Y' DEFAULT 'N'   
SELECT path FROM (
SELECT * FROM t ORDER BY len DESC,str DESC
)
WHERE ROWNUM=1;



PATH
--------------------------------------------------------------
387,3849,382401,982401,9857601,98257601,98457601,984573601

dingjun123

对newkid大哥，我只能远远地膜拜

newkid

递归思路很简单，而且很模式化，写多了就像套路。那些人肉方法的奇思妙想才是值得赞叹的。

加个括号输出好看一点：
WITH p AS (
SELECT pos,l
   FROM (SELECT ROWNUM pos FROM DUAL CONNECT BY ROWNUM<=10),(SELECT ROWNUM l FROM DUAL CONNECT BY ROWNUM<=3)
  )
,t (str,len,path) AS (
SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') ,LEVEL,''
  FROM (SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
START WITH n>0
CONNECT BY NOCYCLE LEVEL<=3
UNION ALL
SELECT SUBSTR(str,1,p.pos-1)||TO_CHAR(SUBSTR(str,p.pos,p.l)*SUBSTR(str,p.pos,p.l))||SUBSTR(str,p.pos+p.l)
       ,LENGTH(SUBSTR(str,1,p.pos-1)||TO_CHAR(SUBSTR(str,p.pos,p.l)*SUBSTR(str,p.pos,p.l))||SUBSTR(str,p.pos+p.l))
       ,path||SUBSTR(str,1,p.pos-1)||'('||SUBSTR(str,p.pos,p.l)||')'||SUBSTR(str,p.pos+p.l)||','
   FROM t,p
  WHERE p.pos+p.l-1<=t.len
        AND LENGTH(TRANSLATE('1234567890','$'||SUBSTR(str,1,p.pos-1)||TO_CHAR(SUBSTR(str,p.pos,p.l)*SUBSTR(str,p.pos,p.l))||SUBSTR(str,p.pos+p.l),'$'))
            = 10 - LENGTH(SUBSTR(str,1,p.pos-1)||TO_CHAR(SUBSTR(str,p.pos,p.l)*SUBSTR(str,p.pos,p.l))||SUBSTR(str,p.pos+p.l))
)
CYCLE str SET cycle_flag TO 'Y' DEFAULT 'N'   
SELECT path||str FROM (
SELECT * FROM t ORDER BY len DESC,str DESC
)
WHERE ROWNUM=1;



PATH||STR
------------------------------------------------------------------------------
38(7),38(49),(3)82401,98(24)01,98(5)7601,98(2)57601,98457(6)01,984573601

〇〇

时间有点长

PATH||STR
----------------------------------------------------------------------------
----------------
38(7),38(49),(3)82401,98(24)01,98(5)7601,98(2)57601,98457(6)01,984573601

已用时间:  00: 02: 01.36

lastwinner

bs，居然不贴sql