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

tree_new_bee · 发表于 2010-12-20 12:08

用大数相乘函数做暴力，写起来很轻松，跑起来很慢。

with t as (select rownum+1 n from dual connect by rownum<100)
,t1 as (select t1.n n1, t2.n n2, pkg_bignum.bigpower(t1.n, t2.n) p from t t1, t t2 )
select count(distinct p) from t1

COUNT(DISTINCTP)
----------------
9183

Executed in 102.281 seconds

tree_new_bee · 发表于 2010-12-20 12:54

稍微变通一下，取一下对数，就不用再用大数运算了。

能够不用大数，即使暴力也非常快。

with t as (select rownum+1 n from dual connect by rownum<100)
,t1 as (select t1.n n1, t2.n n2, trunc(t2.n*log(10,t1.n),30) p from t t1, t t2 )
select count(distinct p) from t1

COUNT(DISTINCTP)
----------------
9183

Executed in 0.437 seconds

应该有好的人肉算法，一时想不出来。

tree_new_bee · 发表于 2010-12-20 15:04

Q30 Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1^(4) + 6^(4) + 3^(4) + 4^(4)
8208 = 8^(4) + 2^(4) + 0^(4) + 8^(4)
9474 = 9^(4) + 4^(4) + 7^(4) + 4^(4)

As 1 = 1^(4) is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

tree_new_bee · 发表于 2010-12-20 15:19

Q30 还是用暴力。

只是在暴力前要稍稍人肉一下，用于确定上限：

对于7位数字，各个数字的5次方的最大和为：
7* 9^5 < 7*10^5 = 700000, 只有6位数字。
因此可以排除7位及以上的数字，只暴力6位以内的组合。

另外，对于6位数字，各个数字的5次方的最大和为：
6*9^5 = 6* 59049 = 354294, 所以这个6位(或以内)不超过354294, 也即第一位数字必须小于4

with targ as (select 6 arg from dual)
, t as (select rownum-1 n from dual connect by rownum<=10)
,ta as (select t1.n || t2.n  || t3.n || t4.n || t5.n || t6.n p
from t t1, t t2, t t3, t t4, t t5, t t6
where t1.n<4 and power(t1.n,5) + power(t2.n,5) + power(t3.n,5) + power(t4.n,5) + power(t5.n,5) + power(t6.n,5)
= t1.n || t2.n  || t3.n || t4.n || t5.n || t6.n
)
--select * from ta where p>1
select sum(p) - 1 from ta

  SUM(P)-1
----------
443839

Executed in 3.828 seconds

SQL>

列出这些数字：

004150
004151
093084
092727
054748
194979

6位数竟然只有1个，害我多循环几十万次！

tree_new_bee · 发表于 2010-12-20 20:00

原帖由 tree_new_bee 于 2010-12-20 12:54 发表
应该有好的人肉算法，一时想不出来。

Q29人肉，要从这里着手：

所有会重复的幂，都是作为底的数之间有幂次关系或者与同一个数有幂次关系，如2^4 = 4^2,  2^6=8^2,  4^6=8^4  其中的底4=2^2, 8=2^3,  4与8都与2有幂次关系
没有这种关系的底，所形成的幂是不会有重复的。

这样，作为第一步，首先要找出这些有幂次关系的数。

with t as (select rownum+1 n from dual connect by rownum<100)
,t1 as (select t1.n n1, t2.n n2, round(log(t2.n, t1.n)) m from t t1, t t2
where t2.n<=10
and log(t2.n, t1.n) >1 and round(log(t2.n, t1.n),0) = round(log(t2.n, t1.n),3)
)
,t2 as (select n1,  n2, m from t1 where n2 not in(select n1 from t1)
union select n2 n1, n2 n2, 1 from t1 where n2 not in(select n1 from t1))
select * from t2

      N1       N2       M
---------- ---------- ----------
      2       2       1
      4       2       2
      8       2       3
      16       2       4
      32       2       5
      64       2       6
      3       3       1
      9       3       2
      27       3       3
      81       3       4
      5       5       1
      25       5       2
      6       6       1
      36       6       2
      7       7       1
      49       7       2
      10       10       1
   100       10       2

18 rows selected

Executed in 0.391 seconds

其中n1表示比较大的数， n2是比较小的数， m表示n1是n2的多少次方。

这个表里的18个数之外的其它81个数的任意幂次，都不会与其它数产生冲突，这81个会产生81*99 = 8019个唯一数。

[ 本帖最后由 tree_new_bee 于 2010-12-20 20:50 编辑 ]

tree_new_bee · 发表于 2010-12-20 21:04

第二部，根据上面的结果去找这些底形成的唯一幂。

推导一下：
假设两个数分别为x1^y1=x2^y2, 这两个数重复的话是因为x1与x2共同是某个数的幂，设这个数为x0, x1=x0^n1, x2=x0^n2
则上式变为 (x0^n1)^y1 = (x0^n2)y2
即x0^(n1*y1) = x0^(n2*y2)
所以n1*y1 = n2*y2

以具体例子来说：对于4^6 和8^4, 4=2^2, 8=2^3, 而2*6 = 3*4, 所以这两个数相等。

这样，利用第一步的成果，就容易得到这18个数的结果数量，加上8019即最后的结果。

