ITPUB论坛－专业的IT技术社区

标题: Puzzleup 2010 比赛快开始了，大家用SQL解答啊 [打印本页]

作者: 〇〇 时间: 2010-7-10 20:07
标题: Puzzleup 2010 比赛快开始了，大家用SQL解答啊
http://www.puzzleup.com/2010/

作者: 〇〇 时间: 2010-7-10 20:08
Competition Rules and Regulations
1. The competition starts on 14th July 2010 and consists of 20 problems which will be posted every week.

2. New problems will be posted every Wednesday at 11:00 (GMT). Each new problem is finalized in the following 24 hours (i.e. checked for possible revisions, changes, extra information, etc.) and the answering period starts on Thursdays at 11:00 (GMT).

3. Competitors may start the competition at any time during the 24 week period, and answer problems from past weeks.

4. Each user may join the competition with a single name/membership.

5. Do not write explanations when answering problems. Respond numerically unless the opposite is requested. Otherwise your answer will be evaluated as wrong.

6. Competitors may be required to justify their answers. In such cases, the particular problem is evaluated according to the justification/explanation.

7. For your comments and suggestions you can use the [comments] section. Please do not discuss/share answers or tips in your messages. Also please keep in mind that every message will be read, but since this section is not a "forum", not all of them will be published or answered.

8. Each correct answer is 100 points and users may additionally collect two types of extra points. These are given depending on (a) the answering day of each user and (b) the percentage of correct answers given by all users to the same problem. More specifically:

  a. Competitors receive 5 points for each answer they provide on the first answering day (Thursday 11:00 - Friday 10:59 GMT) of the first week, 4 points for each answer on the second day (Friday 11:00 - Saturday 10:59 GMT), 3 for each answer on the third day (Saturday 11:00 - Sunday 10:59 GMT), 2 for each answer on the fourth day (Sunday 11:00 - Monday 10:59 GMT), 1 for each answer on the fifth day (Monday 11:00 - Tuesday 10:59 GMT). No extra points are given for correct answers to problems from past weeks.

  b. (100-the correct answer percentage of all users) is added to the total points.
For example: Suppose that a competitor has answered a certain problem on the fifth day and the same problem was answered correctly by 30 of the 50 competitors who responded. In this case, 100 points for answering the problem correctly, another 1 point for answering on the fifth day, and 40 extra points (because 30 out of 50 users answered that problem correctly) will be given. The competitor receives 141 points (100 + 1 +[ 100-(100*30/50) ] = 141 ) in total.

9. Competitors may change their answers but this is limited to 4 times only (5 answering options in total). 20 points will be subtracted from 100 points as each change is made by the competitor. (1st answer-no change:100 points, 2nd answer:80 points, 3rd answer:60 points, 4th answer: 40 points, 5th answer: 20 points).

10. The scoreboard is updated approximately once a month. The points on the scoreboard correspond to correct answers for randomly chosen problems and include bonus points. (The number of randomly chosen problems is equal to half of the total number of problems). The final calculation will be made at the end of the competition, and the competitors will be able to  examine their scores for all the problems for a 1 week period.

11. Certificates will be e-mailed to the winners; the 10 competitors with the highest points. There are no rewards.

12. The answers and the solutions will not be announced. The ideas behind the reason for this can be found in the passage taken from the speech made by Emrehan Halici regarding this rule.

13. The problems in the competition are composed by Emrehan Halýcý, and fall into three different groups:

a. Different versions of formerly published, poorly-known problems

b. Problems based on a mathematical theory or formula

c. Original problems

14. Any problem may be cancelled due to reasons such as faulty problems, or similar problems published in another commonly used medium. In such cases, the cancellation will be announced on the PuzzleUp website and scores will be re-calculated. Objections regarding these problems are to be evaluated at the end of the competition. The deadline for objections will be announced at the end of answering period.

15. The PuzzleUp board has the right to make amendments on these rules. Once amendments have been made, they will be stated in the rules page, and announced on the main page.

16. The PuzzleUp board has the right to disqualify any competitor who violates these rules or any other ethical rule.

17. All competitors are expected to have read and accepted these rules.

作者: newkid 时间: 2010-7-11 08:45
20周，这么长的周期？
记得你去年也贴了好几个问题，但能用上SQL的并不多，而且他们网站都没有答案，也不知道做对了没有。

作者: 〇〇 时间: 2010-7-14 20:11

No: 01 July 14, 2010

Equilateral Triangles

You are using a drawing program on a computer. You place several equilateral triangles of the same size on the screen. You observe that you can cover any of these triangles by moving the other triangles without rotating.

What is the minimum number of triangles you have to place on the screen to ensure that this observation holds true for every case?

[ You can answer this problem starting from Thursday at 11:00 (GMT) ]
today's bonus: -- points

answers: # 0 popularity: 75.0 % difficulty: 75.0 %

作者: newkid 时间: 2010-7-14 21:34
看不懂，放两个一样大小的不就行了吗（角度也要一样）？
这个肯定和SQL没什么关系。

作者: newkid 时间: 2010-7-23 23:45
Round Table

A group of people is sitting around a round table. They give a coffee break. When they return to the table after the break, they sit down randomly. Interestingly, they notice that the six closest persons sitting next to each one of them (three to the left, and three to the right) are completely different from the six closest persons in the previous setting.

At least how many persons should be there?

作者: newkid 时间: 2010-7-23 23:51
圆桌问题：
一群人围着圆桌而坐。他们起来喝完咖啡，随机坐回座位，发现相邻的六人（左边三位和右边三位）和先前完全不同。满足这种情形的最少人数是多少？

用11GR2的SQL模拟一下，因为最少要13人，从N=13开始把N逐步增加, 发现N=17的时候有了答案：

VAR N NUMBER;
EXEC :N := 17;

WITH t (n,str,cnt,first2,first3,last2,last3) AS (
SELECT 1,CAST(',1,' AS VARCHAR2(1000)),1,-9999,-9999,-9999,-9999 FROM DUAL
UNION ALL
SELECT rn
   ,t.str||rn||','
   ,t.cnt+1
   ,DECODE(t.cnt,1,rn,t.first2)
   ,DECODE(t.cnt,2,rn,t.first3)
   ,t.n
   ,t.last2
  FROM t,(SELECT ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM<:N)
WHERE INSTR(t.str,','||rn||',')=0
   AND t.cnt<:N
   AND NOT (ABS(rn-t.n)<=3
            OR ABS(rn-t.last2)<=3
            OR ABS(rn-t.last3)<=3
            OR (t.cnt>=:N-3 OR t.cnt<4) AND rn IN (2,3,4,:N,:N-1,:N-2)
            OR t.cnt>=:N-2 AND ABS(rn-t.first2)<=3
            OR t.cnt =:N-1 AND ABS(rn-t.first3)<=3
            OR rn=2 AND (n>:N-2 OR t.last2>:N-2  OR t.last3>:N-2  )
            OR rn=3 AND (n>:N-1 OR t.last2>:N-1  OR t.last3>:N-1  )
            OR rn=:N-1 AND (n=2 OR t.last2=2       OR t.last3=2    )
            OR rn=:N AND (n<4 OR t.last2 IN (2,3) OR t.last3 IN (2,3))
            )
)
SELECT TRIM(BOTH ',' FROM str) FROM t WHERE cnt=:N
;

