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

tree_new_bee

原帖由 newkid 于 2010-12-18 01:10 发表
107楼的j:=j+step换成对质数表遍历怎么样？不过反正你才在100之内循环，不用那么麻烦了。

换成质数表当然会好很多。

对j的循环次数，是那段代码的性能关节点。

在贴这段代码之前， 我用的while j<=icopy 来循环， 结果性能很差， 比上一个版本的要慢许多倍。
不得已，才改成只循环到sqrt(icopy),  然后在后面再额外处理最后一个因子。(大于sqrt(i)的因子最多只有一个， 并且就是最后的icopy)
对于10000来说，就手工加个 in (2,3,5,....97)的判断就行。  只不过使得参数不能随意调整了。

tree_new_bee

Q23 Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

这个题目看着有点绕， 我来理一下：
一个数的除自身外的因数和如果大于这个数本身， 就称为abundant number。
28123以上的数都能拆成两个abundant number的和。
找出所有不能拆成两个abundant number和的那些数， 求他们的和。

tree_new_bee

用简单的SQL来做：

with targ as (select 28123  arg from dual)
,t1 as (select rownum n from targ connect by rownum<=arg)
,t2 as (select rownum d from targ connect by rownum*rownum<=arg)
,t3 as (select n, sum(d) + sum(n/d) - sum(case when n/d = d then d else 0 end) -n  dn from  t1, t2
where n>=d*d and mod(n, d) = 0  group by n)
select sum(n) from t1 where not exists (
select  1 from t3 ta, t3 tb where ta.n<=tb.n and ta.dn>ta.n and tb.dn>tb.n and ta.n+tb.n=t1.n)

    SUM(N)
----------
   4179871

Executed in 45.828 seconds

不快，但没有想象中的那么慢。 本来我以为要把参数缩小一个数量级才能在可接受的时间内输出结果呢。

tree_new_bee

用plsql, 21题的成果基本上可以拿来直接用。

declare
  arg constant number := 28123;
  sm number;
  type tnumlist is table of number index by pls_integer;
  numlist tnumlist;
  numlist2 tnumlist;
i number;
j number;
icopy number;
step number;
cnt number;
begin
  for i in 1..arg  loop
        cnt := 0;
        sm := 1;
        if bitand(i,1)= 0 then step:=1; else step:=2; end if; --奇数的质因子中不会有偶数，可以跳过偶数
        icopy := i;
        j := 2;
        while j*j<=icopy loop
            while  j<=icopy and mod(icopy,j) = 0 loop
               icopy := icopy/j;
               cnt:=cnt+1;
            end loop;
           if cnt>0 then sm := sm * (power(j,cnt+1)-1)/(j-1); end if;
           cnt:=0;
           if j=2 then j:=j+1; else j:=j+step; end if;
        end loop;
        if icopy>1 then sm:=sm*(icopy+1); end if;  --icopy+1 == (icopy^2-1)/(icopy-1)
        if sm>i+i then numlist(i) := sm-i;end if;
  end loop;
  
   sm := 0;
  dbms_output.put_line('numlist.count: ' || numlist.count);

  i:= numlist.first;
  while i is not null loop
        j:=i;
        while j is not null and j<=arg-i loop
              numlist2(i+j) :=1;
              j:=numlist.next(j);
        end loop;
        i:=numlist.next(i);
  end loop;

  i:= numlist2.first;
  while i is not null loop
      sm:=sm+i;
      i:=numlist2.next(i);
  end loop;

  sm:= arg*(arg+1)/2 - sm;
  dbms_output.put_line('sum is: ' || sm);
end;

PL/SQL procedure successfully completed

Executed in 8.453 seconds

SQL>


比SQL快， 但并不理想。
经过profiler, 这次分解因数不算大开销了，大部分开销都发生在对numlist的两层循环上。

tree_new_bee

想一想SQL并不很慢的原因， 应该是出在not exists很高效的循环上。
所以那个两层循环，需要用Not exists的思路来做。

declare
  arg constant number := 28123;
  sm number;
  type tnumlist is table of number index by pls_integer;
  numlist tnumlist;
  --numlist2 tnumlist;
