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

tree_new_bee

16. What is the sum of the digits of the number 2^1000?

这个问题在帖子： 求2^1000的各位数字之和 里，已经讨论的很充分了。 不再详细讨论。

用递归with计算大数相乘，在http://www.itpub.net/viewthread. ... ;page=1#pid16957717里已经有了。

这里只贴出我的大数相乘的PLSQL，并把相应的幂和阶乘运算放到一个Package中。
这里用得到幂， 后面的题目会用到阶乘。

create or replace package body pkg_bignum is

  function bigmulti(d1 varchar2, d2 varchar2) return varchar2 is
    Result varchar2(4000) := '';
    type t_numlist is table of number index by PLS_INTEGER;
    numlist t_numlist;
    i       number;
    j       number;
    lastm   number;
    tmp     number;
  begin
  
    for i in 1 .. length(d1) + length(d2) loop
      numlist(i) := 0;
    end loop;
  
    for i in 1 .. length(d1) loop
      for j in 1 .. length(d2) loop
        numlist(i + j - 1) := numlist(i + j - 1) +
                              substr(d1, -i, 1) * substr(d2, -j, 1);
      end loop;
    end loop;
  
    lastm := 0;
    for i in 1 .. length(d1) + length(d2) loop
      tmp := mod(numlist(i) + lastm, 10);
      lastm := trunc((numlist(i) + lastm) / 10);
      numlist(i) := tmp;
      result := numlist(i) || result;
    end loop;
  
    return(ltrim(Result, '0'));
  end;

  function bigpower(d1 varchar2, n number) return varchar2 is
    result varchar2(4000);
  begin
    result := '1';
    for i in 1 .. n loop
      result := bigmulti(result, d1);
    end loop;
    return result;
  end;

  function bigfact(d1 varchar2) return varchar2 is
    result varchar2(4000);
  begin
    result := '1';
    for i in 2 .. d1 loop
      result := bigmulti(result, i);
    end loop;
    return result;
  end;

end pkg_bignum;