另一类似写法：
WITH d AS (
SELECT ROWNUM+1 rn
   ,ROWNUM+1-3 min1
   ,ROWNUM+1+3 max1
   ,CASE WHEN ROWNUM+1<=3 THEN :N + ROWNUM+1 -3
         WHEN ROWNUM+1>=:N-2 THEN 1
         ELSE 0
   END min2
   ,CASE WHEN ROWNUM+1<=3 THEN :N
         WHEN ROWNUM+1>=:N-2 THEN ROWNUM+1 + 3 - :N
         ELSE 0
   END max2
FROM DUAL CONNECT BY ROWNUM<:N
)
,t (n,str,cnt,first2,first3,last2,last3) AS (
SELECT 1,CAST(',1,' AS VARCHAR2(1000)),1,-9999,-9999,-9999,-9999 FROM DUAL
UNION ALL
SELECT rn
   ,t.str||rn||','
   ,t.cnt+1
   ,DECODE(t.cnt,1,rn,t.first2)
   ,DECODE(t.cnt,2,rn,t.first3)
   ,t.n
   ,t.last2
  FROM t,d
WHERE INSTR(t.str,','||rn||',')=0
   AND t.cnt<:N
   AND NOT ( t.n    BETWEEN d.min1 AND d.max1 OR t.n    BETWEEN d.min2 AND d.max2
            OR t.last2 BETWEEN d.min1 AND d.max1 OR t.last2 BETWEEN d.min2 AND d.max2
            OR t.last3 BETWEEN d.min1 AND d.max1 OR t.last3 BETWEEN d.min2 AND d.max2
            OR t.cnt>=:N-3 AND (1       BETWEEN d.min1 AND d.max1 OR 1       BETWEEN d.min2 AND d.max2)
            OR t.cnt>=:N-2 AND (t.first2 BETWEEN d.min1 AND d.max1 OR t.first2 BETWEEN d.min2 AND d.max2)
            OR t.cnt =:N-1 AND (t.first3 BETWEEN d.min1 AND d.max1 OR t.first3 BETWEEN d.min2 AND d.max2)
            )
)
SELECT TRIM(BOTH ',' FROM str) FROM t WHERE cnt=:N
;

LTRIM(REPLACE(STR,''),',')
------------------------------------------------
1,5,9,13,17,4,8,12,16,3,7,11,15,2,6,10,14
1,14,10,6,2,15,11,7,3,16,12,8,4,17,13,9,5

两个答案其实是一样的，只是顺时针和逆时针而已。

[ 本帖最后由 newkid 于 2010-7-24 04:12 编辑 ]

作者: lastwinner 时间: 2010-7-25 12:44
sql不是万能的

作者: newkid 时间: 2010-7-29 06:10
Sums of Square Numbers

Which is the smallest number that can be expressed as the sum of six different square numbers, but cannot be expressed as the sum of five different square numbers?

WITH d AS (SELECT ROWNUM*ROWNUM n FROM DUAL CONNECT BY ROWNUM<=10)
,t(lvl,n,s,str) AS (
SELECT 1,n,n,TO_CHAR(n) FROM d
UNION ALL
SELECT lvl+1,d.n,t.s+d.n,t.str||'+'||d.n
  FROM d,t
WHERE t.lvl<=5 AND t.n<d.n
)
SELECT s,str FROM
(SELECT t1.*
  FROM (SELECT * FROM t WHERE lvl=6) t1
   ,(SELECT * FROM t WHERE lvl=5) t2
WHERE t1.s = t2.s(+)
   AND t2.s IS NULL
ORDER BY t1.s
)
WHERE ROWNUM=1;

      S STR
---------- ---------------------------------
      91 1+4+9+16+25+36

作者: 〇〇 时间: 2010-7-29 08:18
标题: 回复 #9 newkid 的帖子
直接就是最小的那个啊,只要证明没有2个平方数之和也是平方数
9+16虽然是25，但是，25已经存在，不算different

作者: newkid 时间: 2010-7-29 08:55
要么是我理解错了，要么就是题目写反了。

作者: newkid 时间: 2010-7-29 22:17
他们加了个注释：(Square numbers: 0, 1, 4, 9, 16, 25, ...)
无非就是从0开始，用同样的方法求出来：1+4+9+16+25+49=104

不会这么肤浅吧？

作者: 〇〇 时间: 2010-7-30 05:46
标题: 回复 #12 newkid 的帖子
为什么不能用36?

作者: newkid 时间: 2010-7-30 06:10
因为
1+4+9+16+25+36 = 0+1+16+25+49 = 91

作者: 〇〇 时间: 2010-8-2 09:56
标题: 回复 #14 newkid 的帖子
去掉0，5个平方数实际是4个
那就是还要去掉a^2+b^2+c^2=d^2的情况
4+9+36=49

作者: 〇〇 时间: 2010-8-5 12:17

No: 04 August 04, 2010

Impossible Square Sum

What is the largest number that cannot be expressed as a sum of different square numbers?
[ You can answer this problem starting from Thursday at 11:00 (GMT) ]
today's bonus: -- points

answers: # 0 popularity: 31.3 % difficulty: 31.3 %

作者: 〇〇 时间: 2010-8-5 12:18
0?
不对，2 3 都不能表示，4=0+4 5=1+4 6不能 7不能

[ 本帖最后由〇〇于 2010-8-5 12:24 编辑 ]

作者: 〇〇 时间: 2010-8-5 12:18
1=0+1

作者: newkid 时间: 2010-8-5 23:00
我很怀疑这题有没有答案？

作者: lastwinner 时间: 2010-8-6 00:50

原帖由 newkid 于 10-8-5 23:00 发表
我很怀疑这题有没有答案？

同怀疑，但我现在找不到证明方法
明天写个sql，用排列组合求和，然后找缺失的数……

作者: 〇〇 时间: 2010-8-6 05:31
需要证明比较大的数都能表示成多个平方和...

作者: lastwinner 时间: 2010-8-6 09:40

原帖由〇〇于 10-8-6 05:31 发表
需要证明比较大的数都能表示成多个平方和...

对，但这个很难证明

作者: 〇〇 时间: 2010-8-6 09:49
with t as (select level*leve l from dual connect by level<=100)
,t1 as (select level l from dual connect by level<=1E4)
...

作者: lastwinner 时间: 2010-8-6 10:56
〇〇做啦？你要做了我就不做了

作者: 〇〇 时间: 2010-8-6 11:19
标题: 回复 #24 lastwinner 的帖子
我不做了，中午还要去还款...

作者: lastwinner 时间: 2010-8-6 13:19

原帖由 lastwinner 于 10-8-6 00:50 发表

同怀疑，但我现在找不到证明方法
明天写个sql，用排列组合求和，然后找缺失的数……

遵循该思路，但是，采用distinct level的方法，数据量太大太恐怖了（参阅 http://www.itpub.net/viewthread. ... p%3Bfilter%3Ddigest）

所以我采用一种变通的方法来尝试此问题
具体思路会在下面的程序中指明

先看表结构：

CREATE TABLE SQUARENUM
(
N NUMBER,
SN NUMBER
)
LOGGING
NOCOMPRESS
NOCACHE
NOPARALLEL
MONITORING;
COMMENT ON TABLE SQUARENUM IS '平方数基表';
CREATE UNIQUE INDEX SQUARENUM_PK ON SQUARENUM
(N)
LOGGING
NOPARALLEL;
ALTER TABLE SQUARENUM ADD (
CONSTRAINT SQUARENUM_PK
PRIMARY KEY
(N)
USING INDEX SQUARENUM_PK);
CREATE TABLE SUMSQUARE
(
S NUMBER,
CONSTRAINT SUMSQUARE_PK
PRIMARY KEY
(S)
USING INDEX SUMSQUARE_PK
)
ORGANIZATION INDEX
LOGGING
NOPARALLEL
MONITORING;
COMMENT ON TABLE SUMSQUARE IS '可拆分为不相同的平方数的和的数';
CREATE TABLE SUMSQUARE_P
(
CURRSN NUMBER
)
LOGGING
NOCOMPRESS
NOCACHE
NOPARALLEL
MONITORING;
COMMENT ON TABLE SUMSQUARE_P IS '指明当前操作处理到哪个数字了';

