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

goldensmile

厉害~~~~

〇〇

tree_new_bee 发表于 2010-12-17 13:08
换成PL/SQL, 能略强一些。

6年之后再来复习一遍.没想到sql比r语言好这么多
http://www.theresearchkitchen.com/archives/475

〇〇

tree_new_bee 发表于 2010-12-18 00:41
Q21 根据提示改写后的plsql代码:
declare
  sm number;

和我自己想的一样
http://www.ituring.com.cn/article/details/273524

〇〇

tree_new_bee 发表于 2010-12-15 20:36
由上一步的分析可以看出， 如果能把之前的路径经历过的数预先排除， 能节省大量的循环开销。
那么我们就分 ...
语言的速度差异太大了
#include <cstdio>
#define NN 1000000
int getsteps(long long n)
{
int i=1;
for(;n!=1;i++)
{
//printf("%-3d %lld\n",i,n);
n=(n %2 ==0)?(n/2):(n*3+1);
}
return i;
}
int main()
{
int maxstep=1;
int maxpos=1;
int n=1;
for(;n<NN;n++)
{
int step=getsteps(n);
if (step>maxstep){
maxstep=step;
maxpos=n;
}
}
printf("maxstep=%d ,at %d\n",maxstep,maxpos);
return 1;
}
D:\>a\timer p14

Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
maxstep=525 ,at 837799

Kernel Time  =     0.015 = 00:00:00.015 =   0%
User Time    =     1.497 = 00:00:01.497 =  84%
Process Time =     1.513 = 00:00:01.513 =  85%
Global Time  =     1.778 = 00:00:01.778 = 100%

〇〇

tree_new_bee 发表于 2010-12-15 20:36
由上一步的分析可以看出， 如果能把之前的路径经历过的数预先排除， 能节省大量的循环开销。
那么我们就分 ...

百度帖吧没有优化的递归
In[1]:= Block[{$RecursionLimit = 100000, f},
         f[n_] :=
         f[n] = If[n == 1, 1, 1 + f[If[EvenQ[n], n/2, 3*n + 1]]];
         Ordering[f /@ Range[10^6], -1]
         ] // Timing

Out[1]= {11.9965, {837799}}

〇〇

newkid 发表于 2010-12-16 05:23
我忽然想到溢出的那些其实可以不管，试一下：

declare

其实tnb的原版减少一些代码就能更快
create or replace procedure q14(NN int)
is
   type tpathtable is table of number index by PLS_INTEGER;
   pathtable tpathtable;
   maxchain    number := 0;
   maxchainnum number := 0;
   icopy       number;
   len         number;
begin
   for i in 1 .. NN loop
     if pathtable.exists(i) then
       null;
     else
       icopy := i;
       len   := 1;
       while icopy > 1 loop
         if icopy < i then --从小到大循环保证了数组一定有数
         --if icopy < NN and pathtable.exists(icopy) and
           -- pathtable(icopy) > 0 then
           len := len + pathtable(icopy) - 1;
           exit;
         else
           null; --if icopy < NN then pathtable(icopy) := 0; end if;
         end if;
         if bitand(icopy, 1) = 0 then
           icopy := icopy / 2;
         else
           icopy := icopy * 3 + 1;
         end if;
         len := len + 1;
       end loop;
     
       pathtable(i) := len;
     
       if len > maxchain then
         maxchain    := len;
         maxchainnum := i;
       end if;
     end if;
   end loop;
   dbms_output.put_line('number: ' || maxchainnum || ' chains: ' ||
                        maxchain);

/*  for i in 1 .. 100 loop
     dbms_output.put_line('number: ' || i || ' chains: ' || pathtable(i));
   end loop; */

end;
/
预存后面的大数确没有用
参见 http://www.ituring.com.cn/article/273547

〇〇

外层的存在性判断也没有用
create or replace procedure q14(NN int)
is
   type tpathtable is table of number index by PLS_INTEGER;
   pathtable tpathtable;
   maxchain    number := 0;
   maxchainnum number := 0;
   icopy       number;
   len         number;
begin
   for i in 1 .. NN loop
     if bitand(i, 1) = 0 then --偶数除以2比它小，一定已经有数
      len:=pathtable(i/2)+1;

     else
       icopy := i;
       len   := 1;
       while icopy > 1 loop
         if icopy < i then --从小到大循环保证了数组一定有数
         --if icopy < NN and pathtable.exists(icopy) and
           -- pathtable(icopy) > 0 then
           --dbms_output.put_line(icopy);
           len := len + pathtable(icopy) - 1;
           exit;
         else
           null; --if icopy < NN then pathtable(icopy) := 0; end if;
         end if;
         if bitand(icopy, 1) = 0 then
           icopy := icopy / 2;
         else
           icopy := icopy * 3 + 1;
         end if;
         len := len + 1;
       end loop;
       end if;
       pathtable(i) := len;

       if len > maxchain then
         maxchain    := len;
         maxchainnum := i;

     end if;
   end loop;
   dbms_output.put_line('number: ' || maxchainnum || ' chains: ' ||
                        maxchain);

/*  for i in 1 .. 100 loop
     dbms_output.put_line('number: ' || i || ' chains: ' || pathtable(i));
   end loop; */

end;
/

〇〇

q30注意到0~9的5次方末位等于原数，那么符合题目要求的数各位相加末位等于本数末位，因此在5位数中对这个条件先过滤，可以提高

〇〇

〇〇 发表于 2016-11-27 04:45
q30注意到0~9的5次方末位等于原数，那么符合题目要求的数各位相加末位等于本数末位，因此在5位数中对这个条 ...

with t as(select level+1e5 l from dual connect by level<4e4),
t1 as(select l-1e5 l from t where mod(substr(l,2,1)+substr(l,3,1)+substr(l,4,1)+substr(l,5,1)+substr(l,6,1),10)=0)
select sum(l||d) from t1,(select level-1 d,power(level-1,5)p5 from dual connect by level<=10)
where (l||d)>9 and (l||d)=(select sum(power(substr(l,level,1),5)) from dual connect by level<=length(l))+p5;

SUM(L||D)
----------
    443839

已用时间:  00: 00: 00.40

tnb版本
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

已用时间:  00: 00: 02.41

〇〇

Q30
在找到一个i=f(i)值后,i的变化如果赶不上f(i)的变化,那一定不可能再相等,利用这个原理，就不用逐个测试