欧拉工程第十一至二十题解题思路分析

十一、网格中的最大乘积

在下面这个20×20的网格中,对角线上相邻的四个元素已经用红色标记出来了,这四个数的乘积为26 × 63 × 78 × 14 = 1788696:

IMG

求在这个网格中,同一方向(上、下、左、右以及对角线)相邻四个元素最大乘积。

分析:此题似乎没有什么讨巧的简便算法,先将数据存入到一个嵌套列表当中,然后依次遍历每个元素,求它每个方向上相邻四个元素(如果有的话,需要条件判断)的乘积,存入到结果列表中,然后求最大值。

with open('euler/ep11.txt','r') as f:
    data = [map(int, s.split()) for s in f.readlines()]

def grid_largest_prod(data):
    import numpy as np
    length = len(data)
    res = np.zeros((length,length))
    right = down = down_right = left_down = 0
    for i in range(length):
        for j in range(length):
            right_exist = all([x<length for x in [i,i+1,i+2,i+3]])
            down_exist = all([x<length for x in [j,j+1,j+2,j+3]])
            left_exist = all([x>=0 for x in [i,i-1,i-2,i-3]])
            if right_exist:
                right = data[i][j]*data[i+1][j]*data[i+2][j]*data[i+3][j]
            if down_exist:
                down = data[i][j]*data[i][j+1]*data[i][j+2]*data[i][j+3]
            if right_exist and down_exist:
                down_right = data[i][j]*data[i+1][j+2]*data[i+2][j+2]*data[i+3][j+3]
            if left_exist and down_exist:
                left_down = data[i][j]*data[i-1][j+1]*data[i-2][j+2]*data[i-3][j+3]
            res[i][j] = max(right,down,down_right,left_down)
    max_res = np.max(res)
    return max_res

print(grid_largest_prod(data))

十二、高度可除的三角数

三角数即由依次排列的自然数的和构成,所以第7个三角数是\(1 + 2 + 3 + 4 + 5 + 6 + 7 = 28\),前十个三角数是:\(1,3, 6, 10, 15, 21, 28, 36, 45, 55,\cdots\),让我们列出前七个三角数的因子:

$$ \begin{equation} \begin{aligned} 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 \end{aligned} \end{equation} $$
可以看出28是第一个因子超过5的三角数,求第一个因子超过五百万的三角数。

分析:首先编写一个函数计算某给定自然数的因子数,每个自然的因子对称分布在平方根的两边,因此只需要找出小于平方根的因子数再乘以二便可以得到总的因子数。需要注意的,这样计算出来的平方数的因子会多一,因此需要从总数中减去一。接着,依次对每个三角数求其因子数,只到找到第一个因子数超过五百万的三角数,然后返回。

from math import sqrt

def num_of_divisor(n):
    if n == 1:
        return 1
    else:
        up_bound = int(sqrt(n)) + 1
        num = 0
        for i in range(1,up_bound):
            if n%i == 0:
                num = num + 1
        return (2*num) - (1 if (up_bound-1)**2 == n else 0)

def numd_of_triangle():
    n = 7
    while True:
        triangle = n*(n+1)//2
        num_d = num_of_divisor(triangle)
        if num_d <= 500:
            n = n + 1
        else:
            return triangle

print(numd_of_triangle())

十三、大数之和

计算如下一百个50位数的和(见数据文件ep13.txt),求这个和的前十位数。

分析:将这些数存入到TXT文件中,用python依次读取并加总,然后将该和转化为字符串并加前十位。

large_sum = 0
f = open("euler/ep13.txt")
for line in f.readlines():
    large_sum += int(line)
print(str(large_sum)[:10])

十四、最长的考拉兹序列

对于所有正整数,考虑如下迭代序列:

$$ n\rightarrow \frac{n}{2}\ if\ n\ is\ even,n\rightarrow3n+1\ if\ n\ is\ odd $$
从13开始并使用以上迭代规则,我们可以得到以下序列:
$$ 13\rightarrow40\rightarrow20\rightarrow10\rightarrow5\rightarrow16\rightarrow8\rightarrow4\rightarrow2\rightarrow1 $$
可以看出这个序列从13开始并到1结束总共包含10个数。考拉兹猜想指出使用以上迭代规则,所有正整数都会最终回到一,虽然这个猜想仍未得到证明。求在一百万以下,那个超始数可以产生最长的考拉兹序列?(注意:序列中包含的数的个数可以超过一百万。)

分析:首先编写一个计算考拉兹序列长度的函数,然后使用该函数对一至一百万之间的自然数求其考拉兹序列的长度,找出其中的最大值并返回初始点,即为所求。

import numpy as np

def num_of_terms(n):
    collatz = lambda n : 3*n+1 if n%2==1 else n//2
    num = 1
    while n !=1:
        n = collatz(n)
        num += 1
    return num

def max_start(n):
    terms_arr = np.array([num_of_terms(x) for x in range(1,n+1)])
    index = terms_arr.argmax() + 1
    return index

print(max_start(1000000))

十五、格子路径

在一个2×2的栅格中,从左上角出来,只能向右或向下移动,总共有6条路径可以到达栅格的右下角:

IMG

求在一个20×20栅格中,有多少条移动路径?

分析:根据维基百科上相关词条,对于一个\(N\times N\)的栅格,要从其\((0,0)\)点到达其\((n,k)\)点,总共可以行走的路线有\(C(n+k,n)\)条。为计算组合数,需要首先定义一个阶乘函数,然后便可求出结果。