复制代码

再看数据初始化脚本：

insert into SUMSQUARE --将向表中插入前15个平方数任意组合后得到的和，去重后将不同和值以及0插入到表中
-- 0本质上不算符合条件的数，加入0只是为了便于后面存储过程的操作
select 0 from dual
union
select distinct dbms_aw.eval_number(xmlpath) from (
select sn, 0||sys_connect_by_path(sn, '+') xmlpath from
(select * from squarenum where n<=15)
connect by n<prior n
)
order by 1 asc;
Insert into SUMSQUARE_P (CURRSN) Values (0);
COMMIT;

复制代码

dbms_aw.eval_number 参阅 http://www.itpub.net/thread-1266657-1-1.html

以及存储过程（这是核心）

create or replace procedure insertss(st in number, en in number) as
v_n number:=-1;
begin
select currsn into v_n from sumsquare_p;
v_n :=greatest(st, v_n);
for v_n in st .. en loop
insert into SUMSQUARE
with tt as (select sn from SQUARENUM where n=v_n)
select distinct (num.sn+total.s) from tt num, SUMSQUARE total
minus
select s from SUMSQUARE where s>＝ (select sn from tt);
UPDATE SCOTT.SUMSQUARE_P SET CURRSN = v_n;
end loop;
end;
/

复制代码

该存储过程是将当前已有可拆分为不同平方数和的数与更大的一个平方数相加，然后从和中去除在sumsquare中已经存在的值
st和en分别表示开始和结束的平方数的平方根

在初始化完成后，sumsquare表中的数据指标情况如下：
sql> select max(s) maxs, count(*) cnt, max(s)-count(*) gap from sumsquare;

MAXS CNT GAP
---------- ---------- ----------
1240 1179 61

[ 本帖最后由 lastwinner 于 2010-8-6 13:22 编辑 ]

作者: lastwinner 时间: 2010-8-6 13:28
具体操作一下：

sql> exec insertss(16,50);

PL/SQL 过程已成功完成。

已用时间:  00: 00: 01.12
sql> select max(s) maxs, count(*) cnt, max(s)-count(*) gap from su
msquare;

   MAXS       CNT       GAP
---------- ---------- ----------
   42925    42864       61

sql> exec insertss(51,100);

PL/SQL 过程已成功完成。

已用时间:  00: 00: 14.82
sql> select max(s) maxs, count(*) cnt, max(s)-count(*) gap from su
msquare;

   MAXS       CNT       GAP
---------- ---------- ----------
338350    338289       61

已用时间:  00: 00: 00.03

gap值始终是61，这意味着在初始化数据完成后，至少从1240开始，以后的每个数都能表示为m个不同平方数的和

作者: 〇〇 时间: 2010-8-6 13:30
http://baike.baidu.com/view/942218.htm
四平方和定理说明所有正整数均可表示为最多四个平方数的和。但不是"不同"的平方数的和

作者: lastwinner 时间: 2010-8-6 13:44
ok，现在开始找缺失的数，最大的那个，可能就是题目要求的那个数
找缺失数的方法详见 http://www.itpub.net/thread-719692-1-1.html

with tt as (SELECT lags s, e
         FROM (SELECT  s,  s-1 e,
                        lag(s,1) OVER(ORDER BY s)+1 lags
                  FROM sumsquare
               )
         WHERE e-lags>=0
)
SELECT a.s+b.dis-1 h
FROM tt a,
   (SELECT rownum dis FROM
      (SELECT max(e-s+1) gap FROM tt)
   CONNECT BY rownum<=gap) b
WHERE a.s+b.dis-1<=a.e
ORDER BY 1;

当前已经进行到100的平方了，得到结果如下
sql>/

      H
----------
      2
      3
      6
      7
      8
      11
      12
      15
      18
      19
      22
      23
      24
      27
      28
      31
      32
      33
      43
      44
      47
      48
      60
      67
      72
      76
      92
      96
   108
   112
   128
338222
338238
338242
338254
338258
338274
338278
338283
338290
338302
338303
338306
338307
338317
338318
338319
338322
338323
338326
338327
338328
338331
338332
338335
338338
338339
338342
338343
338344
338347
338348

已选择62行。

后面一串6位数貌似不是答案，倒是128很像

再继续处理一些数：
sql>exec insertss(101,110);

PL/SQL 过程已成功完成。

已用时间:  00: 00: 07.26
sql>select max(s) maxs, count(*) cnt, max(s)-count(*) gap from sumsquare;

   MAXS       CNT       GAP
---------- ---------- ----------
449735    449674       61

已用时间:  00: 00: 00.09

找缺失的：
      H
----------
      2
      3
      6
      7
      8
      11
      12
      15
      18
      19
      22
      23
      24
      27
      28
      31
      32
      33
      43
      44
      47
      48
      60
      67
      72
      76
      92
      96
   108
   112
   128
449607
449623
449627
449639
449643
449659
449663
449668
449675
449687
449688
449691
449692
449702
449703
449704
449707
449708
449711
449712
449713
449716
449717
449720
449723
449724
449727
449728
449729
449732
449733

已选择62行。

再多的试验我不想做了，该题的答案应该是128，现在就是要证明为毛就是128……

作者: lastwinner 时间: 2010-8-6 13:44

原帖由〇〇于 10-8-6 13:30 发表
 http://baike.baidu.com/view/942218.htm
四平方和定理说明所有正整数均可表示为最多四个平方数的和。但不是"不同"的平方数的和

这个我看了，没毛用

作者: 〇〇 时间: 2010-8-6 14:13
ls打不出"啥"?

作者: lastwinner 时间: 2010-8-6 15:03

原帖由〇〇于 10-8-6 14:13 发表
ls打不出"啥"?

特殊时候，毛＝什么

作者: newkid 时间: 2010-8-6 23:08

原帖由 lastwinner 于 2010-8-6 15:03 发表

特殊时候，毛＝什么

这是哪里口音？我知道粤语的咩=什么

OO贴的链接里面有一个：
连续整数的和
　　平方数还可以表示成 n^2 = 1 + 1 + 2 + 2 + ... + n − 1 + n − 1 + n。例如，4^2 = 16 = 1 + 1 + 2 + 2 + 3 + 3 + 4。可以将其解释为在边长为 3 的矩形上添加宽度为 1 的一行和一列，即得到边长为 4 的矩形。这对于计算较大的数的平方数非常有用。例如， 52^2 = 50^2 + 50 + 51 + 51 + 52 = 2500 + 204 = 2704

似乎能用上，但我想了半天也没出来......

作者: lastwinner 时间: 2010-8-6 23:31

原帖由 newkid 于 10-8-6 23:08 发表

这是哪里口音？我知道粤语的咩=什么

OO贴的链接里面有一个：
连续整数的和
　　平方数还可以表示成 n^2 = 1 + 1 + 2 + 2 + ... + n − 1 + n − 1 + n。例如，4^2 = 16 = 1 + 1 + 2 + 2 + 3 + 3 + 4。可以将其解释为在边长为 3 的矩形上添加宽度为 1 的一行和一列，即得到边长为 4 的矩形。这对于计算较大的数的平方数非常有用。例如， 52^2 = 50^2 + 50 + 51 + 51 + 52 = 2500 + 204 = 2704