i number;
j number;
icopy number;
step number;
cnt number;
found boolean;
begin
  for i in 1..arg  loop
        cnt := 0;
        sm := 1;
        if bitand(i,1)= 0 then step:=1; else step:=2; end if; --奇数的质因子中不会有偶数，可以跳过偶数
        icopy := i;
        j := 2;
        while j*j<=icopy loop
            while  j<=icopy and mod(icopy,j) = 0 loop
               icopy := icopy/j;
               cnt:=cnt+1;
            end loop;
           if cnt>0 then sm := sm * (power(j,cnt+1)-1)/(j-1); end if;
           cnt:=0;
           if j=2 then j:=j+1; else j:=j+step; end if;
        end loop;
        if icopy>1 then sm:=sm*(icopy+1); end if;  --icopy+1 == (icopy^2-1)/(icopy-1)
        if sm>i+i then numlist(i) := sm-i;end if;
  end loop;
  
   sm := 0;
  for i in 1..arg loop
    found:=false;
        j:= numlist.first;
        while j<=i and j is not null  loop
              if numlist.exists(i-j) then
                found:=true;
                exit;
              end if;
              j:=numlist.next(j);
        end loop;
        if not found then sm:=sm+i; end if;
  end loop;   

  dbms_output.put_line('sum is: ' || sm);
end;

sum is: 4179871

PL/SQL procedure successfully completed

Executed in 4.265 seconds




修改后，内层循环的次数可以降低很多，使得总循环次数能减少2/3， 而且还省了一个numlists. 简明多了。

tree_new_bee

Q24  What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012   021   102   120   201   210

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

tree_new_bee

这个题可以先做些分析：
以0开头的后面为1-9的全部组合有9！=362880个
也即从第1个到第362880个全部为0开头
从第362880+1个到第2*362880个全部为1开头
因此第100万个，应该是以(1E6-1) div 9! =2即第2个数开头。 第二个数就是2
同理， 下一个数是上个数的余数274240-1 div 8! =6  即第6个数开头， 0-9中去除上一步用过的2后， 剩下的第6个数，是7
。。。

这个用plsql来做的话，应该很容易， 不过因为没有性能问题， 我想用sql挑战一下自己。

tree_new_bee

先来第一步, 找出这些序号。

SQL语句用了两层递归， 一次求阶乘， 一次求序号。

with targ as (select 1e6 arg1,9 arg2 from dual)
, prod(lastnum, lastprod) as
(select 0, 1  from dual
union all
select lastnum+1, (lastnum+1)*lastprod
from prod,targ
where lastnum < arg2
)
, perm(num, n, prd, d, m) as(
select arg1, 9, lastprod, 0, arg1 from targ,prod where lastnum=9
union all
select
num,
n-1,
lastprod,
floor((m-1)/prd),
mod(m-1,prd)+1
from perm,prod where n>=0 and lastnum=n-1)
select rownum x, d from perm where n<9 order by n desc
/

         X          D
---------- ----------
         1          2
         2          6
         3          6
         4          2
         5          5
         6          1
         7          2
         8          1
         9          1

9 rows selected

Executed in 0.078 seconds

tree_new_bee

第一步的结果有了， 第二步似乎不太容易， 想半天没头绪。
把需求详细描述一下， 大家帮想吧：

就是给定以下数：
         X          D
---------- ----------
         1          2
         2          6
         3          6
         4          2
         5          5
         6          1
         7          2
         8          1
         9          1
第1个数2， 要得到0..9的第2+1个数， 即2
第2个数6， 要得到0..9除上面的2以外的第6+1个数， 即7
第3个数6， 要得到0..9除上面的2/7以外的第6+1个数， 即8
以此类推。

tree_new_bee

用了第三次递归， 把结果整出来了。

上面的sql有个小问题， 最后一个序号没得到， 对于人工来说没问题， 只要知道最后一个数加上就行。
SQL不加处理的后面操作比较麻烦，所以稍作修改，与阶乘表用外连接关联， 从而取得第10个数



with targ as (select 1e6 arg1,9 arg2 from dual)
, prod(lastnum, lastprod) as
(select 0, 1  from dual
union all
select lastnum+1, (lastnum+1)*lastprod
from prod,targ
where lastnum < arg2
)
, perm(num, n, prd, d, m) as(
select arg1, 9, lastprod, 0, arg1 from targ,prod where lastnum=9
union all
select
num,
n-1,
lastprod,
floor((m-1)/prd),
mod(m-1,prd)+1
from perm,prod where n>=0 and lastnum(+)=n-1)
--select * from perm
,tseq as (select rownum x, d from perm where n<9 order by n desc)
, thelastdifficultstep (r, digi, str,path) as (
select 0, '', '0123456789', cast('' as varchar2(1000)) from dual
union all
select  
r+1,
substr(str,d+1,1),
translate(str, '$'||path||substr(str,d+1,1), '$'),
path || substr(str,d+1,1)
from thelastdifficultstep,tseq where r<=10 and x=r+1)
--select * from thelastdifficultstep
select path from thelastdifficultstep where r=10

PATH
--------------------------------------------------------------------------------
2783915460

Executed in 0.297 seconds



第一次解决一个问题用三层递归。 脑袋快麻木了。