Puzzleup 2010 比赛快开始了，大家用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

我不做了，中午还要去还款...

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
四平方和定理说明所有正整数均可表示为最多四个平方数的和。但不是"不同"的平方数的和

这个我看了，没毛用

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

回复 #24 lastwinner 的帖子

浏览过的版块