Euler Project 挨个做 - 之一(Q1-50)

tree_new_bee

Q42  How many triangle words does the list of common English words contain?

The n^(th) term of the sequence of triangle numbers is given by, t_(n) = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t_(10). If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

tree_new_bee

这个题与Q22基本上差不多。
用同样的方式建立外部表。

判断一个数是否是三角数， 只要把n(n+1)/2反过来就是了：
设x = n(n+1)/2
则：
n^2 + n  = 2x
(n+1/2)^2 = 2x + 1/4
n = sqrt(2x+1/4) - 1/2

也就是说只要sqrt(2x+1/4) - 1/2为整数， 则x就是一个三角数。


  create  table euler_words(
  fname varchar2 (20)
  )
  ORGANIZATION EXTERNAL (
         TYPE ORACLE_LOADER
         DEFAULT DIRECTORY euler_dir
         ACCESS PARAMETERS
         (
           records delimited by ','
           badfile euler_dir:'words%a_%p.bad'
           logfile euler_dir:'words%a_%p.log'
           fields ENCLOSED BY '"'
           (fname)
         )
         LOCATION ('euler_words.tx  t')
  );


with t0 as (select rownum n from dual connect by rownum<=20)
,t1 as (select fname, sum(ASCII(substr(fname,n,1))-64) value
from euler_words,t0 where n<=length(fname)  group by fname)
select count(*) from t1 where sqrt(2*value+0.25) - 0.5 = round(sqrt(2*value+0.25) - 0.5)

  COUNT(*)
----------
       162

Executed in 0.187 seconds

tree_new_bee