似乎能用上，但我想了半天也没出来......

这个我想过了，没法用上

从列出的31个不能拆分为不同平方数的和的数后，我就能证明
任何一个大于等于129的数A，都可以拆分为两个数A1和A2，这两个数分别可以由若干个不同的平方数组成
不过我无法由此推出，A可以由若干个不同的平方数组成

毛这个字，也许是这样演变的：
为什么？<=>为嘛？-->为毛（变音后得）
不过我觉得从你说的“咩”变过去的可能性更大

作者: 〇〇 时间: 2010-8-11 20:53
No: 05 August 11, 2010

Nine Balls

You have nine balls, three of which are slightly heavier, and three of which are slightly lighter than the normal three. All three balls in each group has the same weight. All nine balls are identical otherwise. Your mission is to determine the group of every ball using a pair of scales.

How many weighings are needed in order to ensure the accomplishment of your mission?
[ You can answer this problem starting from Thursday at 11:00 (GMT) ]

today's bonus: -- points

answers: # 0 popularity: 50.0 % difficulty: 25.0 %

作者: lastwinner 时间: 2010-8-11 21:22
标题: 回复 #35 〇〇的帖子
这题基本不可能用sql做出
现在我几乎没兴趣做这类IQ题了，太耗脑细胞～～

作者: newkid 时间: 2010-8-11 21:29
以前看过有人搞出一个通用公式的，但只适用于两种重量。

作者: 〇〇 时间: 2010-8-15 16:11
野花128的证明,那些人都是数学精
http://bbs.emath.ac.cn/viewthrea ... p;extra=&page=1

作者: lastwinner 时间: 2010-8-15 23:51

原帖由〇〇于 10-8-15 16:11 发表
野花128的证明,那些人都是数学精
http://bbs.emath.ac.cn/viewthrea ... p;extra=&page=1

——————————————————————————————
这样证明也可以吧：

记M(n)=[0, 255] +(16n)2
n=0,M(0)的元素只有上面31个不能写成不同平方数之和
假设n<=k时，M(k)的元素只有上面31个不能写成不同平方数之和
M(k+1)=[0, 255] +(16(k+1))2=[0, 255] +(16k)2 +32k+256
......

——————————————————————————————

这个？
就目前的文字而言，他的想法跟我的一样
提出的是证明的思路，但是并没有完成证明

作者: 〇〇 时间: 2010-8-16 06:19
pdf

SquareNumber.pdf

673.81 KB, 下载次数: 45

作者: newkid 时间: 2010-8-16 22:23

原帖由〇〇于 2010-8-16 06:19 发表
pdf

先下载，希望能看懂。

作者: newkid 时间: 2010-8-17 05:17
都是只有结论，看不到论文内容。

作者: lastwinner 时间: 2010-8-17 22:23

原帖由〇〇于 10-8-16 06:19 发表
pdf

别光写个pdf啊
要说明是干嘛用的，有没有跟哪个题目相关的

作者: newkid 时间: 2010-8-17 22:30
它只是提到：
There are only 31 numbers that cannot be expressed as the sum of distinct squares: 2, 3, 6, 7, 8, 11, 12, 15,
18, 19, 22, 23, 24, 27, 28, 31, 32, 33, 43, 44, 47, 48, 60, 67, 72, 76, 92, 96, 108, 112, 128 (Sloane's
A001422; Guy 1994; Savin 2000).

似乎有三篇论文：
http://www.research.att.com/~njas/sequences/A001422

Guy, R. K. "Sums of Squares" and "Squares with Just Two Different Decimal Digits." §C20 and F24 in Unsolved Problems in
Number Theory, 2nd ed. New York: Springer-Verlag, pp. 136-138, 147, and 262, 1994.

Savin, A. "Shape Numbers." Quantum 11, 14-18, 2000.

找不到内容，最多只有摘要。

作者: lastwinner 时间: 2010-8-17 22:50
标题: 回复 #44 newkid 的帖子
估计要看得花钱

这个题我的思路是用数学归纳法去证明
但怎么证我就不知道了

作者: newkid 时间: 2010-8-17 22:54
如果你认识哪个留学生，可以让他替你查，大学查论文是免费的。

作者: newkid 时间: 2010-8-19 05:03
Sixteen Numbers

You are going to place all numbers from 1 to 16 on a 4x4 chessboard such that all consecutive number pairs (1-2, 2-3, ..., 15-16) will be on the neighboring cells (left-right-top-down).

In how many different ways can this be done?

If the question was asked for a 2x2 chessboard, the answer would be 8.

把1-6放在8X8的棋盘上，使得所有相邻的数对(1-2,2-3,..., 15-16)在位置上也相邻(上下左右)。有多少种摆法？
以2X2为例，答案是8:
12
43

41
32

34
21

23
14

14
23

21
34

32
41

23
14

作者: newkid 时间: 2010-8-19 05:27
WITH t (pos,n,res) AS (
  SELECT ROWNUM,1,SUBSTR('             ',1,ROWNUM-1)||'A'||SUBSTR('             ',ROWNUM+1) FROM DUAL CONNECT BY ROWNUM<=16
  UNION ALL
  SELECT rn,n+1,SUBSTR(t.res,1,rn-1)||CHR(ASCII('A')+n)||SUBSTR(t.res,rn+1)
FROM t,(SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=16)
WHERE SUBSTR(t.res,rn,1) = ' '
      AND (t.pos NOT IN (4,8,12,16) AND rn=t.pos+1
            OR t.pos NOT IN (1,5,9,13) AND rn=t.pos-1
            OR t.pos NOT BETWEEN 13 AND 16 AND rn=t.pos+4
            OR t.pos NOT BETWEEN 1 AND 4 AND rn=t.pos-4
            )
      AND n<16
)
SELECT COUNT(*) FROM t WHERE n=16;

  COUNT(*)
----------
   552

作者: lastwinner 时间: 2010-8-19 09:58
Sixteen Numbers的意思其实就是将数字顺时针或者逆时针摆放？

作者: newkid 时间: 2010-8-19 22:00

原帖由 lastwinner 于 2010-8-19 09:58 发表
Sixteen Numbers的意思其实就是将数字顺时针或者逆时针摆放？

那是仅仅2X2的情况，4X4复杂些，任何位置都可以是起点，四个方向都可以拐弯。

我随便拿了一个答案：
KLOP
JMNA
IFEB
HGDC

因为超过两位，我用字母A-P来表示。你可以想像为一条蛇把身体盘成奇怪的形状占领整个棋盘。

作者: lastwinner 时间: 2010-8-19 22:58
标题: 回复 #50 newkid 的帖子
嗯，我当时就是按贪吃蛇去想的

作者: newkid 时间: 2010-8-26 23:16
第7题：

Neighboring Digits

We have a number. All the digits of this number are different from one another and all the digits except the first and the last have a greater value than the mean of its neighbors (ie. the digits immediately to the left and to the right).

What can this number be at maximum?

有一个数，它的每一位都不相同。除了首位和末尾，其他的每一位都比它的左右邻居（左边一位数和右边一位数）的平均值更大。这个数最大可能是多少？

