欧拉计划Python解法（第11题-第15题）

欧拉计划提供了几百道由易到难的数学问题，你可以用任何办法去解决它，当然主要还得靠编程，但编程语言不限，已经有Java、C#、Python、Lisp、Haskell等各种解法。

“欧拉计划”的官网是：https://projecteuler.net，你可以在这个网站上注册一个账号，当你提交了正确答案后，可以在里面的论坛里进行讨论，借鉴别人的思路和代码。

如果你的英文不过关，有人已经将几乎所有的题目翻译成了中文，网址：http://pe-cn.github.io。

强烈建议你在看答案之前，自己先尝试编程挑战一下，可以复习一下学到的Python的语法。

第11题

在一个矩阵里，找到一条线上、相邻的、乘积最大的4个数，求积。

用暴力全遍历直接求解即可。

arr = [[ 8,  2, 22, 97, 38, 15,  0, 40,  0, 75,  4,  5,  7, 78, 52, 12, 50, 77, 91,  8],
       [49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48,  4, 56, 62,  0],
       [81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30,  3, 49, 13, 36, 65],
       [52, 70, 95, 23,  4, 60, 11, 42, 69, 24, 68, 56,  1, 32, 56, 71, 37,  2, 36, 91],
       [22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80],
       [24, 47, 32, 60, 99,  3, 45,  2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50],
       [32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70],
       [67, 26, 20, 68,  2, 62, 12, 20, 95, 63, 94, 39, 63,  8, 40, 91, 66, 49, 94, 21],
       [24, 55, 58,  5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72],
       [21, 36, 23,  9, 75,  0, 76, 44, 20, 45, 35, 14,  0, 61, 33, 97, 34, 31, 33, 95],
       [78, 17, 53, 28, 22, 75, 31, 67, 15, 94,  3, 80,  4, 62, 16, 14,  9, 53, 56, 92],
       [16, 39,  5, 42, 96, 35, 31, 47, 55, 58, 88, 24,  0, 17, 54, 24, 36, 29, 85, 57],
       [86, 56,  0, 48, 35, 71, 89,  7,  5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58],
       [19, 80, 81, 68,  5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77,  4, 89, 55, 40],
       [ 4, 52,  8, 83, 97, 35, 99, 16,  7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66],
       [88, 36, 68, 87, 57, 62, 20, 72,  3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69],
       [ 4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18,  8, 46, 29, 32, 40, 62, 76, 36],
       [20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74,  4, 36, 16],
       [20, 73, 35, 29, 78, 31, 90,  1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57,  5, 54],
       [ 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52,  1, 89, 19, 67, 48]
]


def prod4(i, j, inc_i, inc_j):
    prod = arr[i][j]
    for _ in range(3):
        i += inc_i
        j += inc_j
        if i < 0 or j < 0 or i >= 20 or j >=20:
            return 0
        prod *= arr[i][j]
    return prod


max_prod = 0
for i in range(20):
    for j in range(20):
        for (inc_i, inc_j) in [(1, 0), (0, 1), (1, 1), (1, -1)]:
            p = prod4(i, j, inc_i, inc_j)
            if p > max_prod:
                #print(i, j, inc_i, inc_j)
                max_prod = p

print(max_prod)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

第12题 高度可约的三角形数

三角形数数列是通过逐个加上自然数来生成的。例如，第7个三角形数是 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28。三角形数数列的前十项分别是：

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
让我们列举出前七个三角形数的所有约数：

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
我们可以看出，28是第一个拥有超过5个约数的三角形数。

第一个拥有超过500个约数的三角形数是多少？

先用笨办法把因子求出来，在找500个因子的三角形数的时候则非常非常慢。

def tri_number(i):
    return i * (i + 1) // 2


def factors(num):
    fac = filter(lambda x: num % x == 0, range(1, num+1))
    return list(fac)


assert factors(1) == [1]
assert factors(3) == [1, 3]
assert factors(6) == [1, 2, 3, 6]
assert factors(10) == [1, 2, 5, 10]
assert factors(28) == [1, 2, 4, 7, 14, 28]


def tri_num_have_factors(factors_num):
    i = 1
    while True:
        tri_num = tri_number(i)
        facs = factors(tri_num)
        if len(facs) > factors_num:
            return tri_num
        i += 1


print(tri_num_have_factors(5))
print(tri_num_have_factors(50))
print(tri_num_have_factors(500))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

优化一下算法，可以发现因子只需计算前一半就行，另外一半因子可以直接用除法计算出来。

def tri_number(i):
    return i * (i + 1) // 2


def half_factors(num):
    s = int(num ** 0.5)
    fac = filter(lambda x: num % x == 0, range(1, s+1))
    return list(fac)


