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

tree_new_bee · 发表于 2010-12-17 10:19

那个分割成对称的两块的有点意思。
似乎就是从0,0点出发到5,5点的所有路径中必须全部点都处于整个形状的一半的地方。

换句话说，就是对于路径中所经过的所有点，如果画一个能把这所有点都圈进来的多边形，这个多边形不能把5，5点包到内部。

tree_new_bee · 发表于 2010-12-17 10:20

Q18 Find the maximum sum travelling from the top of the triangle to the base.

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

[ 本帖最后由 tree_new_bee 于 2010-12-17 12:06 编辑 ]

tree_new_bee · 发表于 2010-12-17 10:22

照例，先来的总是最笨的办法。
暴力求解:

with tstr as (
select 1 r, '75 '                                        str from dual union all
select 2 r, '95 64 '                                     str from dual union all
select 3 r, '17 47 82 '                                  str from dual union all
select 4 r, '18 35 87 10 '                               str from dual union all
select 5 r, '20 04 82 47 65 '                            str from dual union all
select 6 r, '19 01 23 75 03 34 '                         str from dual union all
select 7 r, '88 02 77 73 07 63 67 '                      str from dual union all
select 8 r, '99 65 04 28 06 16 70 92 '                   str from dual union all
select 9 r, '41 41 26 56 83 40 80 70 33 '                str from dual union all
select 10 r, '41 48 72 33 47 32 37 16 94 29 '             str from dual union all
select 11 r, '53 71 44 65 25 43 91 52 97 51 14 '          str from dual union all
select 12 r, '70 11 33 28 77 73 17 78 39 68 17 57 '       str from dual union all
select 13 r, '91 71 52 38 17 14 91 43 58 50 27 29 48 '    str from dual union all
select 14 r, '63 66 04 68 89 53 67 30 73 16 69 87 40 31 ' str from dual union all
select 15 r, '04 62 98 27 23 09 70 98 73 93 38 53 60 04 23' str from dual )
,t1 as (select rownum c  from dual connect by level<=15)
,t01 as (select rownum-1 n01 from dual connect by rownum<=2)
,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)
--select sys_connect_by_path(num,'/') from t2 where level=15 start with r=1 and c=1 connect by r=prior r+1 and c in (prior c, prior c+1)
, tree(tr,tc,v, sm) as (
select 1, 1, num , num from t2 where r=1 and c=1
union all
select
tr+1,
tc+n01,
(select num from t2 where r= tr+1 and c = tc+n01),
sm + (select num from t2 where r= tr+1 and c = tc+n01)
from tree, t01 where tr<15)
select max(sm) from tree where tr=15 order by tr, tc

MAX(SM)
----------
   1074

Executed in 1.828 seconds

那颗大树太占地方了，后面再写语句都把那个大树略过，只写tstr来引用。

tree_new_bee · 发表于 2010-12-17 11:23

上面是全部枚举所有可能路径，路径数目是2^n, 所以算法复杂度是O(2^n)

对于这棵典型的二叉树，这样：  从底部第二行开始，每个位置都更新为原来的值+下层两个子节点的较大值。
这样每一层都只需比较n次，总的比较次数是n(n+1)/2,  也就是O(n^2)的复杂度。

用递归with解决这种一个节点要访问多个父节点的问题，太麻烦了，还是MODEL省事：

with tstr as ( 。。。)
,t1 as (select rownum c  from dual connect by level<=15)
,t01 as (select rownum-1 n01 from dual connect by rownum<=2)
,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)<15
                  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 max(num) from t3

  MAX(NUM)
----------
   1074

Executed in 0.062 seconds

tree_new_bee · 发表于 2010-12-17 11:44

题目中说后面还有一道题也是同样的类型，只是行数比较多。所以在这里就不纠缠了。

tree_new_bee · 发表于 2010-12-17 11:44

Q19 How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

You are given the following information, but you may prefer to do some research for yourself.

* 1 Jan 1900 was a Monday.
* Thirty days has September,
   April, June and November.
   All the rest have thirty-one,
   Saving February alone,
   Which has twenty-eight, rain or shine.
   And on leap years, twenty-nine.
* A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

这个用oracle的日期操作太easy了。

SQL> with t as (select add_months(to_date('1901-01-01','yyyy-mm-dd') , rownum-1) dt from dual connect by rownum<= 12*100)
  2  select count(*) from t  where to_char(dt,'D') = 1
  3  /

  COUNT(*)
----------
   171

SQL>

就算手工计算，也只是个细心活。 pass

[ 本帖最后由 tree_new_bee 于 2010-12-17 12:06 编辑 ]

tree_new_bee · 发表于 2010-12-17 11:51

Q20 Find the sum of digits in 100!

这个用前面Q16的大数包，前面在包中放的大数阶乘就是为这道题准备的。

SQL> with t as (select /*+ RESULT_CACHE  */ pkg_bignum.bigfact(100) str from dual)
  2  ,t1 as (select rownum n from T connect by rownum<= length(str))
  3  select  sum(substr(str,n,1)) from t, t1
  4  /

SUM(SUBSTR(STR,N,1))
--------------------
               648

Executed in 0.312 seconds

[ 本帖最后由 tree_new_bee 于 2010-12-17 12:06 编辑 ]

tree_new_bee · 发表于 2010-12-17 12:05

Q21 Evaluate the sum of all the amicable numbers under 10000.

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

这次，12题的好多思考成果在这里都没用了。那里考虑的只是取得因数的数目，这里需要关心因数的具体数值了。

[ 本帖最后由 tree_new_bee 于 2010-12-17 12:35 编辑 ]

tree_new_bee · 发表于 2010-12-17 12:44

简单的SQL:
with targ as (select 10000 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 ta.n, ta.dn from t3 ta, t3 tb where ta.n=tb.dn and ta.dn=tb.n and ta.n<>tb.n
select sum(ta.n) from t3 ta, t3 tb where ta.n=tb.dn and ta.dn=tb.n and ta.n<>tb.n

SQL> /

SUM(TA.N)
----------
31626

Executed in 1.719 seconds

速度不算快，但就解决这个题的10000个数来说还算能接受。

tree_new_bee · 发表于 2010-12-17 13:08

换成PL/SQL, 能略强一些。

declare
  sm number;
  type tnumlist is table of number index by pls_integer;
  numlist tnumlist;
begin
  for i in 1 .. 10000 loop
sm := 1;
for j in 2 .. sqrt(i) loop
   if mod(i, j) = 0 then
      sm := sm + j + i / j;
   end if;
end loop;
if sqrt(i) = floor(sqrt(i)) then
   sm := sm - sqrt(i);
end if;
numlist(i) := sm;

  end loop;
  sm := 0;
  for i in 1 .. 10000 loop
if numlist.exists(numlist(i)) then
   if i = numlist(numlist(i)) and i <> numlist(i) then
      sm := sm + i ;
   end if;
end if;
  end loop;
  dbms_output.put_line('sum is: ' || sm);
end;
/

sum is: 31626

PL/SQL procedure successfully completed

Executed in 0.641 seconds

SQL>