with t as (select rownum+1 n from dual connect by rownum<100)
,t1 as (select t1.n n1, t2.n n2, round(log(t2.n, t1.n)) m from t t1, t t2
where t2.n<=10
and log(t2.n, t1.n) >1 and round(log(t2.n, t1.n),0) = round(log(t2.n, t1.n),3)
)
,t2 as (select n1,  n2, m from t1 where n2 not in(select n1 from t1)
union select n2 n1, n2 n2, 1 from t1 where n2 not in(select n1 from t1))
--select * from t2
,t3 as (select n1, n2, m, m*n p  from t2, t)
select count(*)+81*99  total from (select distinct n2, p from t3);

   TOTAL
----------
   9183

Executed in 0.25 seconds

tree_new_bee · 发表于 2010-12-20 21:57

Q31 Investigating combinations of English currency denominations.

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

题目本身简单到无趣的地步。
玩的是性能。

tree_new_bee · 发表于 2010-12-20 22:13

罗列一些能轻易看出且对性能有帮助的事实：
1/2累加的数量能被5整除，1/2/5累加的数量能被10整除, 1/2/5/10/20累加的数量能被50整除,1/2/5/10/20/50累加的数量能被100整除
1/5累加的数量必须是偶数。
200的数量只能有0或1个， 100的数量不能超过2，。。。。

利用这些简单的事实写出的语句：

with t as (select /*+ RESULT_CACHE */  rownum-1 n from dual connect by rownum<=101)
select count(*)
from
t t2,
(select * from t where n<=40) t3,
(select * from t where n<=20) t4,
(select * from t where n<=10) t5,
(select * from t where n<=5) t6,
(select * from t where n<=2) t7,
(select * from t where n<=1) t8
where --t8.n in(0,1) and t7.n in(0,1,2) and t6.n<=4 and t5.n <=10 and t4.n<=20 and t3.n<=40 and t2.n<=100 and
mod(200 - ( t3.n*5 + t4.n*10 + t5.n*20 + t6.n*50 + t7.n*100 + t8.n*200),5) = 0
and mod(200 - (       t4.n*10 + t5.n*20 + t6.n*50 + t7.n*100 + t8.n*200),10) = 0
and mod(200 - (                            t6.n*50 + t7.n*100 + t8.n*200),50) = 0
and mod(200 - (                                     t7.n*100 + t8.n*200),100) = 0
--and mod(200 - ( t2.n*2 + t4.n*10 + t5.n*20 + t6.n*50 + t7.n*100 + t8.n*200),2) = 0
and 200 - (t2.n*2 + t3.n*5 + t4.n*10 + t5.n*20 + t6.n*50 + t7.n*100 + t8.n*200) >=0
and  200 - (t2.n*2 + t3.n*5 + t4.n*10 + t5.n*20 + t6.n*50 + t7.n*100 + t8.n*200) <=200;

  COUNT(*)
----------
   73682

Executed in 51.25 seconds

SQL>

1/5累加的数量必须是偶数,这个条件加上的话，反倒更慢，要100多秒。奇怪。

tree_new_bee · 发表于 2010-12-20 22:25

下面要稍微人肉一下了：
考虑一下，如果只用1p和2p组成的话，那么只要选择了2p的数量， 1p的数量就已经确定了，因此可选的组合为0个2到钱数/2的2，共有(n/2)+1种组合。

这样，我们只要考虑5p以上的各种组合，并且对剩下的钱数应用上面的结果即可。

只考虑5p以上的组合，使得循环次数大大减少。

当然还可以继续往下推导，不过再推导就变成了纯人肉了，那样也无趣。

with t as (select /*+ RESULT_CACHE */  rownum-1 n from dual connect by rownum<=41)
select sum(floor((200-(t3.n*5 + t4.n*10 + t5.n*20 + t6.n*50 + t7.n*100 + t8.n*200))/2)+1)
from
(select * from t where n<=40) t3,
(select * from t where n<=20) t4,
(select * from t where n<=10) t5,
(select * from t where n<=5) t6,
(select * from t where n<=2) t7,
(select * from t where n<=1) t8
where --t8.n in(0,1) and t7.n in(0,1,2) and t6.n<=4 and t5.n <=10 and t4.n<=20 and t3.n<=40 and t2.n<=100 and
mod(200 - ( t3.n*5 + t4.n*10 + t5.n*20 + t6.n*50 + t7.n*100 + t8.n*200),5) = 0
and mod(200 - (       t4.n*10 + t5.n*20 + t6.n*50 + t7.n*100 + t8.n*200),10) = 0
and mod(200 - (                            t6.n*50 + t7.n*100 + t8.n*200),50) = 0
and mod(200 - (                                     t7.n*100 + t8.n*200),100) = 0
and 200 - (t3.n*5 + t4.n*10 + t5.n*20 + t6.n*50 + t7.n*100 + t8.n*200) >=0
and 200 - (t3.n*5 + t4.n*10 + t5.n*20 + t6.n*50 + t7.n*100 + t8.n*200) <=200

SUM(FLOOR((200-(T3.N*5+T4.N*10
------------------------------
                     73682

Executed in 1.156 seconds

SQL>

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

newkid · 发表于 2010-12-20 22:34

NB哥真快，看题都赶不上你做题了。
那个硬币问题我也做过，还用过递归WITH。
Q29我想把100以内的数分解质因子，然后把幂变成系数，看看总共有几种。你后来用的方法更好，只关心那些可能重复的。