Euler Project 挨个做- 之二 (Q51-Q78)

tree_new_bee

原帖由 〇〇 于 2011-1-6 19:36 发表
9i的表现真是奇怪：
97#
select min(n),to_char(min(cb)) cb  from tdigis where digis in (select digis from tdigis group by digis having count(*)=5)
                                                                                 *
ERROR 位于第 9 行:
ORA-00600: 内部错误代码，参数: [kkqwrm_noref: COLFDNF set], [], [], [], [], [], [], []

从做Euler开始， 碰到的内部错误越来越多了。
也许oracle没想到我们拿数据库干这个用吧。

tree_new_bee

64题做的很烦躁。 有点类似的65看见就发晕。
先跳过， 留着心情好的时候再回头做。

Q66 Investigate the Diophantine equation x2 − Dy2 = 1.

Consider quadratic Diophantine equations of the form:

x^(2) – Dy^(2) = 1

For example, when D=13, the minimal solution in x is 649^(2) – 13×180^(2) = 1.

It can be assumed that there are no solutions in positive integers when D is square.

By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we obtain the following:

3^(2) – 2×2^(2) = 1
2^(2) – 3×1^(2) = 1
9^(2) – 5×4^(2) = 1
5^(2) – 6×2^(2) = 1
8^(2) – 7×3^(2) = 1

Hence, by considering minimal solutions in x for D ≤ 7, the largest x is obtained when D=5.

Find the value of D ≤ 1000 in minimal solutions of x for which the largest value of x is obtained.

tree_new_bee

66看着不难。
很容易就能用递归写出来：

with tn as(select level n from dual where trunc(sqrt(level),10)<> trunc(sqrt(level))  connect by level<=50)
, t (x, D) as (
select greatest(2,floor(sqrt(n))), n from tn
union all
select
x+1,
D
from t where trunc(sqrt((x*x-1)/D))<> sqrt((x*x-1)/D)
)
select d,maxx from (select d, max(x) max, max(max(x))over ()  maxx  from t group by d) where max=maxx

         D       MAXX
---------- ----------
        46      24335

Executed in 0.813 seconds

不过，当碰到61的时候， 卡住了。
不知道X(61) 是多大的数， 我测到1000000尚未有结果。
要应付这么大的递归层数， 递归with是无能为力了。

〇〇

晕倒，66居然是64 65的延续

e = [2;1,2,1,1,4,1,1,6,1,1,8,1, … ]
求当 D 为 [1,1000] 内的哪个非完全平方数时，
方程： x
2
– Dy
2
= 1 的最小正整数解 (x 最小 )
中的 x 值最大。
该方程为佩尔方程。
需要求解出 D 的平方根的连分数展开 ， 如果循
环节长度 ( 记作 Len) 为偶数 ， 计算第 Len 个渐
渐分数 ； 若为奇数 ， 计算第 2Len 个渐近分数 。
分子就是 x 的值。
6

tree_new_bee

原帖由 tree_new_bee 于 2011-1-6 20:43 发表
要应付这么大的递归层数， 递归with是无能为力了。

、

试到10000000万还是无解， 感到不对劲了， 这题不是常规方法能做出来的。

Google一把， 发现上个题想逃避的连分数依然要用到。

求出SQRT(D)的连分数[a0: (a1, a2, a3 ... an)...],其中an=2*a1

然后再计算

根据连分数循环节位数n的奇偶性分两种情况

若n为偶数,则 x= pn-1 , y= qn-1 ; n为奇数时x= p2n-1 , y= q2n-1
p0= a0, p1= a0* a1+1 , pn= an*pn-1+pn-2
q0=1,   q1=a1,        qn=an*qn-1+qn-2

对于61：SQRT(D) = [7: (1,4,3,1,2,2,1,3,4,14)] , n=11
套上面的公式： x=p2n-1 = 1766319049  y = 226153980


幸亏google了一把， 要不这么大的数， 靠我去挨个加1， 估计加到我白头发也出不来。
这还只是个61， 后面的大数还多着呢。

tree_new_bee

原帖由 〇〇 于 2011-1-6 21:32 发表
晕倒，66居然是64 65的延续

e = [2;1,2,1,1,4,1,1,6,1,1,8,1, … ]
求当 D 为 [1,1000] 内的哪个非完全平方数时，
方程： x
2
– Dy
2
= 1 的最小正整数解 (x 最小 )
中的 x 值最大。
该方程为佩尔方程。
需要求解出 D 的平方根的连分数展开 ， 如果循
环节长度 ( 记作 Len) 为偶数 ， 计算第 Len 个渐
渐分数 ； 若为奇数 ， 计算第 2Len 个渐近分数 。
分子就是 x 的值。
6

哈，你也搜到了？

这几道成了纯数学题了。郁闷。

明白前面的64，为什么让求循环长度为奇数的个数了，  奇数个数的在这道题里，对应的X要大的多。

[ 本帖最后由 tree_new_bee 于 2011-1-6 21:43 编辑 ]

tree_new_bee

郁闷了。 今天罢工不做了， 早点休息。

newkid

原帖由 tree_new_bee 于 2011-1-6 19:24 发表
实际上上面的算法与111#google到的算法似乎是一样的。

with t0 as (select 23 num from dual)
,t(r, n, a,q,p, path) as (
select 1, num, trunc(sqrt(num)),1, trunc(sqrt(num)), cast(',' as varchar2(4000)) from t0 where trunc(sqrt(num))sqrt(num)
union all
select r+1,n,
trunc(q*(sqrt(n)+p)/(n-p*p)), --a'
(n-p*p)/q,  --q'
(n-p*p)/q * trunc(q*(sqrt(n)+p)/(n-p*p)) - p,   -- q'*a'-p
path || p||'/'||q||','
from t where instr(path,','||p||'/'||q ||',')=0
)
select r,n,a,q,p, path, length(translate(path, ','||path, ','))-1 len from t

         R          N          A          Q          P PATH                                                                                    LEN
