project euler 1~50
前一段时间看到有人在写project euler上的题目,然后我看了看题目,还好,权当练习python了,
然后就花了一周做了些题目。

话说python的整数太好用了,如果用c++写高精不知得花多少时间(c++有一个实现效率极高的大
整数库gmp,不过编程比赛肯定是不能用的了,虽然python也不能用- -|| )java又慢的要死。
MIT都不教LISP改教python了,果然有道理,python的生产力太高了,不需要手动管理内存果然很强大。

下面是我用python写的线性筛法,会经常用到,具体原理请google之

pn = 1000000
primes = []
is_prime = [True for i in range(pn)]
is_prime[0] = False
is_prime[1] = False
for i in range(2, pn):
    if is_prime[i]: primes.append(i)
    for j in primes:
        if i * j >= pn: break
        is_prime[i * j] = False
        if i % j == 0: break

简单思路
1:brute-force
2:算一下 4000000 以下偶fibonacci数的和
3:在[0,sqrt(600851475143) + 1] 范围内用素数试除以下即可
4:brute-force
5:用gcd算lcm
6:brute-force
7:筛法求素数
8:brute-force
9:brute-force
10:筛法求素数
11:brute-force, 注意到只需要计算四个对角线方向中的两个即可
12:brute-force, 只需要试除道sqrt(n) + 1,完全平方数要注意平方根不要计算两次
13:python程序:
    print sum([int(s) for s in file("in", "r").read().strip("\n").split("\n")])
14:brute-force
15:动态规划
dp[0][0] = 1
for i in range(20 + 1):
    for j in range(20 + 1):
        if (i - 1 >= 0): dp[i][j] += dp[i-1][j]
        if (j - 1 >= 0): dp[i][j] += dp[i][j-1]
16:print sum(ord(i) - ord("0") for i in str(2 ** 1000))
17:brute-force,不知道英文数字怎么表示就查查wiki吧
18:动态规划, pascal/杨辉三角
19:brute-force,算算二十世纪有多少个月初是周日
20:brute-force, python很好很强大
21:平衡二叉树做映射,当然c++有map,python有dict,把数组开大点也行..
22:sort
23:brute-force
24:全排列的生成,可以搜,可以查查O(n)的算法,当然有现成的库
    c++:
      next_permutation
    python:
    from itertools import permutations
    list(permutations[0,1,2,3,4])
25:brute-force
26:一个分数1/b,用小学除法实现,当出现相同的x % b时,和上一次相同模值之间的是递归的,
    也就是循环节最长为b
27:注意到n² + an + b,在n==0时,b必须是素数,利用这个性质减小循环量,之后暴力
28:brute-force,纯模拟
29:brute-force
30:brute-force
31:动态规划
    if dp[j] > 0 and j + i <= 200:
        dp[j + i] += dp[j]
32:注意到乘法的性质a x b = c, len(c) >=
    max(len(a),len(b)),先算出可能的长度组合,然后搜
33:模拟,注意最后的结果是将所有可能的分数乘起来再化简得到的分母
34:brute-force
35:模拟一下数字循环
36:进制的转换,注意到需要是回文,所以整数分解得到的数组不用取反
37:给大点素数最大值,算出11个为止
38:brute-force
39:注意到对长度l,每条边的长度都不能超过 l / 2
40:算一下每个整数的长度,模拟扫描
41:注意到sum(1,2...8) = 36,能被3整除,也就是不论怎样组合都是三的倍数,所以肯定不是素数
    同理有sum(1,2...9) = 45,所以计算量减小道10 ^ 7
42:brute-force
43:从前往后推,前几位是可以循环找出,后面的每一位都可以由模的性质从前两位导出
   从后往前推,后三位是17的倍数,前7位全排列即可
44:brute-force
45:用三角数反推另外两个数是否存在一个n满足产生式
46:筛法求素数,然后判断一下性质存在与否
47:筛法求素数,用sqrt(n) + 1之下的素数试除
48:brute-force,python很好很强大
49:把所有素数的全排列也是素数的找出来,在这些数中用三重循环判断。注意到所有全排列不需要计算两次
50:限定一个连续素数的个数,然后窗口式的扫描

作者: schindlerlee 发表于 2011-01-29 18:11 原文链接