测试，无论(2, 1000),  (2^10, 100) 还是(2^100, 10)都很快。
SQL> with t as (select /*+ RESULT_CACHE  */ pkg_bignum.bigpower(power(2, 100), 10) 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;

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

Executed in 0.079 seconds
SQL> with t as (select /*+ RESULT_CACHE  */ pkg_bignum.bigpower(power(2, 10), 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;

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

Executed in 0.031 seconds
SQL> with t as (select /*+ RESULT_CACHE  */ pkg_bignum.bigpower( 2, 1000) 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;

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

Executed in 0.016 seconds

SQL>

tree_new_bee

Q17: How many letters would be needed to write all the numbers in words from 1 to 1000?

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?


这个没难度， 纯粹是体力活，也是细心活。


with
  ta as ( select '03354435543668877988' na, '0066555766' nb from dual) -- na:0-19 nb: 00-90
, t as (select rownum num from dual connect by rownum<1000)
, t1 as (select num, 0 + case when num/100 >=1 then to_number(substr(na,num/100+1,1)) + 7 else 0 end  -- 7: hundred
+ case when num/100>=1 and mod(num,100)>0 then 3 else 0 end  -- 3: x handred and y
+ case when mod(num,100) < 20 then to_number(substr(na,mod(num,100)+1,1)) -- 0-19
       else to_number(substr(nb, mod(num,100)/10+1,1)) + to_number(substr(na,mod(num,10)+1,1)) end pron -- 20-99
         from t, ta  )
select sum(pron)+ 11 from t1  -- 11 for 1000: one thousand

SUM(PRON)+11
------------
       21124

SQL>

〇〇

一个更oracle的写法，可惜结果好象不对
SQL> select sum(n) from(select length(trim(to_char(add_months(date'0001-1-1',12*(level-1)),'Year')))n from dual connect by level<=1000);

    SUM(N)
----------
     14483

SQL> select n from(select to_char(add_months(date'0901-1-1',12*(level-1)),'Year')n from dual connect by level<=1000)where rownum<=20;

N
------------------------------------------
Nine Hundred One
Nine Hundred Two
Nine Hundred Three
Nine Hundred Four
Nine Hundred Five
Nine Hundred Six
Nine Hundred Seven
Nine Hundred Eight
Nine Hundred Nine
Nine Ten
Nine Eleven
Nine Twelve
Nine Thirteen
Nine Fourteen
Nine Fifteen
Nine Sixteen
Nine Seventeen
Nine Eighteen
Nine Nineteen
Nine Twenty

tree_new_bee

原帖由 〇〇 于 2010-12-16 21:27 发表
一个更oracle的写法，可惜结果好象不对
SQL> select sum(n) from(select length(trim(to_char(add_months(date'0001-1-1',12*(level-1)),'Year')))n from dual connect by level select n from(select to_char(add_months(date'0901-1-1',12*(level-1)),'Year')n from dual connect by level

看你的结果的第一行就知道不对。
901 读作 nine hundred and one,  对year的to_char漏了and了。

不过用日期这个主意不错。

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

yaohaiyang

学习

tree_new_bee

想在你那个上面加工加工， 可是好像不止那一个地方， 对年份的拼写，很多地方都与普通的读法不同。

比如：
609        609        Six Hundred Nine
610        610        Six Ten
就是当后面的不是单位数时， 就分两节读， 不再加hundred了。
hundred 加个and好加， 这个Six Ten不好处理。

tree_new_bee

土洋结合， 百位前用我的笨办法，十位以内的数字用你的办法取。 这样除了Hundred和thousande这两个词外，省了硬编码其它数字了。

with ta as  (select level d, replace(to_char(add_months(date'0001-1-1',12*(level-1)),'Year'),'-', ' ') str from dual connect by rownum<=99)
, t as (select rownum num from dual connect by rownum<1000)
, t1 as (select num, case when num/100 >=1 then (select str || ' Hundred ' from ta where d=floor(num/100))  else ' ' end  -- 7: hundred
  || case when num/100>=1 and mod(num,100)>0 then ' AND ' else '' end  -- 3: x handred and y
  || (select str  from ta where d=mod(num,100)) pron
           from t )
select sum(length(replace(pron,' ', '')))+11 from t1  

SUM(LENGTH(REPLACE(PRON,'','')
------------------------------
                         21124

SQL>

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

newkid

这个也是没有AND的：
SELECT  to_char(to_timestamp(LPAD(LEVEL,9,'0'),'FF9'),'FFSP') FROM DUAL WHERE LEVEL>980 CONNECT BY LEVEL<=1000;

TO_CHAR(TO_TIMESTAMP(LPAD(LEVEL,9,'0'),'FF9'),'FFSP')
----------------------------------------------------------------------
NINE HUNDRED EIGHTY-ONE
NINE HUNDRED EIGHTY-TWO
NINE HUNDRED EIGHTY-THREE
NINE HUNDRED EIGHTY-FOUR
NINE HUNDRED EIGHTY-FIVE
NINE HUNDRED EIGHTY-SIX
NINE HUNDRED EIGHTY-SEVEN
NINE HUNDRED EIGHTY-EIGHT
NINE HUNDRED EIGHTY-NINE
NINE HUNDRED NINETY
NINE HUNDRED NINETY-ONE
NINE HUNDRED NINETY-TWO
NINE HUNDRED NINETY-THREE
NINE HUNDRED NINETY-FOUR
NINE HUNDRED NINETY-FIVE
NINE HUNDRED NINETY-SIX
NINE HUNDRED NINETY-SEVEN
NINE HUNDRED NINETY-EIGHT
NINE HUNDRED NINETY-NINE
ONE THOUSAND

tree_new_bee

上面这个容易加工一点， 只要用like '%HUNDRED__% 替换为HUNDRED AND即可。

newkid

那个走方格的题目，我以前在这里见过，费了半天劲才搜索出来：
http://www.itpub.net/viewthread. ... p;extra=&page=1