PUZZLEUP 2015

〇〇

lugionline 发表于 2015-10-4 08:15
我的理解是这5个数不必要一定出现，111.....111这种也算

SQL如果硬拼数字统计的话估计机器要响上半天了

如果没有最后1个条件,相邻都相等,就都是1个数字了

newkid

lugionline 发表于 2015-10-4 08:15
我的理解是这5个数不必要一定出现，111.....111这种也算

SQL如果硬拼数字统计的话估计机器要响上半天了

是不是这个总数：
  COUNT(*)
----------
  64570081

Elapsed: 00:00:25.35

如果要求5个数全部出现还更费周折，要多算几秒：
  COUNT(*)
----------
  21310248

Elapsed: 00:00:29.19

solomon_007

#10

SQL> set timing on;
SQL>
SQL>
SQL> with t as (select to_char(level) n from dual connect by level <=5),
  2       s (lvl,lastchar,str) as ( select 1 lvl,
  3                                        n lastchar,
  4                                        n str
  5                                   from t
  6                                  union all
  7                                 select s.lvl + 1,
  8                                        t.n,
  9                                        s.str||case when substr(s.str,-1,1) =1 then t.n
10                                                    else case when t.n=1 then '1'
11                                                              else s.lastchar
12                                                         end
13                                               end
14                                   from s,t
15                                  where s.lvl < 16
16                                    and t.n = case when substr(s.str,-1,1) =1 then t.n
17                                                        else case when t.n=1 then '1'
18                                                                  else s.lastchar
19                                                             end
20                                              end
21                                 )
22  select count(*) from s where lvl = 16
23  /
  COUNT(*)
----------
  64570081
Executed in 3056.149 seconds

lugionline

newkid 发表于 2015-10-6 02:16
是不是这个总数：
  COUNT(*)
----------

不得不说你的SQL是很快，我是好学生，我用通项公式

In[3]:= (3^(n + 1) - (-1)^n)/2 /. n -> 16

Out[3]= 64570081

lugionline

要求5个数字全部出现就比较麻烦了，但是也能算出通项公式

不能贴图就只能贴难看的公式了

In[238]:= FullSimplify[(1 + 1/2 (-(-1)^n + 3^(n + 1)) +
    3 ((1 - Sqrt[2])^(n + 1) + (1 + Sqrt[2])^(n + 1)) -
    2 ((1 - Sqrt[3])^(n + 1) + (1 + Sqrt[3])^(n + 1)) - 2^(n + 2)) /.
  n -> 16]

Out[238]= 21310248

〇〇

solomon_007 发表于 2015-10-6 09:35
#10

SQL> set timing on;

不错,不到1小时插入了6千万行

newkid

solomon_007 发表于 2015-10-6 09:35
#10

SQL> set timing on;

好吧给你发个章。你还真有耐心，我也写了递归版本但是等不了那么九。

改用二分法：
WITH d2 AS (
SELECT n1||n2 n
  FROM (SELECT LEVEL n1 FROM DUAL CONNECT BY LEVEL<=5)
      ,(SELECT LEVEL n2 FROM DUAL CONNECT BY LEVEL<=5)
WHERE n1=n2 OR n1=1 OR n2=1
)
,d4 AS (
SELECT a.n||b.n n
  FROM d2 a,d2 b
WHERE SUBSTR(a.n,2)=SUBSTR(b.n,1,1)
       OR SUBSTR(a.n,2)=1
       OR SUBSTR(b.n,1,1)=1
)
,d8 AS (
SELECT a.n||b.n n
  FROM d4 a,d4 b
WHERE SUBSTR(a.n,4)=SUBSTR(b.n,1,1)
       OR SUBSTR(a.n,4)=1
       OR SUBSTR(b.n,1,1)=1
)
,d16 AS (
SELECT a.n||b.n n
  FROM d8 a,d8 b
WHERE SUBSTR(a.n,8)=SUBSTR(b.n,1,1)
       OR SUBSTR(a.n,8)=1
       OR SUBSTR(b.n,1,1)=1
)
SELECT COUNT(*) FROM d16;

  COUNT(*)
----------
  64570081

Elapsed: 00:00:25.35

如果要求所有的数全部包含：
WITH d2 AS (
SELECT n1||n2 n
  FROM (SELECT LEVEL n1 FROM DUAL CONNECT BY LEVEL<=5)
      ,(SELECT LEVEL n2 FROM DUAL CONNECT BY LEVEL<=5)
WHERE n1=n2 OR n1=1 OR n2=1
)
,d4 AS (
SELECT a.n||b.n n
  FROM d2 a,d2 b
WHERE SUBSTR(a.n,2)=SUBSTR(b.n,1,1)
       OR SUBSTR(a.n,2)='1'
       OR SUBSTR(b.n,1,1)='1'
)
,d8 AS (
SELECT n
      ,INSTR(n,'1') p1
      ,INSTR(n,'2') p2
      ,INSTR(n,'3') p3
      ,INSTR(n,'4') p4
      ,INSTR(n,'5') p5
  from (
SELECT CAST(a.n||b.n AS VARCHAR2(8)) n
  FROM d4 a,d4 b
WHERE SUBSTR(a.n,4)=SUBSTR(b.n,1,1)
       OR SUBSTR(a.n,4)='1'
       OR SUBSTR(b.n,1,1)='1'
       )
)
,d16 AS (
SELECT a.n||b.n n
  FROM d8 a,d8 b
WHERE (SUBSTR(a.n,8)=SUBSTR(b.n,1,1)
       OR SUBSTR(a.n,8)='1'
       OR SUBSTR(b.n,1,1)='1'
       )
       AND a.p1+b.p1>0
       AND a.p2+b.p2>0
       AND a.p3+b.p3>0
       AND a.p4+b.p4>0
       AND a.p5+b.p5>0
)
SELECT COUNT(*) FROM d16;

  COUNT(*)
----------
  21310248

Elapsed: 00:00:29.19

newkid

lugionline 发表于 2015-10-6 11:07
不得不说你的SQL是很快，我是好学生，我用通项公式

In[3]:= (3^(n + 1) - (-1)^n)/2 /. n -> 16

这个应该不难推，我怎么没想到？

solomon_007

newkid 发表于 2015-10-6 21:38
好吧给你发个章。你还真有耐心，我也写了递归版本但是等不了那么九。

改用二分法：

随便给一个吧     我只会简单的做法, 我怎么就没有想到像你那样先构造所有的两位的组合呢?

solomon_007

〇〇 发表于 2015-10-6 21:25
不错,不到1小时插入了6千万行

第一次运行TEMP表空间不足, 死掉了; 后来加了2个临时文件. 运算的过程中,临时表空间扩展到了好像十多G吧

另外,我的笔记本性能还可以吧...