《从一到无穷大》中的程序思维

2020-03-19 16:27:13

这篇文章是近几天看李永乐老师的《从一到无穷大》读书专栏而想到的一篇文章。在章 「做做数学游戏」 的简单数学，以及第二章 「空间、时间和爱因斯坦」 的拓扑学中（其实也是因为李老师目前只更新了这么多￣□￣｜｜）有很多问题是可以通过计算机思维来思考的。所以这篇我将从计算机程序的角度来讨论《从一到无穷大》有趣的知识。

这篇文章会从科普数学角度以及程序解决问题的角度来讨论这些问题。

当然，如果你对自然科学感兴趣，并且也想观看李老师的专栏，在文章的末尾会有分享码。你可以通过我的分享来购买这门课程，我将佣金（目前是 29 元）全部返还给你。再次声明，我和荔枝微课平台没有任何合作，返还佣金只是为了给粉丝一些福利，交个朋友。

Eratosthenes 素数筛法

原文摘录：有没有什么简单的办法能够将所有的质数按照顺序一个不漏的列出来呢？古希腊哲学家暨数学家 Eratosthenes 提出了这个问题，我们称之为埃氏筛法。

算法讲述

其实在之前的「快速素数筛法」一文中已经介绍过。当我们需要判断快速得到一张素数表，我们可以通过素数的基本定义来解决这个问题。

素数（Prime Number），也叫质数，指在大于 1 的自然数中，除了 1 和它本身以外，无法被其他自然数整除的数。

根据描述，为了筛选出素数，我们可以直接写出暴力代码：

import math
import time
primes = [] * 100000

start = time.time()
for i in range (2, len(primes)):
    flag = True
# 只需要检查小于等于 sqrt(n) 的因数就可以了
# 因为大于的那部分一定对应着一个小于 sqrt(n) 的因数
for j in range(2, int(math.sqrt(i)) + 1):
if  == i %% j:
            flag = False
break
if flag:
        primes[i] = 1
end = time.time()
print(f'总耗时 {end - start}') # 总耗时 0.312835693359375

print(primes[3]) # 1
print(primes[4]) # 
print(primes[11]) # 1

这是我们正向的考虑这个数学问题。下面我们从计算机的一大思想 —— 缓存来想这个问题。当我们计算的时候，此时如果我们变换一个因子，这个数其实也变相的刨除了。

所以，如果我们用缓存策略来考虑这个问题，由于 2 是一个质数，那么所有 2 的倍数都不是质数！我们按照这个规律依次对后面的数做一个排除，就可以找到所有质数了。再次放上这张过程图，在阅读代码之前先大概了解下筛选流程，有助于你来理解代码：

primes = [1] * 100000

start = time.time()
primes[] = primes[1] = 

for i in range(2, len(primes)):
if primes[i] == 1:
for j in range(2, len(primes)):
if i * j >= len(primes):
break
            primes[i * j] = 

end = time.time()
print(f'总耗时 {end - start}') # 总耗时 0.0969996452331543

print(primes[3]) # 1
print(primes[4]) # 
print(primes[11]) # 1

复杂度分析

根据上述算法介绍，可以看出：当外层循环是 i 时，内层循环一共执行了次。因此总的时间消耗为：

其中表示不超过 n 的素数个数。根据素数定理^[1] 有以下等式：

根据文献「Villarino, Mark B, Mertens' Proof of Mertens' Theorem」^[2]，可知 Mertens 定理 2（下图为为文献中的定理引用部分）：

根据大 O 的无穷大渐进的估算方法，得到算法复杂度：

所以我们了解到 Eratosthenes 素数筛法将普通的的暴力筛选法优化到了级别。

哥德巴赫猜想

原文摘录：数论中还有一个既没被证明也没被伪证的有趣问题，人称「哥德巴赫猜想」（Goldbach conjecture）。这个猜想是在 1742 年被提出的，它宣称任何一个偶数都能表示为两个质数之和。

虽然我们现在也无法给出证明，但是由于我们学了上面的 Eratosthenes 素数筛选方法，则可以使用暴力方法来简单的验证一下哥德巴赫猜想。

