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

lastwinner

原帖由 tree_new_bee 于 10-12-12 22:12 发表
Q4还有一个可以改进之处是:6位数的回文数是11的倍数， 所以两个数字至少有一个是11的倍数。
但加上这个条件后，就必须把原来关于第两个数的大小的假设去掉了。

这个思路很好啊！原先的不太容易看出是11的倍数呢
1001＝7×11×13
100001＝11×9091

tree_new_bee

原帖由 〇〇 于 2010-12-12 20:30 发表
5楼的解法，在9i时间是相反的

最后一个语句在你那里，能快那么多， 有点不可思议。


另外我这里怪异的是， 那个语句中的t1.n<t2.n如果放到紧接着where的后面， 执行计划没有任何改变， 但速度却可以快很多。
优化器竟然对这个明显的条件都没有进行顺序调整？

SQL> with t as (select rownum+100 n from dual connect by rownum<=900)
  2  select max(t1.n*t2.n) from t t1, t t2
  3  --select t1.n, t2.n,t1.n*t2.n from t t1, t t2
  4  where
  5   substr(t1.n*t2.n,1,1) = substr(t1.n*t2.n,-1,1)
  6  and  substr(t1.n*t2.n,2,1) = substr(t1.n*t2.n,-2,1)
  7  and  substr(t1.n*t2.n,3,1) = substr(t1.n*t2.n,-3,1)
  8  and t1.n<t2.n
  9  /

MAX(T1.N*T2.N)
--------------
        906609

已用时间:  00: 00: 01.42

执行计划 ---------------------------------------------------------- Plan hash value: 1546677613 -------------------------------------------------------------------------------- ------------------------------- | Id  | Operation                       | Name                        | Rows  | Bytes | Cost (%CPU)| Time     | -------------------------------------------------------------------------------- ------------------------------- |   0 | SELECT STATEMENT                |                             |     1 |    26 |     6   (0)| 00:00:01 | |   1 |  TEMP TABLE TRANSFORMATION      |                             |       |       |            |          | |   2 |   LOAD AS SELECT                | SYS_TEMP_0FD9D66D8_B1C55C92 |       |       |            |          | |   3 |    COUNT                        |                             |       |       |            |          | |*  4 |     CONNECT BY WITHOUT FILTERING|                             |       |       |            |          | |   5 |      FAST DUAL                  |                             |     1 |       |     2   (0)| 00:00:01 | |   6 |   SORT AGGREGATE                |                             |     1 |    26 |            |          | |   7 |    NESTED LOOPS                 |                             |     1 |    26 |     4   (0)| 00:00:01 | |   8 |     VIEW                        |                             |     1 |    13 |     2   (0)| 00:00:01 | |   9 |      TABLE ACCESS FULL          | SYS_TEMP_0FD9D66D8_B1C55C92 |     1 |    13 |     2   (0)| 00:00:01 | |* 10 |     VIEW                        |                             |     1 |    13 |     2   (0)| 00:00:01 | |  11 |      TABLE ACCESS FULL          | SYS_TEMP_0FD9D66D8_B1C55C92 |     1 |    13 |     2   (0)| 00:00:01 | -------------------------------------------------------------------------------- SQL> with t as (select rownum+100 n from dual connect by rownum<=900)   2  select max(t1.n*t2.n) from t t1, t t2   3  --select t1.n, t2.n,t1.n*t2.n from t t1, t t2   4  where t1.n<t2.n   5  and  substr(t1.n*t2.n,1,1) = substr(t1.n*t2.n,-1,1)   6  and  substr(t1.n*t2.n,2,1) = substr(t1.n*t2.n,-2,1)   7  and  substr(t1.n*t2.n,3,1) = substr(t1.n*t2.n,-3,1)   8  / MAX(T1.N*T2.N) --------------         906609 已用时间:  00: 00: 00.81 执行计划 ---------------------------------------------------------- Plan hash value: 1937261042 -------------------------------------------------------------------------------- ------------------------------- | Id  | Operation                       | Name                        | Rows  | Bytes | Cost (%CPU)| Time     | -------------------------------------------------------------------------------- ------------------------------- |   0 | SELECT STATEMENT                |                             |     1 |    26 |     6   (0)| 00:00:01 | |   1 |  TEMP TABLE TRANSFORMATION      |                             |       |       |            |          | |   2 |   LOAD AS SELECT                | SYS_TEMP_0FD9D66D6_B1C55C92 |       |       |            |          | |   3 |    COUNT                        |                             |       |       |            |          | |*  4 |     CONNECT BY WITHOUT FILTERING|                             |       |       |            |          | |   5 |      FAST DUAL                  |                             |     1 |       |     2   (0)| 00:00:01 | |   6 |   SORT AGGREGATE                |                             |     1 |    26 |            |          | |   7 |    NESTED LOOPS                 |                             |     1 |    26 |     4   (0)| 00:00:01 | |   8 |     VIEW                        |                             |     1 |    13 |     2   (0)| 00:00:01 | |   9 |      TABLE ACCESS FULL          | SYS_TEMP_0FD9D66D6_B1C55C92 |     1 |    13 |     2   (0)| 00:00:01 | |* 10 |     VIEW                        |                             |     1 |    13 |     2   (0)| 00:00:01 | |  11 |      TABLE ACCESS FULL          | SYS_TEMP_0FD9D66D6_B1C55C92 |     1 |    13 |     2   (0)| 00:00:01 |