递归WITH:
WITH t(str) AS (
SELECT TO_CHAR(ROWNUM) FROM DUAL CONNECT BY ROWNUM<=9
UNION ALL
SELECT str||rn
   FROM t,(SELECT ROWNUM RN FROM DUAL CONNECT BY ROWNUM<=9)
WHERE INSTR(str,rn)=0
      AND (LENGTH(str)<2
            OR rn+SUBSTR(str,-2,1) <SUBSTR(str,-1,1)*2
            )
)
SELECT MAX(TO_NUMBER(str)) FROM t;

MAX(TO_NUMBER(str))
--------------------
            479863

作者: durexlollipop 时间: 2010-8-27 09:22
689740

作者: szusunny 时间: 2010-8-27 09:26

原帖由 newkid 于 2010-8-26 23:16 发表
第7题：

Neighboring Digits

We have a number. All the digits of this number are different from one another and all the digits except the first and the last have a greater value than the mean of its neighbors (ie. the digits immediately to the left and to the right).

What can this number be at maximum?

有一个数，它的每一位都不相同。除了首位和末尾，其他的每一位都比它的左右邻居（左边一位数和右边一位数）的平均值更大。这个数最大可能是多少？

递归WITH:
WITH t(str) AS (
SELECT TO_CHAR(ROWNUM) FROM DUAL CONNECT BY ROWNUM

newkid为什么忽略0呢?
最大应该是3689740.

作者: szusunny 时间: 2010-8-27 09:29
with tmp1 as(select rownum-1 as p from dual connect by rownum <= 10),
tmp2 as (select a.p as x, b.p as y from tmp1 a, tmp1 b where a.p <> b.p)
--
select
max(to_number(replace(sys_connect_by_path(x,','),',') || y)) as res
from tmp2
connect by level <= 10
         and prior x + y < (prior y)*2
         and prior x <> y
         and prior y = x

-- Result

   RES
1 3689740

作者: lastwinner 时间: 2010-8-27 12:56
人肉：
假设有一五位数满足52楼题设条件，记这个数为abcde
那一定有 2b>a+c , 2c>b+d, 2d>c+e
于是c<2b-a, c<2d-e ,推出 2c<2b+2d-a-e ，结合 2c>b+d
可得2b+2d-a-e>b+d，推出b+d>a+e
即以中间的数为轴心，最靠近中间的两个数之和>次靠近中间的两个数之和>....>最外层两个数之和————（1）

假设有一四位数满足52楼题设条件，记这个数为abcd
则类似可得b+c>a+d,可推出最中间的两个数之和>次中间的两个数之和>....>最外层两个数之和—————（2）

上面表明了一个数要满足52楼的题设，应具备的条件（奇位数满足1，偶位数满足2）

构造方法的论述：
从0～9中任取一个数A开始构造，构造时以该数为中心，逐步往左右两边推出其他数，直至无法再推下去为止。这样的数可能能推出不止一个，最大的一个数称为由A开始构造的最大邻居数。

如果有一个满足题设的数B，其最左边或最右边的数最大，那可以尝试从最大的数的右边或者左边继续构造符合题设的数，直至构造并找出以B为基础的最大邻居数。
——————————————————————————写完发现其实以上都没啥用，不过有助于思考问题————————————————
——————————————————————————我最终无法证明9在最中央才能取得最大的数—————————————————
由前，对于abcde，可得 b>(a+c)/2>c/2, c>(b+d)/2>b/2
可能的b和c总共有16组（考虑对称性，令b>c）

with tt as (select rownum-1 r from dual connect by rownum<11)
select t1.r b, t2.r c from tt t1, tt t2 where t1.r>t2.r/2 and t2.r>t1.r/2 and t1.r>t2.r
/
B C
---------- ----------
3 2
4 3
5 3
5 4
6 4
6 5
7 4
7 5
7 6
8 5
8 6
8 7
9 5
9 6
9 7
9 8
已选择16行。

复制代码

左右两边各自衔接自己，得
with tt as (select rownum-1 r from dual connect by rownum<11),
t as (select t1.r b, t2.r c from tt t1, tt t2 where t1.r>t2.r/2 and t2.r>t1.r/2 and t1.r>t2.r)
--select ta.b, ta.c, tb.c d from t ta, t tb where ta.c=tb.b and ta.c*2>ta.b+tb.c
select ta.c a, tb.b, tb.c, tc.c d from t ta, t tb, t tc where tb.c=tc.b and tb.c*2>tb.b+tc.c
and ta.b=tb.b and tb.b*2>tb.c+ta.c and ta.c<>tc.c and ta.c<>tb.c
/

      A       B       C       D
---------- ---------- ---------- ----------
      4       6       5       3
      5       7       6       4
      6       8       7       5
      6       8       7       4
      5       8       7       4
      8       9       7       4
      6       9       7       4
      5       9       7       4
      7       9       8       6
      7       9       8       5
      6       9       8       5
      5       9       8       6

已选择12行。

再在左右两边各自衔接原始的待选数，发现右边连接不了了，左边还可以连接
with tt as (select rownum-1 r from dual connect by rownum<11),
t as (select t1.r b, t2.r c from tt t1, tt t2 where t1.r>t2.r/2 and t2.r>t1.r/2 and t1.r>t2.r),
abcd as (select ta.c a, tb.b, tb.c, tc.c d, ta.c||tb.b||tb.c||tc.c str from t ta, t tb, t tc where tb.c=tc.b and tb.c*2>tb.b+tc.c
and ta.b=tb.b and tb.b*2>tb.c+ta.c and ta.c<>tc.c and ta.c<>tb.c)
select tg.c g, abcd.a, abcd.b, abcd.c, abcd.d--, te.c e
from abcd, t tg--, t te
where abcd.a=tg.b and abcd.a*2>abcd.b+tg.c and instr(abcd.str, tg.c)=0
--and abcd.d=te.b and abcd.d*2>abcd.c+te.c and instr(abcd.str, te.c)=0
/

      G       A       B       C       D
---------- ---------- ---------- ---------- ----------
      4       7       9       8       5
      4       7       9       8       6
      5       8       9       7       4
      6       8       9       7       4

四组数是对称的右边既然连接不了了，左边自然也连接不了
考虑到最外侧两个数的特殊性，故而从这几个数开始尝试构造再大一些的邻居数
47985，左侧只能填0，右侧只能填1
47986，左侧只能填0，右侧能填3、2、1
58974，左侧只能填2、1，右侧只能填0
68974，左侧能填3、2、1，右侧只能填0

综上，最大的邻居数为3689740
————————————————————只有得出了结果，我才能说9在最中央才能得到最大的邻居数—————————————————

作者: lastwinner 时间: 2010-8-27 12:58

原帖由 szusunny 于 10-8-27 09:29 发表
with tmp1 as(select rownum-1 as p from dual connect by rownum <= 10),
tmp2 as (select a.p as x, b.p as y from tmp1 a, tmp1 b where a.p <> b.p)
--
select
max(to_number(replace(sys_connect_by_path(x,','),',') || y)) as res
from tmp2
connect by level <= 10
         and prior x + y < (prior y)*2
         and prior x <> y
         and prior y = x

作者: lastwinner 时间: 2010-8-27 14:08
with t as (select 3689740 cd from dual),
sp as (select substr(cd, rownum, 1) spn, rownum rn from t connect by rownum <=length(cd))
select spn, (case when rn between 1+1 and count(*)over() -1 then
               (case when spn>
                        (sum(spn)over(order by rn asc rows between 1 preceding  and 1 following)-spn)/2
                  then 1 else 0 end )
               else null end)  rlt
from sp
/

SP RLT
-- ---
3
6 1
8 1
9 1
7 1
4 1
0

已选择7行。

作者: 〇〇 时间: 2010-8-27 17:41
nice 花花

作者: newkid 时间: 2010-8-27 21:20

原帖由 szusunny 于 2010-8-27 09:29 发表
with tmp1 as(select rownum-1 as p from dual connect by rownum <= 10),
tmp2 as (select a.p as x, b.p as y from tmp1 a, tmp1 b where a.p <> b.p)
--
select
max(to_number(replace(sys_connect_by_path(x,','),',') || y)) as res
from tmp2
connect by level <= 10
         and prior x + y < (prior y)*2
         and prior x <> y
         and prior y = x

-- Result

         RES
1       3689740

我大意了，忘记0也可以用。
你这个帖子我要收藏，原来我也想过用CONNECT BY, 但不知道怎么访问超过一层的数据。看了你写的才茅塞顿开，原来只需先做一个自连接！

作者: newkid 时间: 2010-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, ...

作者: lastwinner 时间: 2010-9-1 22:12

原帖由 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 时间: 2010-9-1 22:17
这个题要用到数字平方的常识
比如一个数不断的平方平方再平方……，最终其尾数只可能是0、1、5、6
而0×0＝0，1×1＝1，所以题中没必要尝试去单独删0或者1

作者: dingjun123 时间: 2010-9-1 22:25
对于连续的最多删除3位，然后将删除数字替换为其平方数，变成新数字，每个数字的每一位还有其他的不一样

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

作者: lastwinner 时间: 2010-9-1 22:55
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 时间: 2010-9-1 22:57
递归暴力法：

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 时间: 2010-9-1 22:59
对newkid大哥，我只能远远地膜拜

作者: newkid 时间: 2010-9-1 23:10
递归思路很简单，而且很模式化，写多了就像套路。那些人肉方法的奇思妙想才是值得赞叹的。

加个括号输出好看一点：
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

作者: 〇〇 时间: 2010-9-2 08:15
时间有点长

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 时间: 2010-9-2 08:55
标题: 回复 #69 〇〇的帖子
bs，居然不贴sql

作者: 〇〇 时间: 2010-9-2 09:51

原帖由 lastwinner 于 2010-9-2 08:55 发表
bs，居然不贴sql

就是newkid的代码。。。
增加
WHERE substr(SUBSTR(str,p.pos,p.l),-1)<>'0'

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

已用时间: 00: 01: 58.75

作者: 〇〇 时间: 2010-9-2 11:30
我一直以为递归第一层没有重复数字字母，其实不是的

with t as
(SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',')a ,LEVEL l,''c
FROM (SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
START WITH n>0
CONNECT BY NOCYCLE LEVEL<=3)
select * from(select a from t minus select to_char(level,'fm999') a from dual connect by level<=999)where rownum<=10;

作者: 〇〇 时间: 2010-9-2 12:24
如果第一步就不允许重复数字字母

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
*/
select a,length(a),'' from (select to_char(level,'fm999') a from dual connect by level<=999)
where a<=9
or(a>=10 and a<=99 and mod(a,11)>0)
or(a>=100 and (substr(a,1,1)<>substr(a,2,1) and substr(a,1,1)<>substr(a,3,1) and substr(a,3,1)<>substr(a,2,1)))
UNION ALL
SELECT SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+l)
   ,LENGTH(SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+l))
   ,path||SUBSTR(str,1,pos-1)||'('||SUBSTR(str,pos,l)||')'||SUBSTR(str,pos+l)||','
