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

tree_new_bee · 发表于 2010-12-13 13:37

Q8: Find the greatest product of five consecutive digits in the 1000-digit number.

这个太简单，不写了。

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

6666444 · 发表于 2010-12-13 13:39

不错不错，学习学习

jboracle1981 · 发表于 2010-12-13 14:33

强悍！

tree_new_bee · 发表于 2010-12-13 16:19

Q9:Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a^(2) + b^(2) = c^(2)

For example, 3^(2) + 4^(2) = 9 + 16 = 25 = 5^(2).

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

单就做这个题，也很easy:

SQL> with t as (select rownum n from dual connect by rownum<=1000/2)
  2  select ta.n a, tb.n b, 1000-ta.n-tb.n c, ta.n * tb.n * (1000-ta.n-tb.n) prod from t ta, t tb
  3  where ta.n<tb.n and
  4  ta.n* ta.n + tb.n*tb.n = (1000-ta.n - tb.n)*(1000-ta.n - tb.n)
  5  /

      A       B       C    PROD
---------- ---------- ---------- ----------
   200       375       425 31875000

Executed in 0.297 seconds

不过，毕竟这是个O(n2)的算法，推广到大数以后，就是个问题了。
Euler的文档中有降低难度的算法，不过看不明白。

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

tree_new_bee · 发表于 2010-12-13 16:27

可以略微优化一点的地方是：因为a<b<c , 所以a<1000/3, c>1000/3
c>1000/3 => a+b < 2000/3 => b< 2000/3-a
不过，因为本身很快，所以改善不会太明显。

with t as (select rownum n from dual connect by rownum<=1000/2)
select ta.n a, tb.n b, 1000-ta.n-tb.n c, ta.n * tb.n * (1000-ta.n-tb.n) prod from t ta, t tb
where ta.n<1000/3 and tb.n < 2000/3-ta.n and ta.n<tb.n and
ta.n* ta.n + tb.n*tb.n = (1000-ta.n - tb.n)*(1000-ta.n - tb.n)

Executed in 0.219 seconds

tree_new_bee · 发表于 2010-12-13 17:43

Q10:Find the sum of all the primes below two million.

直接利用Q7的成果就是了。

public static double findsum(double d)
{
  long i=1;
  double sum;

  if(d==1) return 0;  if(d==2) return 2;
  if(d<=4) return 5;  if(d<=6) return 10;

  sum=10; // sum of 2+3+5
  while (i<(d-1)/6)
  {
if (isprim(i*6+1)==0) sum+= i*6+1;
if (i*6+5 > d) return sum;
if (isprim(i*6+5)==0) sum+= i*6+5;
i++;
  }
  return sum;
}

SQL> select pkg_prim2.jfindsum(2000000) from dual;

PKG_PRIM2.JFINDSUM(2000000)
---------------------------
            142913828922

Executed in 14.078 seconds

用Java都要14秒， PLSQL就懒得再去试了。

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

tree_new_bee · 发表于 2010-12-13 19:41

找连续数范围内所有质数，还是用Eratosthenes筛法效率最好。
根据euler文档中的算法改写：

public static double seivesum(double d)
{
int i,j;
boolean n[];
int m = (int)d+1;
n = new boolean[m] ;
double sum = 0;
for (i=1; i<m; i++ ) n[i]=(i % 2==1);
n[0] = false; n[1] = false; n[2] = true;
j = 3;
while (j<=java.lang.Math.sqrt(d))
{
if (n[j] )
for (i=j*j; i<m; i+=j) n[i]=false;
j+=2;
}
for (i=2; i<m;i++ ) if (n[i]) sum+=i;
return sum;
}
SQL> select pkg_prim2.jseivesum(2000000) from dual;
PKG_PRIM2.JSEIVESUM(2000000)
----------------------------
142913828922
Executed in 0.484 seconds

复制代码

效果很惊人！

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

newkid · 发表于 2010-12-13 22:57

可怜OO的秘密武器，就这样被维基解密了

关于质数表，以前OO也有贴过，确实是筛选法最快：
http://www.itpub.net/viewthread.php?tid=1244925

newkid · 发表于 2010-12-13 23:14

回文数可以用一下这个reverse函数：

with t as (select rownum+100 n from dual connect by rownum<=900)
select max(t1.n*t2.n) from t t1, t t2
--select t1.n, t2.n,t1.n*t2.n from t t1, t t2
where to_char(t1.n*t2.n) = reverse(to_char(t1.n*t2.n))
and t1.n<t2.n;

tree_new_bee · 发表于 2010-12-14 01:08

原帖由 newkid 于 2010-12-13 23:14 发表
回文数可以用一下这个reverse函数：

哈，忘了还有这么一个宝贝函数了。

这个reverse函数做函数索引的时候很有用的。