[ 本帖最后由 〇〇 于 2010-12-13 07:37 编辑 ]

tree_new_bee

OO给编辑进来的代码显示代码不错， 保存下来了。

tree_new_bee

Q5:What is the smallest number divisible by each of the numbers 1 to 20?

这个题实现起来很简单， 但可优化之处也很多。

SQL: 简单的SQL+人肉， 1..20的最小公倍数必然是1..20范围内所有质数的乘积的倍数。

with t as (select rownum*2*3*5*7*13*11*17*19 n from dual connect by rownum<=100)
, t20 as (select rownum+1 d from dual connect by rownum<20)
select min(n) from t
where not exists (select 1 from t20 where mod(n,d) <> 0)


利用计算lcm的递归with语句：


with t as (select rownum n from dual connect by rownum<=20)
,t1 as (select n n1, lead(n ,1) over (order by n desc) n2 from t )
,t2 as (select max(n1) n1, max(n2)n2  from t1 )
, mlcm(a,b, gcd, b2, lcm) as
(select n2, n1, n2, n1, n1  from t2
union all
select
case when b2=0 then (select max(n) from t where n<a) else a end,
case when b2=0 then lcm                              else b end,
case when b2=0 then (select max(n) from t where n<a) else b2 end,
case when b2=0 then  lcm                             else mod(gcd, b2) end,
case when mod(gcd, b2)=0 then lcm*a/b2               else lcm end

from mlcm where a is not null
)
cycle a,b,gcd,b2 set iscycle to 'y' default 'n'
select max(lcm) from mlcm where b2=0


  MAX(LCM)
----------
232792560

Executed in 0.032 seconds

[ 本帖最后由 tree_new_bee 于 2010-12-15 19:22 编辑 ]

tree_new_bee

连续数的公倍数， 可以这样用人肉计算：
1..20的公倍数：
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19 *20
4，前面出现过2，用一个2替代， 变成1 * 2 * 3 * 2
6， 前面有2,3, 所以可忽略
8， 前面有2个2， 再加一个2即可，  变成1 * 2 * 3 * 2 *5 *_ * 7 * 2
同理，10，12 , 14，15, 18，20 可忽略， 9需要加一个3替代，16需要加一个2替代。最终变成：
1 * 2 * 3 * 2 * 5 * _ * 7 * 2 * 3 * _ * 11 * _ * 13 * _ * _ * 2 * 17 * _ * 19 *_
= 1 * 2 * 3 * 2 * 5  * 7 * 2 * 3  * 11  * 13  * 2 * 17 *  19
= 1 * 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19

SQL> select 1 * power(2,4) * power(3,2) * 5 * 7 * 11 * 13 * 17 * 19 from dual
  2  /

1*POWER(2,4)*POWER(3,2)*5*7*11
------------------------------
                     232792560

[ 本帖最后由 tree_new_bee 于 2010-12-13 11:23 编辑 ]

tree_new_bee

Q6:Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.


这个简单， 不写语句了。
无非是简单循环， 和数学计算两种方法。对于sql来说，简单循环计算效率也很高。

数学计算：
(1+2+..n)^2 = (n*(n+1)/2) ^2 = n^2 * (n+1)^2 /4
1^2 + 2^2 + .. n^2 = n*(n+1)*(2n+1)/6

[ 本帖最后由 tree_new_bee 于 2010-12-15 19:22 编辑 ]

tree_new_bee

Q7:What is the 10001^(st) prime number?

考验人的东西来了， 不过好在之前这个版对于质数判断讨论了很多了。