def factors(num):
    if num == 1:
        return [1]
    first_half = half_factors(num)
    second_half = [num // x for x in reversed(first_half)]
    return first_half + second_half


assert factors(1) == [1]
assert factors(3) == [1, 3]
assert factors(6) == [1, 2, 3, 6]
assert factors(10) == [1, 2, 5, 10]
assert factors(28) == [1, 2, 4, 7, 14, 28]


def tri_num_have_factors(factors_num):
    i = 1
    while True:
        tri_num = tri_number(i)
        facs = factors(tri_num)
        if len(facs) > factors_num:
            return tri_num
        i += 1


print(tri_num_have_factors(5))
print(tri_num_have_factors(50))
print(tri_num_have_factors(500))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

利用itertools可以改写while True那段循环：

import itertools

def tri_num_have_factors(factors_num):
    for i in itertools.count(1):
        tri_num = tri_number(i)
        facs = half_factors(tri_num)
        if len(facs) * 2 > factors_num:
            return tri_num
1
2
3
4
5
6
7
8

还可以改成这样：

import itertools

def tri_num_have_factors(factors_num):
    tri_numbers = map(tri_number, itertools.count(1))
    seq = itertools.dropwhile(lambda n: len(half_factors(n)) * 2 <= factors_num, tri_numbers)
    return next(seq)
1
2
3
4
5
6

还可以变态地弄成一行：

import itertools
result = next(itertools.dropwhile(lambda n: len(list(filter(lambda x: n % x == 0, range(1, int(n ** 0.5)+1)))) * 2 <= 500, map(lambda i: i * (i + 1) // 2, itertools.count(1))))
print(result)
1
2
3

对数学感兴趣的朋友，还利用因子的数学性质进一步优化，提高上千倍不止，这里不展开讨论了。

第13题

有100个长达50位的大整数，求和，只取前10位数字。

numbers = [
    37107287533902102798797998220837590246510135740250,
    46376937677490009712648124896970078050417018260538,
    74324986199524741059474233309513058123726617309629,
    91942213363574161572522430563301811072406154908250,
    23067588207539346171171980310421047513778063246676,
    89261670696623633820136378418383684178734361726757,
    28112879812849979408065481931592621691275889832738,
    44274228917432520321923589422876796487670272189318,
    47451445736001306439091167216856844588711603153276,
    70386486105843025439939619828917593665686757934951,
    62176457141856560629502157223196586755079324193331,
    64906352462741904929101432445813822663347944758178,
    92575867718337217661963751590579239728245598838407,
    58203565325359399008402633568948830189458628227828,
    80181199384826282014278194139940567587151170094390,
    35398664372827112653829987240784473053190104293586,
    86515506006295864861532075273371959191420517255829,
    71693888707715466499115593487603532921714970056938,
    54370070576826684624621495650076471787294438377604,
    53282654108756828443191190634694037855217779295145,
    36123272525000296071075082563815656710885258350721,
    45876576172410976447339110607218265236877223636045,
    17423706905851860660448207621209813287860733969412,
    81142660418086830619328460811191061556940512689692,
    51934325451728388641918047049293215058642563049483,
    62467221648435076201727918039944693004732956340691,
    15732444386908125794514089057706229429197107928209,
    55037687525678773091862540744969844508330393682126,
    18336384825330154686196124348767681297534375946515,
    80386287592878490201521685554828717201219257766954,
    78182833757993103614740356856449095527097864797581,
    16726320100436897842553539920931837441497806860984,
    48403098129077791799088218795327364475675590848030,
    87086987551392711854517078544161852424320693150332,
    59959406895756536782107074926966537676326235447210,
    69793950679652694742597709739166693763042633987085,
    41052684708299085211399427365734116182760315001271,
    65378607361501080857009149939512557028198746004375,
    35829035317434717326932123578154982629742552737307,
    94953759765105305946966067683156574377167401875275,
    88902802571733229619176668713819931811048770190271,
    25267680276078003013678680992525463401061632866526,
    36270218540497705585629946580636237993140746255962,
    24074486908231174977792365466257246923322810917141,
    91430288197103288597806669760892938638285025333403,
    34413065578016127815921815005561868836468420090470,
    23053081172816430487623791969842487255036638784583,
    11487696932154902810424020138335124462181441773470,
    63783299490636259666498587618221225225512486764533,
    67720186971698544312419572409913959008952310058822,
    95548255300263520781532296796249481641953868218774,
    76085327132285723110424803456124867697064507995236,
    37774242535411291684276865538926205024910326572967,
    23701913275725675285653248258265463092207058596522,
    29798860272258331913126375147341994889534765745501,
    18495701454879288984856827726077713721403798879715,
    38298203783031473527721580348144513491373226651381,
    34829543829199918180278916522431027392251122869539,
    40957953066405232632538044100059654939159879593635,
    29746152185502371307642255121183693803580388584903,
    41698116222072977186158236678424689157993532961922,
    62467957194401269043877107275048102390895523597457,
    23189706772547915061505504953922979530901129967519,
    86188088225875314529584099251203829009407770775672,
    11306739708304724483816533873502340845647058077308,
    82959174767140363198008187129011875491310547126581,
    97623331044818386269515456334926366572897563400500,
    42846280183517070527831839425882145521227251250327,
    55121603546981200581762165212827652751691296897789,
    32238195734329339946437501907836945765883352399886,
    75506164965184775180738168837861091527357929701337,
    62177842752192623401942399639168044983993173312731,
    32924185707147349566916674687634660915035914677504,
    99518671430235219628894890102423325116913619626622,
    73267460800591547471830798392868535206946944540724,
    76841822524674417161514036427982273348055556214818,
    97142617910342598647204516893989422179826088076852,
    87783646182799346313767754307809363333018982642090,
    10848802521674670883215120185883543223812876952786,
    71329612474782464538636993009049310363619763878039,
    62184073572399794223406235393808339651327408011116,
    66627891981488087797941876876144230030984490851411,
    60661826293682836764744779239180335110989069790714,
    85786944089552990653640447425576083659976645795096,
    66024396409905389607120198219976047599490197230297,
    64913982680032973156037120041377903785566085089252,
    16730939319872750275468906903707539413042652315011,
    94809377245048795150954100921645863754710598436791,
    78639167021187492431995700641917969777599028300699,
    15368713711936614952811305876380278410754449733078,
    40789923115535562561142322423255033685442488917353,
    44889911501440648020369068063960672322193204149535,
    41503128880339536053299340368006977710650566631954,
    81234880673210146739058568557934581403627822703280,
    82616570773948327592232845941706525094512325230608,
    22918802058777319719839450180888072429661980811197,
    77158542502016545090413245809786882778948721859617,
    72107838435069186155435662884062257473692284509516,
    20849603980134001723930671666823555245252804609722,
    53503534226472524250874054075591789781264330331690,
]

first10 = str(sum(numbers))[:10]
print(first10)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

第14题 Collatz序列

Collatz序列的意思是，当一个数n是偶数时，下一数为n/2；当n为奇数时，下一个数为3*n+1。
这种序列有一个猜想，最后都会收敛于4，2，1。例如：
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
从100万之内挑一个数作为起始数，生成Collatz序列，哪个生成的链最长？

def collatz_len(x):
    if x == 1:
        return 1

    y = x * 3 + 1 if x % 2 else x // 2
    return collatz_len(y) + 1


max_collatz = 0
result = 0
for n in range(1, 1_000_000):
    c = collatz_len(n)
    if c > max_collatz:
        max_collatz = c
        result = n
        print(n, max_collatz)


print(result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

可以缓存一些结果，避免一些重复计算。

cache = {}

def collatz_len(x):
    if x == 1:
        return 1

    if x in cache:
        return cache[x]
    
    y = x * 3 + 1 if x % 2 else x // 2
    ret = collatz_len(y) + 1
    cache[x] = ret
    return ret


max_collatz = 0
result = 0
for n in range(1, 1_000_000):
    c = collatz_len(n)
    if c > max_collatz:
        max_collatz = c
        result = n
        print(n, max_collatz)


print(result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

第15题

第15题 网格路径
已知2x2网格中从左上角到右下角共有6条可能路径，计算20x20网格中，有多少条可能的路径。

解：
还是用递归的思路。对于m行n列的网格，可以利用其它网格的路径个数的结果，即：
P(m,n) = P(m-1,n) + P(m-1,n-1) + … + P(m-1,1) + P(m-1,0)
对于0行或者0列的网格，路径只有1条。

代码并不难：

def path_slow(m, n):
    if m == 0 or n == 0:
        return 1

    s = 0
    for j in range(n+1):
        s += path_slow(m-1, j)

    return s


print(path_slow(12, 12))
print(path_slow(20, 20))   
1
2
3
4
5
6
7
8
9
10
11
12
13

求和那几行语句，还可以用列表推导式写成一行：
s = sum([path_slow(m-1, j) for j in range(n+1)])

但递归的代价有点大，程序性能很差，12x12网格很快可以搞定，但20x20就非常吃力了。
加上缓存，则性能改善非常非常大。

cache = {}

def path_fast(m, n):
    if m == 0 or n == 0:
        return 1

    if (m, n) in cache:
        return cache[(m, n)]
    
    s = sum([path_fast(m-1, j) for j in range(n+1)])
    cache[(m, n)]  = s
    return s


print(path_fast(20, 20))  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15