使用代数优化代码

照片由 Roman Mager 在 Unsplash 上拍摄

大学期间，我选修了一门名为“离散数学”的课程。讲师决定将学生分成小组，每组由两到三名学生组成。他们要针对讲师布置的特定主题进行阐述。

我所在的小组（实际上只有两个人）给我们布置了“递归关系”的课题。根据维基百科的解释，这是：

一旦给出一个或多个初始项，递归定义值序列或多维数组的方程：序列或数组的每个进一步的项都定义为前面项的函数。

换句话说，递归函数；）

用代码来解释这个概念是完美的情况:D

河内塔

你还记得这个玩具吗？

著名的汉诺塔。游戏要求玩家用尽可能少的步数，将所有盘子从第一根柱子移动到最后一根柱子（从左到右，或从右到左）。规则是：大盘子不能放在小盘子上方，并且每次只能移动一个盘子。例如：

这个问题有一个解决它的算法，它是这样的：

其中n是问题中的磁盘数量。

让我们编写代码

让我们用 Python 来编写这个算法。它就像这样：

def hanoi(n):
    if n <= 1: return 1
    else: return 2 * hanoi(n-1) + 1

因此如果我们有 4 个磁盘...

>>> hanoi(4)
15

很好。有效。我们试试吧

>>> hanoi(5)
31
>>> hanoi(10)
1023
>>> hanoi(40)
1099511627775

看起来不错。现在我知道如果用 40 个盘子的话需要移动多少次了（顺便说一句，这得花 10460 年，千万别在家试）。但如果我有 7000 个盘子呢？

>>> hanoi(7000)
Traceback (most recent call last):which
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in hanoi
  File "<stdin>", line 3, in hanoi
  File "<stdin>", line 3, in hanoi
  [Previous line repeated 994 more times]
  File "<stdin>", line 2, in hanoi
RecursionError: maximum recursion depth exceeded in comparison

哦……看来这性能不够好。当然，你可以用增加 Python 中的最大递归深度（使用sys.setrecursionlimit(n)）来“解决”这个问题，但优化一下会更好。

优化

解决递归关系的方法有很多种，其中之一就是迭代。它包括逐步求解运算，并从过程中推导出非递归方程。首先，我们尝试求解一个给定的值：

然后，从最后一行，我们可以推导出一个等价的方程：

如果你注意到，t(4) = 8 + 7它与 相同t(4) = 2^(4-1) + (2^(4-1) - 1)，这就是为什么它是我们的初始语句。但是现在我们已经解决了递归关系，让我们在代码中使用它。

def better_hanoi(n):
    return 2**n - 1

进而...

现在我们知道用 7000 个磁盘解决这个问题需要多少步（可能是宇宙寿命的几倍）。

结论

我们利用离散数学的概念优化了一个小算法，这只是为了让我们稍微了解一下如何利用这些简单的概念来构建更好的程序。