单用SQL, 如下的语句已经算是很优化了， 不过性能还是不可接受， 我这里要运行422秒！

with t1 as (
select 5 n from dual union all
select rownum*6+1 n from dual connect by rownum<=20000 union all
select rownum*6+5 n from dual connect by rownum<=20000
order by n
)
, t as (
select 2 n from dual union all select 3 n from dual union all
select * from t1 )
,t2 as (select  rownum rn, n from t outer
where not exists (select 1 from t1 where n<=sqrt(outer.n) and mod(outer.n,n) = 0) and rownum<=10001)
select n from t2 where rn=10001

[ 本帖最后由 tree_new_bee 于 2010-12-15 19:21 编辑 ]

tree_new_bee

用函数进行质数判断， 下面的函数在以前的帖子中有过。
  function isprim(n number) return number is  
  nsqrt number;
  i number;
  step number;
  begin
       if n = 2 then return 0; end if;
       if (n mod 2) = 0 then        return 2;        end if;
      nsqrt := ceil(sqrt(n));
      i := 3;
      step:=2;
      while (i <= nsqrt) loop
         if (n mod i) = 0 then
           return i;
         end if;
         if i>6 then step := 6 - step; end if;
         i:=i+step;
      end loop;
      return 0;
  end;


用sql语句遍历调用这个函数， 结果：

with t1 as (
select 5 n from dual union all
select rownum*6+1 n from dual connect by rownum<=20000 union all
select rownum*6+5 n from dual connect by rownum<=20000
order by n
)
, t as (
select 2 n from dual union all
select 3 n from dual union all
select * from t1 )
,tt as (select rownum rn, n from t where pkg_prim2.isprim(n) = 0 and rownum<=10001)
select * from tt where rn = 10001

SQL> /

        RN          N
---------- ----------
     10001     104743

Executed in 1.484 seconds

tree_new_bee

或者，还把遍历过程也放到函数里：
  function findnth(d number) return number is
    cnt number;
    i number;
  begin
    if d =1  then return 2; end if;
    if d =2  then return 3; end if;
    if d =3  then return 5; end if;
    cnt:=3;
    i:= 1;
  while cnt<d loop
    if (isprim(i*6+1)=0) then
      cnt := cnt+1;
      if (cnt=d) then return i*6+1; end if;
    end if;
    if (isprim(i*6+5)=0) then
      cnt := cnt+1;
      if (cnt=d) then return i*6+5; end if;
    end if;

    i:=i+1;
  end loop;
  return 0;
end;

SQL> select pkg_prim2.findnth(10001) from dual;

PKG_PRIM2.FINDNTH(10001)
------------------------
                  104743

Executed in 1.25 seconds

SQL>

tree_new_bee

最后，用java来实现：
create or replace and compile java source named prim as
public class prim
{
public static double isprim(double d)
{
long n=(long)d;
if (n==2) return 0;
if (n%2==0)return 2;
long nsqrt=(long)(java.lang.Math.sqrt(d))+1;
long i=3;
long step=2;
while (i<=nsqrt)
{
if(n%i==0)return i;
if(i>6)step=6-step;
i=i+step;
}
return 0;
};

public static double findnth(long d)
{

  double i=1;
  long cnt;

  if(d==1) return 2;
  if(d==2) return 3;
  if(d==3) return 5;
   
  cnt=3;
  while (cnt<d)
  {
    if (isprim(i*6+1)==0)
      {
      cnt++;
      if (cnt==d) return i*6+1;
      }
    if (isprim(i*6+5)==0)       {
      cnt++;
      if (cnt==d) return i*6+5;
      }

    i++;
  }
  return 0;

}
}


在pkg_prim包头中加入：
function isprimj(x number) return number
as
language Java Name
'prim.isprim(double) return double';

function jfindnth(x number) return number
as
language Java Name
'prim.findnth(long) return double';


SQL> select pkg_prim2.jfindnth(10001) from dual;

PKG_PRIM2.JFINDNTH(10001)
-------------------------
                   104743

Executed in 0.328 seconds


不过， 如果是用SQL遍历，去执行pkg_prim.isprimj, 性能还不如用pl/sql函数。
11  ,tt as (select rownum rn, n from t where pkg_prim2.isprimj(n) = 0 and rownum<=10001)
12  select * from tt where rn = 10001
13  /

        RN          N
---------- ----------
     10001     104743

Executed in 2.109 seconds

SQL>

怀疑是频繁的SQL/PLSQL/JAVA上下文的切换，导致运行效率降低。