FROM t,p
  WHERE pos+l-1<=t.len  and substr(SUBSTR(str,pos,l),-1)<>'0' and SUBSTR(str,p.pos,p.l)>'1'
      AND LENGTH(TRANSLATE('1234567890','$'||SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+l),'$'))
         = 10 - LENGTH(SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+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

已用时间:  00: 00: 50.37

作者: 〇〇 时间: 2010-9-2 12:27

原帖由 newkid 于 2010-9-1 23:10 发表
递归思路很简单，而且很模式化，写多了就像套路。

这才是设计模式,比编码更高一层

作者: 〇〇 时间: 2010-9-2 12:37
如果73楼不加and SUBSTR(str,p.pos,p.l)>'1'

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

已用时间: 00: 01: 36.87

作者: 〇〇 时间: 2010-9-2 13:26
居然有不同路径可以得到同一个值....
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
*/
select a,length(a),'' from (select to_char(level,'fm999') a from dual connect by level<=999)
where a<=9
or(a>=10 and a<=99 and mod(a,11)>0)
or(a>=100 and (substr(a,1,1)<>substr(a,2,1) and substr(a,1,1)<>substr(a,3,1) and substr(a,3,1)<>substr(a,2,1)))
UNION ALL
SELECT SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+l)
   ,LENGTH(SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+l))
   ,path||SUBSTR(str,1,pos-1)||'('||SUBSTR(str,pos,l)||')'||SUBSTR(str,pos+l)||','
FROM t,p
  WHERE pos+l-1<=t.len  and substr(SUBSTR(str,pos,l),-1)<>'0' and SUBSTR(str,p.pos,p.l)>'1'
  --and t.len-l+LENGTH(TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l)))<=10
  and
  case when SUBSTR(str,pos,l) <=3 then 0
   when SUBSTR(str,pos,l)<=31 then 1
   when SUBSTR(str,pos,l)<=316 then 2
   else 3
  end + len<=10
      AND LENGTH(TRANSLATE('1234567890','$'||SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+l),'$'))
         = 10 - LENGTH(SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+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

已用时间:  00: 00: 50.40

/*+rule*/

PATH||STR
---------------------------------------------------------------------------
----------------
38(7),38(49),38(24)01,(3)857601,9857(6)01,98(5)73601,98(2)573601,984573601

已用时间:  00: 00: 49.67

SQL> 19
19* FROM t,p
SQL> c/t,p/p,t
19* FROM p,t
SQL> /

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

已用时间:  00: 00: 59.26

作者: 〇〇 时间: 2010-9-2 13:35
如果能证明3位数的平方都不合适...
SQL> 22
22* and
SQL> a l<3 and
22* andl<3 and
SQL> 22
22* andl<3 and
SQL> c/dl/d l
22* and l<3 and
SQL> /

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

已用时间: 00: 00: 37.00

作者: lastwinner 时间: 2010-9-2 16:54

原帖由〇〇于 10-9-2 13:26 发表
居然有不同路径可以得到同一个值....

ps：三位数里有满足题设条件的

with p as (select rownum-1 rn from dual connect by rownum<=10),
three_digits as (select replace(sys_connect_by_path(rn,','),',','') num  from p where level=3 start with rn>0 connect by nocycle rn<>prior rn  and level<=3)
select num, numnum from
(select num, power(num,2) numnum from three_digits)
where length(numnum)=11-length(translate('0123456789',numnum,'$'))
/

NUM    NUMNUM
------- --------
124       15376
126       15876
128       16384
134       17956
136       18496
137       18769
142       20164
147       21609
148       21904
152       23104
153       23409
154       23716
169       28561
172       29584
174       30276
175       30625
176       30976
178       31684
179       32041
186       34596
189       35721
193       37249
195       38025
196       38416
198       39204
203       41209
209       43681
213       45369
214       45796
217       47089
219       47961
248       61504
259       67081
267       71289
268       71824
269       72361
273       74529
281       78961
286       81796
287       82369
289       83521
295       87025
302       91204
304       92416
305       93025
309       95481
324    104976
328    107584
352    123904
364    132496
367    134689
374    139876
375    140625
397    157609
403    162409
405    164025
413    170569
416    173056
425    180625
456    207936
458    209764
463    214369
487    237169
504    254016
507    257049
508    258064
509    259081
529    279841
542    293764
564    318096
567    321489
571    326041
572    327184
574    329476
584    341056
589    346921
591    349281
593    351649
597    356409
598    357604
618    381924
621    385641
625    390625
629    395641
634    401956

NUM    NUMNUM
------- --------
637    405769
639    408321
645    416025
647    418609
651    423801
695    483025
705    497025
708    501264
709    502681
713    508369
724    524176
741    549081
759    576081
763    582169
783    613089
805    648025
807    651249
829    687241
839    703921
842    708964
843    710649
845    714025
852    725904
854    729316
867    751689
871    758641
872    760384
902    813604
903    815409
905    819025
916    839056
934    872356
945    893025
968    937024

已选择119行。

作者: 〇〇 时间: 2010-9-2 20:11
SQL> select num, numnum from
  2    (select num, power(num,2) numnum from (select to_char(level+99,'fm999') num from dual connect by level<=999-100))
  3    where length(numnum||num)=10-length(translate('0123456789','$'||numnum||num,'$'));

NUM    NUMNUM
---- ----------
209    43681
259    67081
567    321489
807    651249
854    729316

已用时间:  00: 00: 00.00

作者: haiersknl 时间: 2010-9-2 20:19
7楼的答案17 不是最优的，请你重新审视你的程序。

作者: 〇〇 时间: 2010-9-2 20:36
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)
  )
