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

tree_new_bee

Q74 Determine the number of factorial chains that contain exactly sixty non-repeating terms.

The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:

1! + 4! + 5! = 1 + 24 + 120 = 145

Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.

How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?

tree_new_bee

这道题， 开始我理解错题目了， 以为只要找到一个长度为60的。
很轻松，就找到了一个1479

填答案发现错了， 才知道是找所有长度为60的链。

继续沿用之前的题目中有关保存路径的方法。

create or replace procedure P_Q74 is
  maxnum integer:=1000000;
  i integer;
  icopy integer;
  pathlen integer;
  tmp integer;
  pathcopy varchar2(4000);
  type t_numtable is table of number index by pls_integer;
  type tstringtable is table of varchar2(4000) index by pls_integer;

  fact t_numtable;
  path tstringtable;
  factsum integer;
  sm integer := 0;
begin
  fact(0):=1;
  for i in 1..9 loop
    fact(i):= i*fact(i-1);
  end loop;
  
  for i in 1.. maxnum loop
    if path.exists(i) then goto CONTINUE; end if;
     path(i):= '/'|| i ||'/';
     icopy :=i;
     while true loop
       factsum:= 0;
       for j in 1..length(icopy) loop
         factsum:= factsum + fact(substr(icopy,j,1));
       end loop;
       if instr(path(i), '/'|| factsum ||'/') > 0 then
         exit;
       end if;
       if path.exists(factsum) then
         path(i) := path(i) || substr(path(factsum),2);
         exit;
       end if;
       path(i) := path(i) || factsum || '/';
       icopy := factsum;
     end loop;   

     pathlen := length(translate(path(i), '/'||path(i) ,'/'))-1;
     if pathlen = 60 then
       dbms_output.put_line('i: ' || i || ' len: ' || pathlen || ' path:' || path(i));
       sm:=sm+1;
       --return;
     end if;
     pathcopy := substr(path(i),instr(path(i),'/',2,1));
     for k in 1.. pathlen-1 loop
       tmp := substr(pathcopy, 2,instr(pathcopy, '/',2)-2);
       if tmp is null then exit; end if;
       if tmp = factsum then exit; end if;
       path(tmp):=pathcopy;
       pathcopy := substr(pathcopy, instr(pathcopy, '/',2,1));
     end loop;
   <<CONTINUE>>
     null;
  end loop;

   dbms_output.put_line('Count:' || sm);   
  
end P_Q74;

SQL> exec p_q74

i: 1479 len: 60 path:/1479/367945/368790/408967/408985/443665/1614/746/5784/45504/289/403202/36/726/5762/5882/80762/46083/41071/5067/5881/80761/46082/41067/5786/46200/748/45384/40494/362953/363734/5802/40443/79/367920/368649/404670/5810/40442/75/5160/842/40346/775/10200/6/720/5043/151/122/5/120/4/24/26/722/5044/169/363601/1454/
i: 1497 len: 60 path:/1497/367945/368790/408967/408985/443665/1614/746/5784/45504/289/403202/36/726/5762/5882/80762/46083/41071/5067/5881/80761/46082/41067/5786/46200/748/45384/40494/362953/363734/5802/40443/79/367920/368649/404670/5810/40442/75/5160/842/40346/775/10200/6/720/5043/151/122/5/120/4/24/26/722/5044/169/363601/1454/
。。。。。

Count:402

PL/SQL procedure successfully completed

Executed in 86.093 seconds

一看结果，就知道什么地方该优化了：
一个数的所有排列， 其乘积和必然相等， 因此只要求其中一个就够了。

有意思的是： 如果观察所有数的路径就能发现： 除了极少数的几个数，如1,2,10, 以及题目中提到的145,69,78等之外， 其它绝大多数的路径都是以1454结尾。

[ 本帖最后由 tree_new_bee 于 2011-1-11 22:37 编辑 ]

newkid

干吗用goto?
11g里面直接写continue.

tree_new_bee

原帖由 newkid 于 2011-1-12 04:43 发表
干吗用goto?
11g里面直接写continue.

哦， 这个还真不知道。

tree_new_bee

原帖由 tree_new_bee 于 2011-1-11 22:34 发表
一看结果，就知道什么地方该优化了：
一个数的所有排列， 其乘积和必然相等， 因此只要求其中一个就够了。

按上面说的改写了一下， 只取数字排列中从小到大的排列。

newkid给的那个给数字排序的方法发挥大用场了，好几个题目中都用到了。

create or replace procedure P_Q74B is
  maxnum integer:=1000000;
  icopy varchar2(100);
  pathlen integer;
  tmp varchar2(100);
  pathcopy varchar2(4000);
  type t_numtable is table of number index by pls_integer;
  type tstringtable is table of varchar2(4000) index by varchar2(100);

  fact t_numtable;
  path tstringtable;
  factsum integer;
  factsumorder varchar2(100);
  sm integer := 0;
  function numorder(n integer) return varchar2 is
  begin
    return TRANSLATE(n,'0123456789','0')||
       TRANSLATE(n,'1023456789','1')||
       TRANSLATE(n,'2013456789','2')||
       TRANSLATE(n,'3012456789','3')||
       TRANSLATE(n,'4012356789','4')||
       TRANSLATE(n,'5012346789','5')||
       TRANSLATE(n,'6012345789','6')||
       TRANSLATE(n,'7012345689','7')||
       TRANSLATE(n,'8012345679','8')||
       TRANSLATE(n,'9012345678','9');
  end;
