Project Euler解题汇总(更新至309在1楼)

〇〇

原帖由 newkid 于 2010-11-6 06:05 发表

最近有些忙还顾不上看。你为什么用辗转相除法？

lcm(a b)=a*b/gcd(a b)啊
gcd用辗转相除法计算，另外你把签名换成书的封面阿，方法见PM

newkid

原帖由 〇〇 于 2010-11-6 06:12 发表

lcm(a b)=a*b/gcd(a b)啊
gcd用辗转相除法计算，另外你把签名换成书的封面阿，方法见PM

pm里面已经看不到控制代码，只有效果图。我随便设了个，以后再改字体吧。
49楼的两题，第一个用人肉方法很容易，第二个只需考虑1,3,7结尾8位数以下，应该不难。周末没时间搞这些了，下周再玩吧！

lastwinner

原帖由 〇〇 于 10-11-6 05:48 发表
其他题目
题目24 ：What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

题目简介 ：将数字0, 1, 2, 3, 4, 5, 6, 7, 8 ,9的所有排列按字典顺序排序，求排在第1,000,000位的那个数字。(注

意：从第一位记起)


问题41 ：What is the largest n-digit pandigital prime that exists?

题目简介 ：一个数称为pandigital，如果它是数字1，2，……，n的一个排列。比如2143就是一个4位的
  pandigital。

　　现在求所有pandigital中最大的那个素数。

24用表连接去做，不用connect by。人肉很简单：
9!=362880<1000000<10!=3628800
1000000/362880=2...274240
如果第一个排列可以以0开头，那么要求的数X必然以2开头；如果第一个排列必须以非0数字开头，那么要求的数X必然以3开头
8!=40320，27240/40320=6...32320
故第二个数的位序为7（这里所谓的第X个数的位序是M，指的是剩下来的N个数中（因为已经使用的数字要刨除掉），从小到大的第M个数，ps：M必然是不超过N的。）
如法泡制，第三个的位序数为7，第四个的位序为3，第五个的位序为6，第六个的位序为2，第七个的位序为3，第八个的位序为2，第九个的位序为2，第十个数为剩下的数

第一个数的位序实际上是3或4，我们先以3为例来解答
377362322x
则对应的实际数字是
2783915460

以第一个数的位序为4得到的结果如下：
3782915460

___________________________________________________________________
〇〇，转贴要转全啊！
A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

这样子我就没有第一位是否可以为0的疑问了……

____________________________________________________________________

至于Pandigital_number，太复杂了没看懂
http://en.wikipedia.org/wiki/Pandigital_number

[ 本帖最后由 lastwinner 于 2010-11-7 00:39 编辑 ]

lastwinner

原帖由 lastwinner 于 10-11-5 00:09 发表


3和5的最小公倍数为15
3、5、6、9、10、12、15，其和为60，个数为7
各自加上15的整数倍n，即可得下一组3和5的倍数，于是其和为
15×7×n＋60＝60＋105n

trunc(999/15)=66，mod(999/15)=9

故总和为
60*66+105*(65*(65+1)/2)+(3+5+6+9+990*4)
复制粘贴到计算器中得 233168

〇〇多算了个1000

其实还有更简单的办法……
所有3的倍数的和＋所有5的倍数的和－所有15的倍数的和即是

select 3*(n3*(n3+1)/2)+5*(n5*(n5+1)/2)-15*(n15*(n15+1)/2) sum_35 from
(select trunc(999/3) n3, trunc(999/5) n5, trunc(999/15) n15 from dual)
/

得 233168

lastwinner

原帖由 〇〇 于 10-11-3 15:24 发表
问题3:Find the largest prime factor of a composite number.
求600851475143的最大质因数。


SELECT x, s,res FROM DUAL MODEL    DIMENSION BY (1 AS x) MEASURES (600851475143 AS s,2 as res)  
RULES UPDATE ITERATE (4000) UNTIL res[1]=s[1]
(s[1] = case when mod(s[1],res[1])=0 then s[1]/res[1] else s[1] end,
res[1]=case when mod(s[1],res[1])0 then res[1]+1 else res[1] end );

         X                      S        RES
---------- ---------------------- ----------
         1        6857.0000000000       4002

我的方法
with t as (select 600851475143 n from dual),
t1 as (select pp from (select 1+rownum*2 pp, n from t connect by rownum<=sqrt(n)) where n/pp=trunc(n/pp))
select max(max(b.pp))  from t1 a, t1 b where a.pp<b.pp group by b.pp having sum(decode(b.pp/a.pp, trunc(b.pp/a.pp), 1, 0))=0

速度要慢点，结果6857

newkid

原帖由 〇〇 于 2010-11-6 06:12 发表

lcm(a b)=a*b/gcd(a b)啊
gcd用辗转相除法计算，另外你把签名换成书的封面阿，方法见PM

如果要用这个方法，就得有两层迭代，在MODEL里面用两个DIMENSION列可以做到。当然递归WITH也可以，等有空来搞一下。

〇〇

最小公倍数，plsql是容易的

SQL> set serverout on
SQL> declare
  2  a number;
  3  b number;
  4  tmp number;
  5  lcm number;
  6  gcd number;
  7  begin
  8  lcm:=1;
  9  for i in 2..7 loop
10  a:=i;
11  b:=lcm;
12  while a<>0 loop
13  tmp:=a;
14  a:=mod(b,a);
15  b:=tmp;
16  end loop;
17  gcd:=b;
18  lcm:=lcm*i/gcd;
19  dbms_output.put_line(i||','||a||','||b||','||lcm);
20  end loop;
21  end;
22  /
2,0,1,2
3,0,1,6
4,0,2,12
5,0,1,60
6,0,6,60
7,0,1,420

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.01
SQL> 9
  9* for i in 2..7 loop
SQL> c/7/20
  9* for i in 2..20 loop
SQL> /
2,0,1,2
3,0,1,6
4,0,2,12
5,0,1,60
6,0,6,60
7,0,1,420
8,0,4,840
9,0,3,2520
10,0,10,2520
11,0,1,27720
12,0,12,27720
13,0,1,360360
14,0,14,360360
15,0,15,360360
16,0,8,720720
17,0,1,12252240
18,0,18,12252240
19,0,1,232792560
20,0,20,232792560

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.01

〇〇

原帖由 newkid 于 2010-11-7 09:26 发表


如果要用这个方法，就得有两层迭代，在MODEL里面用两个DIMENSION列可以做到。当然递归WITH也可以，等有空来搞一下。

我就是不清楚 RULES UPDATE ITERATE能否做到

newkid

原帖由 〇〇 于 2010-11-7 09:52 发表

我就是不清楚 RULES UPDATE ITERATE能否做到

用不上ITERATE, 只能用两个DIMENSION, 像我做大数乘法那样。因为没有UNTIL所以不能提早推出里层循环。

newkid

原帖由 lastwinner 于 2010-11-6 19:00 发表


24用表连接去做，不用connect by。人肉很简单：
9!=362880

Pandigital_number应该就是1-N的连续自然数的排列吧？N<=9