,d3 as
(select rownum rn,num, numnum from
(select num, power(num,2) numnum from (select to_char(level+99,'fm999') num from dual connect by level<=999-100))
where length(numnum||num)=10-length(translate('0123456789','$'||numnum||num,'$')))
,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
*/
select a,length(a),'' from (select to_char(level,'fm999') a from dual connect by level<=999)
where a<=9
or(a>=10 and a<=99 and mod(a,11)>0)
or(a>=100 and (substr(a,1,1)<>substr(a,2,1) and substr(a,1,1)<>substr(a,3,1) and substr(a,3,1)<>substr(a,2,1)))
UNION ALL
SELECT SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+l)
   ,LENGTH(SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+l))
   ,path||SUBSTR(str,1,pos-1)||'('||SUBSTR(str,pos,l)||')'||SUBSTR(str,pos+l)||','
FROM t,p
  WHERE pos+l-1<=t.len  and substr(SUBSTR(str,pos,l),-1)<>'0' and SUBSTR(str,p.pos,p.l)>'1' and (l<3 or SUBSTR(str,pos,l)in( select num from d3))
      AND LENGTH(TRANSLATE('1234567890','$'||SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+l),'$'))
         = 10 - LENGTH(SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+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;

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

已用时间:  00: 00: 34.67

[ 本帖最后由〇〇于 2010-9-2 20:48 编辑 ]

作者: 〇〇 时间: 2010-9-2 20:50
79/81楼的算法错误，n 和n*n可以有重复数字...

作者: haiersknl 时间: 2010-9-2 21:16
版主，你的算法还是不对，你仔细看看

作者: newkid 时间: 2010-9-2 21:35

原帖由 haiersknl 于 2010-9-2 21:16 发表
版主，你的算法还是不对，你仔细看看

哪个版主？

作者: newkid 时间: 2010-9-2 21:47
如果把ROWNUM=1改为ROWNUM<=10, 可以看到其他路径，不过都是一样的，就是替换的先后顺序不同而已：
PATH||STR
-----------------------------------------------------------------------------------------------
38(7),38(49),(3)82401,98(24)01,98(5)7601,98(2)57601,98457(6)01,984573601
38(7),38(49),(3)82401,98(24)01,98(5)7601,98(2)57601,98457(6)01,9845736(0)1,984573601
38(7),38(49),38(24)01,38(5)7601,38(2)57601,(3)8457601,98457(6)01,984573601
38(7),38(49),38(24)01,38(5)7601,(3)8257601,98257(6)01,98(2)573601,984573601
38(7),38(49),38(24)01,38(5)7601,(3)8257601,98(2)57601,98457(6)01,984573601
38(7),38(49),38(24)01,(3)857601,9857(6)01,98(5)73601,98(2)573601,984573601
38(7),38(49),38(24)01,(3)857601,98(5)7601,98257(6)01,98(2)573601,984573601
38(7),38(49),38(24)01,(3)857601,98(5)7601,98(2)57601,98457(6)01,984573601
38(7),38(49),(3)82401,98(24)01,9857(6)01,98(5)73601,98(2)573601,984573601
38(7),38(49),(3)82401,98(24)01,98(5)7601,98257(6)01,98(2)573601,984573601

作者: newkid 时间: 2010-9-2 22:02

原帖由 haiersknl 于 2010-9-2 20:19 发表
7楼的答案17 不是最优的，请你重新审视你的程序。

可否贴出你的答案？（就是第二次入座后的顺序）
谢谢！

作者: lastwinner 时间: 2010-9-2 23:17

原帖由〇〇于 10-9-2 20:50 发表
79/81楼的算法错误，n 和n*n可以有重复数字...

╮(╯_╰)╭
你参照我78楼贴的不就好了么……

作者: newkid 时间: 2010-9-2 23:37

原帖由 lastwinner 于 2010-9-2 23:17 发表

╮(╯_╰)╭
你参照我78楼贴的不就好了么……

我把他的d3换成你的，确实效率高很多。
如果没有3位限制呢？也就是可以划掉任意连续位然后代之以平方。

作者: newkid 时间: 2010-9-2 23:42
去除3位限制：（相当于5位限制，因为最小的123456平方也超过10位了）
WITH p AS (
SELECT pos,l
FROM (SELECT ROWNUM pos FROM DUAL CONNECT BY ROWNUM<=10),(SELECT ROWNUM l FROM DUAL CONNECT BY ROWNUM<=5)
  WHERE pos+l<=11
  )
,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 substr(SUBSTR(str,pos,l),-1)<>'0' and SUBSTR(str,p.pos,p.l)>'1'
      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
------------------------------------------------------
31(5),31(2)5,314(5),(3142)5,98721(6)45,987213645

Elapsed: 00:00:37.38

作者: 〇〇 时间: 2010-9-3 09:06

原帖由 lastwinner 于 2010-9-2 16:54 发表

赞

ps：三位数里有满足题设条件的

with p as (select rownum-1 rn from dual connect by rownum<=10),
three_digits as (select replace(sys_connect_by_path(rn,','),',','') num from p where level=3 start with rn>0 connect by nocycle rn<>prior rn and level<=3)
select num, numnum from
(select num, power(num,2) numnum from three_digits)
where length(numnum)=11-length(translate('0123456789',numnum,'$'))
/

硬是看不懂,你把平方数的第一位换成$为什么

作者: 〇〇 时间: 2010-9-3 09:30
xeon

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)
  )
,d3 as
(select rownum rn,num, numnum from
(select num, power(num,2) numnum from (select level+99 num from dual connect by level<=999-100))
where  (substr(num,1,1)<>substr(num,2,1) and substr(num,1,1)<>substr(num,3,1) and substr(num,3,1)<>substr(num,2,1))and
length(numnum)=10-length(translate('0123456789','$'||numnum,'$')))
,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
*/
select a,length(a),'' from (select to_char(level,'fm999') a from dual connect by level<=999)
where a<=9
or(a>=10 and a<=99 and mod(a,11)>0)
or(a>=100 and (substr(a,1,1)<>substr(a,2,1) and substr(a,1,1)<>substr(a,3,1) and substr(a,3,1)<>substr(a,2,1)))
UNION ALL
SELECT SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+l)
   ,LENGTH(SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+l))
   ,path||SUBSTR(str,1,pos-1)||'('||SUBSTR(str,pos,l)||')'||SUBSTR(str,pos+l)||','