import math

primes = [1] * 100000000

primes[] = primes[1] = 

for i in range(2, len(primes)):
if primes[i] == 1:
for j in range(2, len(primes)):
if (i * j) >= len(primes):
break
            primes[i * j] = 

def goldbach_check(n: int):
for k in range(2, 10000000 // 2):
if primes[k] == 1 and primes[n - k] == 1:
return (k, n - k)
return None


print(goldbach_check(16)) # 3, 13
print(goldbach_check(6398)) # 19, 6379
print(goldbach_check(7479634)) # 3, 7479631

也许你会问道：即使我们证明了哥德巴赫猜想，到底有什么实际的应用呢？我身为一个程序员会告诉你目前看上去完全没有什么用处。但或许当千百年后，哥德巴赫猜想或者证明哥德巴赫猜想的方法将会是某个重要理论的根基，而这个重要的理论也许将会改变整个世界。

古希腊几何学家阿波罗尼乌斯总结了圆锥曲线理论，在当时那个时代也饱受争议。但是在一千八百年后德国天文学家开普勒将其用于行星轨道理论，并提出了开普勒三大定律。何夕的《伤心者》当中说道：“世界沉默着，为了这些伤心的名字，为了这些伤心的名字后面那千百年的寂寞时光。”

四色定理

原文摘录：假设有一个划分为若干区域的球面，现在我们要给球面上色，使得任意两个相邻区域（即拥有共同边界的区域）的颜色各不相同。要完成这个任务，我们需要几种不同的颜色？（答案是四种，这也就是四色定理的问题模型）

关于四色定理的证明，其实是一个很好玩的故事。1976 年，数学家 Kenneth Appel 和 Wolfgang Haken 借助计算机将四色问题证明，四色问题也由此变成了四色定理。四色定理也是图论和拓扑学中的问题的抽象，所以使用编程来描述是十分合适的。

为了通过编程思维来了解四色定理，这里引入一个题目我们一起来思考一下解法。「POJ 1129 Channel Allocation」^[3]，题目描述大概意思是我们给出一个图来描述各个节点关系，然后我们用多种颜色给这个图染色，要求是相邻节点不能染成相同的颜色。解释一组样例：

Input:
4
A:BC
B:ACD
C:ABD
D:BC

Output:
3 channels needed.

这种情况，我们使用如图三种颜色进行图染色，就可以满足题目要求。

这道题其实我们知道，可以用深度优先搜索来完成这个染色尝试。我们简单来实现一下：

n = 4

input_demo = """A:BC
B:ACD
C:ABD
D:BC
"""

G = [[] for _ in range(n)]
mark = [] * n
ans = 4 # 根据四色定理，我们得知 ans 大值就是 4

datas = input_demo.split("\n")

for line in datas:
if len(line) == :
continue
    f = ord(line[]) - ord('A')
for to_ch in line[2:]:
        t = ord(to_ch) - ord('A')
        G[f].append(t)

def check(x: int, col: int) -> bool:
global G, ans, mark
if mark[x] != :
return False
for i in G[x]:
if mark[i] == col:
return False
return True

def dfs(pos: int):
global G, ans, mark
if pos == n:
        ans = min(ans, max(mark))
return 
for i in G[pos]:
# 根据四色定理，仅需要使用 4 个颜色来染下一步即可
for col in range(1, 5):
if check(i, col):
                mark[i] = col
                dfs(i + 1)

mark[] = 1
dfs(1)

print(mark) # 染色方法 [1, 3, 2, 1]
print(ans) # 需要颜色 3

当我们知道了四色定理这个结论，这道题其实就 在结果上已经做出了大幅度减枝。

当然四色定理的我们可以进而将其抽象，他还可以利用在排程和分配问题上。例如我手上的几个任务，他们某几个之间存在互斥性，我需要对其进行排期。这时候我对日程来建立图，就可以求得排期方式。图论神奇的地方，就是它可以将各种各样的模型转换成拓扑图的关系问题，再通过图算法从而高效的得到问题的答案。