---------- ---------- ---------- ---------- ---------- -------------------------------------------------------------------------------- ----------
         1         23          4          1          4 ,                                                                                         0
         2         23          1          7          3 ,4/1,                                                                                     1
         3         23          3          2          3 ,4/1,3/7,                                                                                 2
         4         23          1          7          4 ,4/1,3/7,3/2,                                                                             3
         5         23          8          1          4 ,4/1,3/7,3/2,4/7,                                                                         4

昨天我还给根号加上系数，其实B恒为1, 我的写法简化后就和你一样了：

WITH n AS (SELECT LEVEL N FROM DUAL WHERE MOD(SQRT(LEVEL),1)>0 CONNECT BY LEVEL<=10000)
,t(A,C,D,STR,N) AS (
SELECT TRUNC(SQRT(N)),TRUNC(SQRT(N)),1,CAST('~' AS VARCHAR2(4000)),N FROM n
UNION ALL
SELECT TRUNC((D*SQRT(N)+D*C)/(N - C*C))
      ,(TRUNC((D*SQRT(N)+D*C)/(N - C*C))*(N - C*C) - D*C )/D
      ,(N - C*C)/D
      ,STR||C||','||D||'~'
      ,N
  FROM t
WHERE INSTR(STR,'~'||C||','||D||'~')=0   
) CYCLE C,D,N SET cycle_flag TO 'Y' DEFAULT 'N'
SELECT COUNT(*)
  FROM (SELECT N,SUBSTR(STR, INSTR(STR,'~'||C||','||D||'~')+1) AS STR
          FROM T
         WHERE INSTR(STR,'~'||C||','||D||'~')>0
       )
WHERE MOD(LENGTH(STR)-LENGTH(REPLACE(STR,'~')),2)=1
;

  COUNT(*)
----------
      1322

Elapsed: 00:00:10.95

tree_new_bee

66题， 用119#的方法来做：

--with t0 as (select 61 num from dual)
with t0 as (select rownum num from dual connect by rownum<=1000)
,t(r, n, a,q,p, x, xx, y ,yy, path, len) as (
select 0 r, num n, trunc(sqrt(num)) a,1 q, trunc(sqrt(num)) p,
trunc(sqrt(num)) x, 1 xx, 1 y,0 yy, cast(',' as varchar2(4000)), 0 from t0 where trunc(sqrt(num))<>sqrt(num)
union all
select r+1,n,
trunc(q*(sqrt(n)+p)/(n-p*p)), --a'
(n-p*p)/q,  --q'
(n-p*p)/q * trunc(q*(sqrt(n)+p)/(n-p*p)) - p,   -- q'*a'-p
trunc(q*(sqrt(n)+p)/(n-p*p))*x + xx,  -- xn = an*xn-1 + xn-2
x,
trunc(q*(sqrt(n)+p)/(n-p*p))*y + yy,   -- yn = an*yn-1 + yn-2
y,
case when  instr(path,','||p||'/'||q ||',')=0 then path || p||'/'||q||',' else path end,
case when  instr(path,','||p||'/'||q ||',')=0 then len+1 else len end
from t where r=0 or r<len*2
)
, tt as (select r,n,a,q,p,x,y, path, max(len) over (partition by n) maxlen from t)
, ttt as(select n,x,y from tt where (mod(maxlen,2)=1 and r=2*maxlen-1 ) or (mod(maxlen,2)=0 and r=maxlen-1))
select * from ttt where x = (select max(x) from ttt)


         N          X          Y
---------- ---------- ----------
       661 1.6422E+37 6.3873E+35

已用时间:  00: 00: 01.17


1E37, 这要是还用一个一个加的办法， 就不是白头发的问题了， 估计要留着让子子孙孙一直算下去了。

tree_new_bee

Q67  Using an efficient algorithm find the maximal sum in the triangle?

Q18的加长版本。
因为Q18的解法效率已经足够， 所以直接拿来套用即可。 只是初始表用外部表来代替。

create  table euler_triangle(
  line varchar2 (400)
    )
  ORGANIZATION EXTERNAL (
         TYPE ORACLE_LOADER
         DEFAULT DIRECTORY euler_dir
         ACCESS PARAMETERS
         (
           records delimited by '\n'
           badfile euler_dir:'triangle%a_%p.bad'
           logfile euler_dir:'triangle%a_%p.log'
           fields terminated by '\n'
                   (line char(400))
         )
         LOCATION ('euler_triangle.txt')
  );


with tstr as (select rownum r, line str from euler_triangle)
,t1 as (select rownum c  from dual connect by level<=100)
,t2 as (select r, c, to_number(substr(str, c*3-2, 2)) num from tstr, t1 where substr(str, c*3-2, 2) is not null)
,t3 as (SELECT r,c,num
  FROM t2
MODEL
    DIMENSION BY (r,c)
    MEASURES (num)
    RULES update
     (
     update num[any, any] order by r desc, c = case when cv(r)<100
                     then  num[cv(r),cv(c)] +  greatest(num[cv()+1,cv()], num[cv(r)+1, cv(c)+1])
                     else  num[cv(r),cv(c)] end
) order by r , c)
select * from t3 where r=1 and c=1

         R          C        NUM
---------- ---------- ----------
         1          1       7273

Executed in 0.203 seconds