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

tree_new_bee

有了正确的，才知道33#的函数错在哪里了。

那个判断是否是顺子的地方， 应该用-1, 写成+1了， 所以所有的顺子都没判断出来。

if to_number(hand(i).val,'X') <> to_number(hand(i-1).val,'X')+1 then straight:=false; end if;

改为

if to_number(hand(i).val,'X') <> to_number(hand(i-1).val,'X')-1 then straight:=false; end if;

修改后， 使用函数：

SQL> select count(*)
  2  from euler_poker
  3  where poker_rank(p1) >poker_rank(p2)
  4  /

  COUNT(*)
----------
       376

Executed in 0.312 seconds

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

tree_new_bee

Q55 How many Lychrel numbers are there below ten-thousand?
原题太长了。 用OO发的中文来代替：

题目简介：首先介绍一个数学名词：利克瑞尔数（Lychrel Number）：指的是将该数与将该数各数位逆序翻转
后形成的新数相加、并将此过程反复迭代后，结果永远无法是一个回文数的自然数。
　　现在已知对于10000以内的自然数，要么能够在50步（指将这个数与其逆序后的数相加的过程）内得到一
个回文数；要么该数是一个利克瑞尔数。
　　求：10000以内利克瑞尔数的个数

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

tree_new_bee

难题后面总是要跟几道容易些的题的。

这道用递归可以简单搞掂。

with pal(n, r, num) as (
select rownum, 1, rownum+reverse(to_char(rownum)) from dual connect by rownum<=10000
union all
select n, r+1, num+reverse(to_char(num))
from pal where r<50 and num <> reverse(to_char(num))
)
select count(*) from pal where r=50

  COUNT(*)
----------
       249

Executed in 0.875 seconds


实际上这道题有很大的优化空间， 如同14题一样，有些路径上已有的数可以跳过。
不过， 由于数据量小， 不值得花那个力气了。

tree_new_bee

Q56  Considering natural numbers of the form, a^b, finding the maximum digital sum.

A googol (10^(100)) is a massive number: one followed by one-hundred zeros; 100^(100) is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.

Considering natural numbers of the form, a^(b), where a, b < 100, what is the maximum digital sum?

tree_new_bee

在第一辑帖子的#259楼，曾经提到过， 现有的大数幂的运算效率比较低， 应该加以改进。
做56题这种需要大量密集的幂运算， 就能感觉到改进的必要性了。

下面是改进后的大数幂函数：

  function bigpower2(d1 varchar2, n number) return varchar2 is
    result varchar2(30000);
    tmp varchar2(30000);
    n2 varchar2(3000);
    j number;
  begin
    result := '1';

   n2:=n;
   while n2>=2 loop
     tmp:=d1;
      j := 2;
      while j<=n2 loop
        tmp:=bigmulti(tmp,tmp);            
        j := j*2;
      end loop;  
      result:=bigmulti(result, tmp);      
      n2:=n2-j/2;
    end loop;
    if n2=1 then result:=bigmulti(result, d1); end if;
    return result;
  end;

经过这样的改进， 计算1000次幂时， 大数乘法的次数可以从1000次降低到44次。
实际上，这个改进并不彻底， 中间有些步骤还是重复计算过。

依然以power(n, 7)为例：
这个算法是：
result=1
tmp1 = n*n
tmp2 = tmp1*tmp1
result = result*tmp2
tmp3 = n*n
result = result*tmp3
result = result * n

而理想的算法是
result=1
tmp1 = n*n
tmp2 = tmp1*tmp1
result = result*tmp2
result = result*tmp1
result = result * n

理想的算法算1000次幂只要14次乘法。
不过，理想的算法需要保留中间结果， 有点过于麻烦了。

[ 本帖最后由 tree_new_bee 于 2011-1-1 00:08 编辑 ]

tree_new_bee

下面就简单的用新的大数幂函数来解答：

with t as (select level n from dual connect by level<=100)
,t1 as (select /*+ MATERIALIZE */ distinct pkg_bignum.bigpower2(t1.n, t2.n) p
        from t t1, t t2)
,tsum as (select p, sum(substr(p,d,1)) sump
      from t1, (select rownum d from dual connect by rownum<=201) where d<=length(p) group by  p)
select max(sump) from tsum
/

MAX(SUMP)
----------
       972

Executed in 42.281 seconds

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

tree_new_bee

为了提升一些性能， 可以进行以下优化：
首先，1,10,100的幂的和， 都是1， 可以排除。
另外， 我们可以先找一个可能比较大的数， 比如99^100, 看看这个数的数字和：

with t1 as (select   pkg_bignum.bigpower2(99, 100) p from dual  )
,tsum as (select p, sum(substr(p,d,1)) sump from t1, (select rownum d from dual connect by rownum<=201) tlen where d<=length(p) group by  p)
select max(sump) from tsum
MAX(SUMP)
----------
       873

既然这个数是873， 那就意味着最大数一定>873.  而>873, 意味着那个幂至少有873/9=97位。 因此我们可以把幂的位数低于97的排除掉。

with t as (select level n from dual connect by level<=100)
,t1 as (select /*+ MATERIALIZE */ distinct pkg_bignum.bigpower2(t1.n, t2.n) p
        from t t1, t t2
        where t1.n not in (1, 10, 100) and t2.n*log(10,t1.n) >=97)
,tsum as (select p, sum(substr(p,d,1)) sump
      from t1, (select rownum d from dual connect by rownum<=201) where d<=length(p) group by  p)
select * from tsum
/

MAX(SUMP)
----------
       972

Executed in 30.719 seconds

优化的结果是省了很多循环量(从tsum的行数可以看出， 从 9271减少到3639)， 但没省多少时间。 这是因为无论大数幂运算，还是后面的对各位数字求和，都是当位数越多时计算越慢，耗时大的数都保留下来了， 节省的那些都是不需要太长时间计算的小数。

newkid

祝NB哥新年越来越NB!

〇〇

祝所有看帖的同学新年快乐

tree_new_bee

祝大家新年快乐！

用以下代码来表达对大家的新年祝愿(请在命令行方式下执行)：

set head off
clear screen
set pagesize 0
set feed off

with t as (select rownum rn, 'HAPPYNEWYEAR!' s from dual connect by rownum<=10000)
,tlen as (select rownum d from dual connect by rownum<=length('HAPPYNEWYEAR!'))
select dbms_random.string('L',70/(length(s)+1)-1)
||replace(sys_connect_by_path(substr(s, level,1)||dbms_random.string('L',70/(length(s)+1)-1), '/' ),'/', '')
from t,tlen where level = length(s) connect by rn=prior rn and d= prior d+1
/

[ 本帖最后由 tree_new_bee 于 2011-1-1 12:34 编辑 ]