原帖由 〇〇 于 2010-12-26 21:47 发表
捣鼓半天，消除了谓词推进的查询重写
with t as (select level l from dual connect by level<=7)
,tb as
(
select /*+ MATERIALIZE */t1.l||t2.l||t3.l||t4.l||t5.l||t6.l||t7.l s

一直没找到MATERIALIZE hint的相关说明。 看字面含义似乎与result_cache差不多？

〇〇

问题43:Find the sum of all pandigital numbers with an unusual sub-string divisibility property.
题目简介:数字1406357289具有以下性质：
　　1.它是0~9的一个排列
　　2.记di为它的第i为数字(从左至右,i从1开始),则:
　　　　　* d2d3d4=406 is divisible by 2
　　　　　* d3d4d5=063 is divisible by 3
　　　　　* d4d5d6=635 is divisible by 5
　　　　　* d5d6d7=357 is divisible by 7
　　　　　* d6d7d8=572 is divisible by 11
　　　　　* d7d8d9=728 is divisible by 13
　　　　　* d8d9d10=289 is divisible by 17
　　求所有具有上述性质的数字之和。
答　　案:16695334890

〇〇

43就是穷尽法
with t as (select level l from dual connect by level<=9),
t2 as(select level*2 l from dual connect by level<=998/2),
t5 as(select l from(select level *7 l from dual connect by level<=999/7) where substr(l,2,1) ='5'),
t8 as(select level *17 l from dual connect by level<=999/17)
select t.l||t2.l||t5.l||t8.l, sum(t.l||t2.l||t5.l||t8.l) over()s
from t,t2,t5,t8
where mod(substr(t2.l,2,2)||substr(t5.l,1,1),3)=0
and mod(substr(t5.l,2,2)||substr(t8.l,1,1),11)=0
and mod(substr(t5.l,3,1)||substr(t8.l,1,2),13)=0
and translate('1234567890','#'||t.l||t2.l||t5.l||t8.l,'#')is null;

已选择6行。

已用时间:  00: 00: 04.32

有个漏洞 t5缺少  or substr(l,2,1) ='0'

已选择6行。

已用时间:  00: 00: 06.83

[ 本帖最后由 〇〇 于 2010-12-27 16:09 编辑 ]

〇〇

with t as (select level l from dual connect by level<=9),
t2 as(select l from(select level*2 l from dual connect by level<=998/2)
where substr(l,1,1)<>substr(l,2,1) and substr(l,1,1)<>substr(l,3,1) and substr(l,2,1)<>substr(l,3,1)),
t5 as(select l from(select level *7 l from dual connect by level<=999/7)
where (substr(l,2,1) ='5' or substr(l,2,1) ='0') and (substr(l,1,1)<>substr(l,2,1) and substr(l,1,1)<>substr(l,3,1) and substr(l,2,1)<>substr(l,3,1))),
t8 as(select l from(select level *17 l from dual connect by level<=999/17)
where substr(l,1,1)<>substr(l,2,1) and substr(l,1,1)<>substr(l,3,1) and substr(l,2,1)<>substr(l,3,1))
select t.l||t2.l||t5.l||t8.l, sum(t.l||t2.l||t5.l||t8.l) over()s
from t,t2,t5,t8
where mod(substr(t2.l,2,2)||substr(t5.l,1,1),3)=0
and mod(substr(t5.l,2,2)||substr(t8.l,1,1),11)=0
and mod(substr(t5.l,3,1)||substr(t8.l,1,2),13)=0
and translate('1234567890','#'||t.l||t2.l||t5.l||t8.l,'#')is null;

3.6秒

tree_new_bee

Q43, 本以为随便写出一个SQL，性能会很差， 没想到结果非常快。

注意，有几个条件是可以简化的：
2,5的倍数只要判断末尾即可。
3的倍数判断几位相加是否3的倍数
3位的11的倍数， 首尾相加减去中间的数是11的倍数。

with td as (select rownum-1 d from dual connect by rownum<=10)
select sum(td1.d||td2.d||td3.d||td4.d||td5.d||td6.d||td7.d||td8.d||td9.d||td10.d)
from td td1, td td2, td td3, td td4, td td5, td td6, td td7, td td8, td td9, td td10
where td4.d in (0,2,4,6,8)
and mod(td3.d+td4.d+td5.d, 3) = 0
and  td6.d in (0,5)
and mod(td5.d||td6.d||td7.d, 7) = 0
and td6.d+td8.d-td7.d in (0,11)
and mod(td7.d||td8.d||td9.d, 13) = 0
and mod(td8.d||td9.d||td10.d, 17) = 0
and translate('0123456789', '$'||td1.d||td2.d||td3.d||td4.d||td5.d||td6.d||td7.d||td8.d||td9.d||td10.d, '$') is null

SUM(TD1.D||TD2.D||TD3.D||TD4.D
------------------------------
                   16695334890

Executed in 0.469 seconds

〇〇

226,227在9i上都是0.2s，看来又是优化器惹的祸

tree_new_bee

Q44 Find the smallest pair of pentagonal numbers whose sum and difference is pentagonal.

Pentagonal numbers are generated by the formula, P_(n)=n(3n−1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P_(4) + P_(7) = 22 + 70 = 92 = P_(8). However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, P_(j) and P_(k), for which their sum and difference is pentagonal and D = |P_(k) − P_(j)| is minimised; what is the value of D?


这是一道有挑战性的题。

[ 本帖最后由 tree_new_bee 于 2010-12-28 14:40 编辑 ]

tree_new_bee

x=n(3n−1)/2
则n = (sqrt(24x+1) + 1)/6
所以判断一个数是否pentagonal numbers(五角数)， 就是判断(sqrt(24x+1) + 1)/6是否为自然数。

没有边界， 所以用sql来做依然需要逐步试探。

每次增加1000，到3000时得到了结果：

with tpen as (select rownum n, rownum*(rownum*3-1)/2 pen from dual connect by rownum<=3000)
select t1.n n1, t1.pen pen1, t2.n n2, t2.pen pen2, t2.pen-t1.pen d  from tpen t1, tpen t2
where floor((sqrt(24*(t1.pen+t2.pen)+1)+1)/6) =   (sqrt(24*(t1.pen+t2.pen)+1)+1)/6
and floor((sqrt(24*(t2.pen-t1.pen)+1)+1)/6) =   (sqrt(24*(t2.pen-t1.pen)+1)+1)/6
and t1.pen < t2.pen

        N1       PEN1         N2       PEN2          D
---------- ---------- ---------- ---------- ----------
      1020    1560090       2167    7042750    5482660

Executed in 18.188 seconds

当n到10000时， 时间需要200多秒，依然只有这么一个结果。
但是，我无法确定这是否能确认得到的D,是否就是最小的D.
也许会有很大的n1,n2, 也满足这个条件， 并且p(n2)-p(n1)小于上面得到的5482660

要想真的确认， 也许需要验证到某个数n, 它和与它紧紧相邻的数的差都大于上面的D, 即p(n)-p(n-1)大于5482660才能确认。

而p(n)-p(n-1) = n(3n-1)/2 - (n-1)(3n-4)/2 = 3(n-1) + 1
这样， 验证工作要达到n = 1827555
这个数量， 计算量吓人！

[ 本帖最后由 tree_new_bee 于 2010-12-27 20:58 编辑 ]