begin
  fact(0):=1;
  for i in 1..9 loop
    fact(i):= i*fact(i-1);
  end loop;

  for rc in (with t as (select rownum n,
         TRANSLATE(rownum,'0123456789','0')||
         TRANSLATE(rownum,'1023456789','1')||
         TRANSLATE(rownum,'2013456789','2')||
         TRANSLATE(rownum,'3012456789','3')||
         TRANSLATE(rownum,'4012356789','4')||
         TRANSLATE(rownum,'5012346789','5')||
         TRANSLATE(rownum,'6012345789','6')||
         TRANSLATE(rownum,'7012345689','7')||
         TRANSLATE(rownum,'8012345679','8')||
         TRANSLATE(rownum,'9012345678','9') norder
         from dual connect by rownum<=maxnum)
         select norder, count(*) cnt from t group by norder order by to_number(norder))  
  loop

    if path.exists(rc.norder) then goto CONTINUE; end if;
     path(rc.norder):= '/'|| rc.norder ||'/';
     icopy :=rc.norder;
     while true loop
       factsum:= 0;
       for j in 1..length(icopy) loop
         factsum:= factsum + fact(substr(icopy,j,1));
       end loop;
       factsumorder:=numorder(factsum);
       if instr(path(rc.norder), '/'|| factsumorder ||'/') > 0 then
         exit;
       end if;
       if path.exists(factsumorder) then
         path(rc.norder) := path(rc.norder) || substr(path(factsumorder),2);
         exit;
       end if;
       path(rc.norder) := path(rc.norder) || factsumorder || '/';
       icopy := factsumorder;
     end loop;

     pathlen := length(translate(path(rc.norder), '/'||path(rc.norder) ,'/'))-1;
     if pathlen = 60 then
       dbms_output.put_line('i: ' || rc.norder || ' cnt:' || rc.cnt || ' len: ' || pathlen || ' path:' || path(rc.norder));
       sm:=sm+rc.cnt;
       --return;
     end if;
     pathcopy := substr(path(rc.norder),instr(path(rc.norder),'/',2,1));
     for k in 1.. pathlen-1 loop
       tmp := substr(pathcopy, 2,instr(pathcopy, '/',2)-2);
       if tmp is null then exit; end if;
       if tmp = factsumorder then exit; end if;
       path(tmp):=pathcopy;
       pathcopy := substr(pathcopy, instr(pathcopy, '/',2,1));
     end loop;
   <<CONTINUE>>
     null;
  end loop;

   dbms_output.put_line('Count:' || sm);
end P_Q74B;

i: 0479 cnt:18 len: 60 path:/0479/345679/036789/046789/045889/344566/1146/467/4578/04455/289/002234/36/267/2567/2588/02678/03468/01147/0567/1588/01678/02468/01467/5678/00246/478/34458/04449/233569/333467/0258/03444/79/023679/346689/004467/0158/02444/57/0156/248/03446/577/00012/6/027/0345/115/122/5/012/4/24/26/227/0445/169/013366/1445/
i: 1479 cnt:24 len: 60 path:/1479/345679/036789/046789/045889/344566/1146/467/4578/04455/289/002234/36/267/2567/2588/02678/03468/01147/0567/1588/01678/02468/01467/5678/00246/478/34458/04449/233569/333467/0258/03444/79/023679/346689/004467/0158/02444/57/0156/248/03446/577/00012/6/027/0345/115/122/5/012/4/24/26/227/0445/169/013366/1445/
i: 223479 cnt:360 len: 60 path:/223479/345679/036789/046789/045889/344566/1146/467/4578/04455/289/002234/36/267/2567/2588/02678/03468/01147/0567/1588/01678/02468/01467/5678/00246/478/34458/04449/233569/333467/0258/03444/79/023679/346689/004467/0158/02444/57/0156/248/03446/577/00012/6/027/0345/115/122/5/012/4/24/26/227/0445/169/013366/1445/
Count:402

PL/SQL procedure successfully completed

Executed in 28.422 seconds

SQL>


快多了。 实际上28秒里有20多秒都花在了那个SQL语句上。
那个语句改成拼数字串的方法应该会高效的多， 可是涉及到带前导0，以及带重复数字的排列的数目，好烦， 先扔那里吧。

[ 本帖最后由 tree_new_bee 于 2011-1-13 15:42 编辑 ]

tree_new_bee

Q75 Find the number of different lengths of wire that can form a right angle triangle in only one way.

It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.

12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)

In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.

120 cm: (30,40,50), (20,48,52), (24,45,51)

Given that L is the length of the wire, for how many values of L ≤ 1,500,000 can exactly one integer sided right angle triangle be formed?

就是说一些数只能拆成唯一的一组勾股数的和， 找出这些数的数目。


这个帖子又很长了， 做完这道题开新贴。

[ 本帖最后由 tree_new_bee 于 2011-1-13 21:37 编辑 ]

tree_new_bee

题目看起来很简单， 要是小一点的上界， 怎么都好做。
但1500000实在是个恐怖的数字。

用wiki里这个公式：
    a = m2 − n2,
    b = 2mn,
    c = m2 + n2

其中m,n互质， 可以产生素勾股数
要产生所有勾股数， 只要在上面的基础上乘上自然数k就行。
问题是， 前一步的素勾股数可以很快产生， 所有的素勾股数*k,这一步也很慢。

newkid

造出所有素的a+b+c，用它们作筛子，被一个以上筛过的L就不合格。

tree_new_bee

原帖由 newkid 于 2011-1-13 23:21 发表
造出所有素的a+b+c，用它们作筛子，被一个以上筛过的L就不合格。

造素勾股数，大概是 sqrt(n/2) * sqrt(n/2)=n/2的复杂度, 筛的过程要循环n/3次， 总共要n^2/6，仍然是O(n^2)的复杂度。

估计还是要有什么数学方法， 直接找出重复L的什么规律来。

zhangweicai74

最近没见奥数哥光临了。