def comb_num(n,k):
    fac = lambda n:reduce(lambda x,y:x*y,range(1,n+1))
    num = fac(n)/(fac(n-k)*fac(k))
    return num

def lattice_paths(n,k):
    return comb_num(n+k,k)

print(lattice_paths(20,20))

十六、指数各位数之和

\(2^{15}=32768\)且各位数之和为\(3+2+7+6+8=26\),求\(2^{1000}\)各个位数之和。

分析:求出\(2^{1000}\),将其转化字符串,并将字符串转化为整数再求和。

print(sum([int(x) for x in str(2**1000)]))

十七、数词字母数量

如果把数字一到五用单词写出来,即one, two, three, four, five,那么总共使用的字母数量:

$$ 3+3+5+4+4=19 $$
如果把从一到一千的数字用对应的单词写出来,总共需要多少个字母?(注意:不要计算空格与连字符,如342(three hundred and forty-two)包含23个字母,而115(one hundred and fifteen)包含20个字母,and的使用遵守英式英语的规则。)

分析:将所有需要用到的数词都存入到一个CSV文件中并用pandas导入,并将其转化为一个词典。分别考\([1:20],[21:100],[101:1000]\)不同的数词对应规则,编写一个将数字转化为相应的词语的函数,但忽略空格与连字符。列出所有1000以下的数字,转化为对应的词语并统计总的字母数量。

import pandas as pd
df = pd.read_csv('euler/ep17.csv',header=None)
words_dict = df.set_index(0).to_dict()[1]

def num_to_words(n):
    if n in words_dict.keys():
        return words_dict[n]
    else:
        if 21<=n<=100:
            ten_digit = n/10*10
            digit = n%10
            return words_dict[ten_digit] + words_dict[digit]
        elif 101<=n<=1000:
            hundred_dict = n/100
            remainder = n%100
            if remainder == 0:
                return words_dict[hundred_dict] + 'hundred'
            else:
                return words_dict[hundred_dict] + 'hundredand' + num_to_words(remainder)

print(sum([len(num_to_words(x)) for x in range(1,1001)]))

十八、最大和的路径

从以下这个三角形的顶部开始,向相邻的下一行的数字移动,经过之数所能得到的最大的和为23,即:\(3+7+4+9=23\)

$$ 3\\ 7\quad4\\ 2\quad4\quad6\\ 8\quad5\quad9\quad3 $$
对于以下三角形(见数据文件ep18.txt),求期从上到下所有路径中最大的和。【注:由于总共只有16384条路径,因此可以尝试每条路径并求最大值。然而,问题67与此问题类似但有三角形共有100行,从而无法用暴力枚举方法解决,这需要一个聪明的方法。】

分析:这是一道经典的动态规划问题,为求三角形从上到下的最大和,先从最下一行开始倒推,即:

$$ max(8+2,5+2)=10,max(5+4,9+4)=13,max(9+6,3+6)=15 $$

这样可以将最下二行合为一行,即:

$$ 3\\ 7\quad4\\ 10\quad13\quad15 $$

依次类推,可以继续倒推出:

$$ max(10+7,13+7)=20,max(13+4,15+4)=19 $$

即:

$$ 3\\ 20\quad19 $$

容易得到23是最大值,而路径也是题目中所给出的路径。对于题目中给出的三角形,与之类似可以得出答案。

with open('euler/ep18.txt') as f:
    table = [map(int,s.split()) for s in f.readlines()]

for row in range(len(table)-1, 0, -1):
    for col in range(0, row):
        table[row-1][col] += max(table[row][col], table[row][col+1])

print(table[0][0])

十九、计算星期天的数量

以下信息是题目直接给予你的,当然你也可以自己做一些研究:1900年1月1日是星期一,一月有30天的月份分别为九月、四月、六月与十一月,除开二月以外其它月份都有31天。二月在闰年有29天,其它年份有28天。闰年是年份可以整除四的年份,除非这个年份跨世纪的年份,但在跨世纪的年份中如果该年份可以整除400则也为闰年。在20世纪(1900年1月1日至2000年12月31日)每个月的首日是星期天的次数是多少?

分析:本题可以使用python中datetime模块解决,从1990年1月1日开始循环至2000年12月31日结束,如果某天同时为一个月的第一天且是星期天,则计数加一,这样便可以统计出整个二十世纪符合条件的天数。

def count_sundays():
    import datetime as dt
    delta = dt.timedelta(days=1)
    start_date = s = dt.datetime(1901, 1, 1)
    end_date = dt.datetime(2000, 12, 31)
    count = 0
    while start_date <= end_date:
        if start_date.day==1 and start_date.isoweekday()==7: count+=1
        start_date += delta
    return count

print(count_sundays())

二十、阶乘各位数的和

\(n!\)等于\(n\times(n-1)\times(n-2)\cdots\times3\times2\times1\),例如\(10!=10\times9\times8\cdots\times2\times1=3628800\),并且其各位数的和为\(3+6+0+8+8+0+0=27\),求\(100!\)各位数之和。

分析:直接求出\(100!\),并计算其各位数之和即可。

fac = lambda n:reduce(lambda x,y:x*y,range(1,n+1))
print(sum([int(x) for x in str(fac(100))]))