FROM t,p
  WHERE pos+l-1<=t.len  and substr(SUBSTR(str,pos,l),-1)<>'0' and SUBSTR(str,p.pos,p.l)>'1' and (l<3 or SUBSTR(str,pos,l)in( select num from d3))
      AND LENGTH(TRANSLATE('1234567890','$'||SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+l),'$'))
         = 10 - LENGTH(SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+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

已用时间:  00: 00: 35.00

作者: lastwinner 时间: 2010-9-3 10:15

原帖由〇〇于 10-9-3 09:06 发表

硬是看不懂,你把平方数的第一位换成$为什么

这不跟之前你们用来测试有无重复数字的代码差不多么？

要不你说应该替换为什么？

作者: szusunny 时间: 2010-9-3 10:16
标题: 回复 #91 〇〇的帖子
38(7),38(49),(3)82401,98(24)01,98(5)7601,98(2)57601,98457(6)01,984573601
这个答案为什么不继续向前推呢?
38(7),38(49),(3)82401,98(24)01,98(5)7601,98(2)57601,98457(6)01,984(5)73601,9842573601

作者: lastwinner 时间: 2010-9-3 10:46

原帖由 szusunny 于 10-9-3 10:16 发表
38(7),38(49),(3)82401,98(24)01,98(5)7601,98(2)57601,98457(6)01,984573601
这个答案为什么不继续向前推呢?
38(7),38(49),(3)82401,98(24)01,98(5)7601,98(2)57601,98457(6)01,984(5)73601,9842573601

说明他们的算法还是有遗漏的地方

作者: szusunny 时间: 2010-9-3 10:46
不继续向前推的原因是判断字符不重复方法length(num)=10-length(translate('0123456789','$'||num,'$'))的漏洞.
应该加上nvl(...)解决NULL问题.
nvl(length(num),0)=10-nvl(length(translate('0123456789','$'||num,'$')),0)

作者: 〇〇 时间: 2010-9-3 11:31
上面的代码在E5420
如果E7540
40秒
595
55秒

作者: 〇〇 时间: 2010-9-3 12:23

原帖由 szusunny 于 2010-9-3 10:46 发表
不继续向前推的原因是判断字符不重复方法length(num)=10-length(translate('0123456789','$'||num,'$'))的漏洞.
应该加上nvl(...)解决NULL问题.
nvl(length(num),0)=10-nvl(length(translate('0123456789','$'||num,'$')),0)

NICEＪＯＢ

作者: haiersknl 时间: 2010-9-3 15:11
标题: 回复 #86 newkid 的帖子
1 5 9 13 17 2 6 10 14 18 3 7 11 15 19 4 8 12 16

请你继续算第8题，上面有人算出984573601，有人指出应该继续运行得出9842573601。
那么现在的问题就出来了，程序上的漏洞会不会，让我们怀疑这个结果：9842573601 很可能不是最优的。

你们之前算的552是对的。552你们编程加调试一共用了多久？我有个简单方法笔算可搞定。

作者: newkid 时间: 2010-9-3 21:59

原帖由 haiersknl 于 2010-9-3 15:11 发表
1 5 9 13 17 2 6 10 14 18 3 7 11 15 19 4 8 12 16

请你继续算第8题，上面有人算出984573601，有人指出应该继续运行得出9842573601。
那么现在的问题就出来了，程序上的漏洞会不会，让我们怀疑这个结果：9842573601 很可能不是最优的。

你们之前算的552是对的。552你们编程加调试一共用了多久？我有个简单方法笔算可搞定。

你的答案是19?题目要找出最小的人数，我的答案是17:
1,5,9,13,17,4,8,12,16,3,7,11,15,2,6,10,14
1,14,10,6,2,15,11,7,3,16,12,8,4,17,13,9,5

这两个答案是顺序相反的排列。如果你觉得17有错，那么其中哪一个人的排列不符合题目要求？

第8题原来的TRANSLATE有漏洞，改过来就好了。如果你觉得还有错只需再举个反例，或者指出程序中的错误。

552指的是47楼那题？我花不到10分钟就写了那个递归SQL, 如果你有好的人肉方法请贴出来共享。

作者: newkid 时间: 2010-9-3 22:24
第8题，先把所有不重复的平方数找出来：

CREATE TABLE nums AS
WITH
n AS (
  SELECT TO_NUMBER(REPLACE(SYS_CONNECT_BY_PATH(rn,','),',','')) num
FROM (SELECT ROWNUM-1 rn FROM DUAL CONNECT BY ROWNUM<=10)
  START WITH rn>0
  CONNECT BY NOCYCLE rn<>PRIOR rn AND LEVEL<=5
  )
,nums AS (
SELECT TO_CHAR(num) num, TO_CHAR(numnum) numnum,LENGTH(numnum) l2
  FROM (SELECT num, num*num numnum FROM n)
WHERE LENGTH(numnum)=11-LENGTH(TRANSLATE('$0123456789','$'||numnum,'$'))
)
SELECT * FROM nums;

----------------------------------------
没有3位限制的写法：
WITH p AS (
SELECT pos,l
FROM (SELECT ROWNUM pos FROM DUAL CONNECT BY ROWNUM<=10),(SELECT ROWNUM l FROM DUAL CONNECT BY ROWNUM<=5)
  WHERE pos+l<=11
  )
,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 REPLACE(str,num,numnum)
   ,t.len+nums.l2-p.l
   ,path||SUBSTR(str,1,p.pos-1)||'('||num||')'||SUBSTR(str,p.pos+p.l)||','
FROM nums,t,p
  WHERE p.pos+p.l-1<=t.len
      and substr(SUBSTR(str,pos,l),-1)<>'0' and SUBSTR(str,p.pos,p.l)>'1'
      AND LENGTH(TRANSLATE('$1234567890','$'||REPLACE(str,num,numnum),'$'))
         = 11 - (t.len+nums.l2-p.l)
      AND SUBSTR(str,p.pos,p.l) = nums.num
)
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
-------------------------------------------------------------------------
19(8),(1964),3857(2)96,3857(49)6,(3)85724016,98572401(6),9857240136

Elapsed: 00:00:20.40

有3位限制的写法：
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)
  WHERE pos+l<=11
  )
,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 REPLACE(str,num,numnum)
   ,t.len+nums.l2-p.l
   ,path||SUBSTR(str,1,p.pos-1)||'('||num||')'||SUBSTR(str,p.pos+p.l)||','
FROM nums,t,p
  WHERE p.pos+p.l-1<=t.len
      and substr(SUBSTR(str,pos,l),-1)<>'0' and SUBSTR(str,p.pos,p.l)>'1'
      AND LENGTH(TRANSLATE('$1234567890','$'||REPLACE(str,num,numnum),'$'))
         = 11 - (t.len+nums.l2-p.l)
      AND SUBSTR(str,p.pos,p.l) = nums.num
)
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,984(5)73601,9842573601

Elapsed: 00:00:17.19

奇怪的是如果我把表nums写成WITH, 计划就改变了，等了好几分钟也出不来。有一步HASH JOIN变成了NESTED LOOP, 不知道有什么HINTS可以让它走HASH JOIN.

欢迎光临 ITPUB论坛－专业的IT技术社区 (http://www.itpub.net/)