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

newkid

WOW! 有点绚烂烟花的特效！NB哥拜年都这么NB!

tree_new_bee

Q57 Investigate the expansion of the continued fraction for the square root of two.

It is possible to show that the square root of two can be expressed as an infinite continued fraction.

√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

By expanding this for the first four iterations, we get:

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

tree_new_bee

本以为这个很容易， 没想到就这么往上加，加起来很快，不久就溢出了。
之前的大树package中一直没有大数和， 现在加上。(其实实现起来比乘法容易多了)

  function bigplus(d1 varchar2, d2 varchar2) return varchar2 is
    Result varchar2(30000) := '';
    type t_numlist is table of number index by PLS_INTEGER;
    numlist t_numlist;
    i       number;
    lastm   number;
    tmp     number;
  begin
    if d1<1e36 and d2<1e36 then
       return d1+d2;
    end if;
  
    for i in 1 .. greatest(length(d1) ,length(d2)) loop
      numlist(i) := nvl(substr(d1, -i, 1),0) + nvl(substr(d2, -i, 1),0);
    end loop;
  
    lastm := 0;
    for i in 1 .. greatest(length(d1) ,length(d2)) loop
      tmp := mod(numlist(i) + lastm, 10);
      lastm := trunc((numlist(i) + lastm) / 10);
      numlist(i) := tmp;
      result := numlist(i) || result;
    end loop;
    if lastm>0 then result:=lastm||result; end if;
    return(nvl(ltrim(Result, '0'),0));
  end;


观察一下题目中数字的规律， 不难发现， 每对数的分母都是上对数的分子分母和， 而分子则是这个和再加上上一个分母。
然后， 简单的用个递归就行了。

with t(r, a, b)
as (select 1, '3', '2' from dual
union all
select
r+1,
pkg_bignum.bigplus(pkg_bignum.bigplus(a,b),b),
pkg_bignum.bigplus(a,b)
from t where r<1000)
select count(*) from t where length(a)>length(b)
/

  COUNT(*)
----------
       153

Executed in 1.781 seconds

tree_new_bee

Q58 Investigate the number of primes that lie on the diagonals of the spiral grid.

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

[ 本帖最后由 tree_new_bee 于 2011-1-1 22:05 编辑 ]

tree_new_bee

Q58与Q28的螺旋是一样的， 直接使用Q28的成果就行。

with t(n, sm) as (
select 1, 0 from dual
union all
select
n+1,
sm + case when pkg_prim2.isprim((2*n-1)*(2*n-1)- 2*(n-1))=0 then 1 else 0 end
+ case when pkg_prim2.isprim((2*n-1)*(2*n-1)- 4*(n-1))=0 then 1 else 0 end
+ case when pkg_prim2.isprim((2*n-1)*(2*n-1)- 6*(n-1))=0 then 1 else 0 end  
from t where n<3 or  sm/(4*n-3)>0.1)
select (2*max(n)-1) from t
/

(2*MAX(N)-1)
------------
       26241

Executed in 28.797 seconds

有点慢， 但想不出有什么好的优化手段。

〇〇

不知道调用函数的代价如何，其实3、5的倍数是有规律的
with t as
(select level n from dual connect by level <=20)
select ((2*n-1)*(2*n-1)- 6*(n-1)) a,((2*n-1)*(2*n-1)- 4*(n-1)) b,((2*n-1)*(2*n-1)- 2*(n-1))c
from t;

         A          B          C
---------- ---------- ----------
         1          1          1
         3          5          7
        13         17         *21
        31         37         43
        *57         #65         73
        91        101        *111
       133        #145        157
       *183        197        211
       241        257        *273
       307        #325        343
       *381        401        421
       463        #485        *507
       553        577        601
       *651        677        703
       757        #785        *813
       871        901        931
       *993       #1025       1057
      1123       1157       *1191
      1261       1297       1333
      *1407       #1445       1483

tree_new_bee

原帖由 〇〇 于 2011-1-1 20:45 发表
不知道调用函数的代价如何，其实3、5的倍数是有规律的
with t as
(select level n from dual connect by level  

isprim的性能，在判断一个非质数时是比较快的， 尤其是那种有2/3/5/7这样的小因子的合数时。
真正费时的是那些真的质数。
所以排除一些3/5的倍数，总体收益并不太多。

这段代码只调用函数40000次左右， 调用次数并不多，函数调用的开销几乎可以忽略。

以下试着预排除3/5/7, 可以看到几乎没有什么作用。

with t(n, sm) as (
select 1, 3 from dual
union all
select
n+1,
sm
+ case when mod((2*n-1)*(2*n-1)- 2*(n-1),3) = 0 or mod((2*n-1)*(2*n-1)- 2*(n-1),5) = 0 or mod((2*n-1)*(2*n-1)- 2*(n-1),7) = 0then 0
when pkg_prim2.isprim((2*n-1)*(2*n-1)- 2*(n-1))=0 then 1 else 0 end
+ case when mod((2*n-1)*(2*n-1)- 4*(n-1),3) = 0 or mod((2*n-1)*(2*n-1)- 4*(n-1),5) = 0 or mod((2*n-1)*(2*n-1)- 4*(n-1),7) = 0 then 0
when pkg_prim2.isprim((2*n-1)*(2*n-1)- 4*(n-1))=0 then 1 else 0 end
+ case when mod((2*n-1)*(2*n-1)- 6*(n-1),3) = 0 or mod((2*n-1)*(2*n-1)- 6*(n-1),5) = 0 or mod((2*n-1)*(2*n-1)- 6*(n-1),7) = 0 then 0
when pkg_prim2.isprim((2*n-1)*(2*n-1)- 6*(n-1))=0 then 1 else 0 end  
from t where n<3 or  sm/(4*n-3)>0.1)
select (2*max(n)-1) from t

(2*MAX(N)-1)
------------
       26241

Executed in 29.328 seconds

tree_new_bee

Q59 Using a brute force attack, can you decrypt the cipher using XOR encryption?

不抄原题了， 简单介绍一下：

给出一段密文的ascii码， 已知原文是一段普通英文文本。  密钥是3位小写字母，加密方法是循环使用密钥，用XOR方式加密。

求原文的ascii码的和。

密文文件如下：

〇〇

tnb请把工具包放在1楼啊，便于学习..

tree_new_bee

原帖由 〇〇 于 2011-1-1 22:19 发表
tnb请把工具包放在1楼啊，便于学习..

是说大数package和质数package吧， 我回头整理一下放到顶楼。