斐波那契数列编码面试：兔子洞

• 下载源代码 - 4.7 KB

引言

软件开发人员对斐波那契数和编码面试有什么看法？虽然我们大多数人可能会同意面试旨在展示我们最好的知识和经验，但斐波那契数可能被认为是初学者的编码练习。然而，是否有可能将这两个概念融合成有用的东西？

对这个主题进行了更多思考后，我得出了一个相当出人意料的结论：尽管斐波那契数看似简单，但我们可以利用它们来开发几个使用多种编程技术的代码片段。我们还可以进行一些不错的渐近复杂度分析，而无需深入研究数学。

综合来看，我可以想象这种面试场景的概念验证。这个场景无疑是人为的：面试官总是问候选人预期的问题，而候选人也准备好了回答。为了使事情更接近初级面试的实际情况，我使用了一种我不太熟悉的编程语言，并且在没有查阅教科书（除了一个漂亮的公式）的情况下进行了所有数学运算，因此牺牲了严谨性以换取简洁性。我还应该注意到，本文中使用的代码和数学绝非新事物，因此我绝不会声称拥有著作权。最后，您肯定会注意到我写的文字比代码多得多。 *Mea culpa。* 我很喜欢E. W. Dijkstra大约50年前写的这些话 [1, 第39页]

... 很难声称你知道自己在做什么，除非你能将你的行为作为你本可以做的可能事情中的一个蓄意选择来呈现。

尽管如此，我希望有人能发现我的文章至少有趣，甚至能学到一些有用的东西。

背景和约定

本文的目标受众是初级软件开发人员和/或学习计算机科学基础知识的学生。经验丰富的开发人员也欢迎，但他们不太可能看到任何新东西。

代码片段使用Python（Anaconda 2023.03中的v3.10）编写，因此需要具备该语言的中级知识。

下面的文本使用一些排版约定来区分对话的不同部分

• 普通文本（像这样）用于候选人的讲话，这构成了下面大部分文本。
• 面试官的问题看起来像引文

  面试官

  请您多谈谈这个话题好吗？

• 预计对读者有用但在实际面试中不宜大声说出的评论如下

  注意赋值语句的使用。

级别0：各种实现

面试官

好的，让我们开始。您想如何实现一个计算斐波那契数列的程序？

我将从这个序列的定义开始。让我们用以下递归规则来指定它

假设我们可以通过打印前 \(n\) 个斐波那契数来展示我们的解决方案，这段代码似乎足以开始讨论

n = int(input("Enter series length: "))

assert(n >= 1)

past_item, current_item = 1, 0

for i in range(n):
    print(current_item)
    past_item, current_item = current_item, past_item + current_item 

面试官

开个好头。现在，您看到任何改进解决方案的方法了吗？

用户需求是改进的首要任务，但由于我们目前没有新的需求，我们可以根据软件工程最佳实践，致力于改进我们的代码。

我们当前的实现不符合两个重要标准：代码既不可*重用*也不可*维护*。实际上，我们可以看到两个交织的活动：计算斐波那契数和执行输入/输出操作。因此，我们不能轻易地将这些计算用于其他目的，也不能在不理解输出部分的情况下修改它们，反之亦然。

因此，我们应该将斐波那契数的计算与输出分开。

面试官

同意。鉴于我们的时间有限，我们省略I/O细节，只讨论数字的计算。

当前的实现使用全局变量来保存当前和过去生成的数字（或计算*状态*）。这使得，例如，不可能一次生成多个数字序列。为了改进这一点，我们应该将我们的状态存储到一些适当的*数据结构*中。在我们的案例中，任何能够存储两个整数的数据结构都足够了（例如，对、两元素数组或列表，等等），但最方便的选择是面向对象编程范式意义上的*对象*，因为这使得将我们的解决方案与我们选择的语言中的其他代码集成起来更容易，而这种语言鼓励使用这种方法。

我们现在必须做出的下一个设计决策比上一个更重要：我们应该如何生成我们的数字？不同的问题可能需要不同的“访问模式”：有时，按顺序一个一个地或以某种大小的块生成数字很方便，但有时我们只需要这些数字的子集，以随机顺序。

面试官

你认为这个决定为什么如此重要？

因为我们的选择直接决定了我们代码的生命周期。大多数程序并非一成不变，因此我们必须随着时间的推移修改它们。选择得当的抽象能够更长久地抵御这些变化。然而，我们也必须明白，随着对软件提出新的要求，我们最终将耗尽原始设计选择的灵活性储备，并且应该准备好向前迈进，审视它们，有时甚至彻底推翻它们。

到目前为止，让我们从一个可能以相当老式的面向对象风格编写的解决方案开始，它也可能非常适合Python以外的其他语言。

class OldSchool:
    def __init__(self):
        self._past_item = 1
        self._current_item = 0

    def next_value(self):
        self._past_item, self._current_item = self._current_item, self._past_item + self._current_item

        return self._past_item 

将此代码放入单独的源文件，例如 `fib.py`，我们创建了一个模块，该模块可以在多个程序中使用。

为了生成斐波那契数列，我们现在应该创建 `OldSchool` 类的一个实例，并根据需要多次调用 `next_value` 来获取该数列的另一个项。

import fib

fo = fib.OldSchool()

print([fo.next_value(), fo.next_value(), fo.next_value()])
print([fo.next_value(), fo.next_value()]) 

输出是：

[0, 1, 1]
[2, 3] 

更甚者，我们可以创建多个对象并同时生成多个序列

fo1 = fib.OldSchool()
fo2 = fib.OldSchool()
print([[fo1.next_value(), fo1.next_value()], [fo2.next_value()], [fo1.next_value()], [fo2.next_value()]])
print([[fo1.next_value()], [fo2.next_value(), fo2.next_value()], [fo1.next_value()], [fo2.next_value()]]) 

输出是：

[[0, 1], [0], [1], [1]]
[[2], [1, 2], [3], [3]]

根据上面的代码片段，我们可以得出结论，我们当前的实现可以通过多种方式重用（无论是在不同的程序中，还是在一个程序中生成多个序列）。此外，由于实现细节被隐藏起来，并且可以在不重做“客户端”代码的情况下进行更改，因此我们也获得了更好的可维护性。

自动化单元测试对于可维护性甚至更为重要，因为它们提供了代码更改时不可避免的错误的早期诊断。反过来，使代码可重用对于单元测试是绝对必要的。

面试官

好的。我同意单元测试的重要性，但让我们暂时搁置讨论。您刚才提到，可以有另一种生成数字块的实现方式。您有什么理由更倾向于逐个生成同一序列中的项吗？

是的，我们可能会将我们的实现更改为类似这样的东西

class Blocks:
    def __init__(self):
        self._past_item = 1
        self._current_item = 0

    def next_values(self, n=1):
        assert (type(n) is int and n >= 0)

        if n < 0:
            raise ValueError("Block length must be non-negative")

        result = []

        for i in range(n):
            result.append(self._current_item)
            self._past_item, self._current_item = self._current_item, self._past_item + self._current_item

        return result 

这可以大大简化我们目前的任务

fb = fib.Blocks()

print(fb.next_values(3))
print(fb.next_values(4)) 

输出是：

[0, 1, 1]
[2, 3, 5, 8] 

然而，跳出思维定式，我们可以预见到面向块方法的一个不希望出现的后果：即使我们稍后逐项消费它们，我们也会提前生成所有数字。考虑到块大小可能很大，由于将项添加到列表中而导致的内存不必要的消耗和性能损失可能会很明显。因此，似乎更优选逐项生成我们的序列，我们可以在需要时使用，例如，列表推导将其打包到列表中。

fo = fib.OldSchool()
print([fo.next_value() for i in range(5)])

[0, 1, 1, 2, 3] 

面试官

您提到您的方法有些老式，并且适用于其他语言。您能向我们展示一些针对Python的代码改进吗？

一种可能的方法是使用名为 `__call__` 的特殊方法来使我们的代码更简洁。这种语法糖既不会改变内存消耗也不会改变执行速度，但可以说，它改善了我们的视觉体验。

class Callable(OldSchool):
    def __call__(self):
        return self.next_value()

请注意，我们通过继承再次重用了我们现有的代码。

fc = fib.Callable()
print([fc(), fc(), fc()])
print([fc() for i in range(4)])

输出是：

[0, 1, 1]
[2, 3, 5, 8]

另一个改进是使我们的类可迭代

class Iterable:
    def __iter__(self):
        class FibIter:
            def __init__(self):
                self._seq = OldSchool()

            def __iter__(self):
                return self

            def __next__(self):
                return self._seq.next_value()

        return FibIter()

这个类看起来完全不同，但它也重用了 `OldSchool`，这次是通过聚合。

虽然我们之前让对象“可调用”的改进只是表面上的，但后者影响更大：通过这种方式，我们使用所谓的“迭代器协议”将我们的代码集成到通用语言基础设施中。

import itertools

fi = iter(fib.Iterable())

print(next(fi))
print(list(itertools.islice(fi, 2)))
print(list(itertools.islice(fi, 4)))
print(next(fi))

输出是：

0
[1, 1]
[2, 3, 5, 8]
13

请注意，itertools 模块允许我们做的事情远不止简单地从可迭代对象中收集数据

print(sum(itertools.takewhile(lambda x: x < 30, fib.Iterable())))

输出是：

54

此表达式从斐波那契数列中取出其值不超过30的第一个项目，并计算它们的和，所有这些都在一行代码中完成。

面试官

确实，这种编程风格非常简洁和富有表现力。请您告诉我，它的优点和缺点是什么？

抛开表达力不谈，我还可以说这种方法效率很高：实现可迭代的代码只是逐个生成项目，只要调用者消费它们，就不再生成。

关于它的弱点，它自然适用于单趟算法，这些算法或多或少按照序列项出现的顺序（逐个或以有限大小的块）消费序列项，其他项访问模式可能需要其他抽象。此外，正如我们所见，实现迭代器协议需要一些样板代码，并且可能不直观。

面试官

有什么改进的办法吗？

如果我们将可迭代对象重写为生成器函数，则可以自动生成样板代码。

def seq():
    past_item, current_item = 1, 0

    while True:
        yield current_item
        past_item, current_item = current_item, past_item + current_item

这个特殊函数（注意 `yield` 的使用）被调用时，有效地返回一个类似于我们的 `fib.Iterable` 的可迭代对象，但所有必要的机制都在底层自动创建。它可以完全像上面那样使用。

print(sum(itertools.takewhile(lambda x: x < 30, fib.seq())))

输出是：

54

面试官

那么，生成器可以被认为是创建序列的终极解决方案吗？

这取决于情况。在大多数情况下，它们确实绰绰有余，但有时我们可能需要对迭代进行额外的控制。例如，某些算法（例如，解析器）可能需要“预读”或检查传入项而不消费它的能力。同样，有些问题可能需要保存迭代器的当前状态并将其恢复。在所有这些情况下，自定义可迭代对象可以提供所需的方法。

级别1：与复杂性作斗争

面试官

好的，现在让我们考虑另一个用例：我们需要按索引随机顺序生成斐波那契数列的子集。我们是否可以重用我们最近讨论过的一些代码？

不，很不幸，我们不能。这次，我们遇到了我之前提到的问题：每个决定都有其局限性。我们可以尝试像这样重用我们现有的代码：

def nth_seq(n):
    assert (type(n) is int and n >= 0)

    if n < 0:
        raise ValueError("Item index must be non-negative")

    return next(itertools.islice(seq(), n, None))

乍一看，这如预期般有效，而且看起来不错。

print([fib.nth_seq(i) for i in [3, 5, 6, 4]])

输出是：

[2, 5, 8, 3]

然而，这个解决方案的性能是不可行的。实际上，生成给定索引 \(n\) 的数字时，我们会在底层重新生成整个子序列 \(F_0\), \(\ldots\), \(F_n\)。使用大 \(O\) 符号，`nth_seq(n)` 的复杂度是 \(O(n)\)。

当我们生成单个数字时，这种复杂度可能看起来可以接受，但如果我们需要，比如 \(m\) 个数字，这些 \(O(n)\) 就会累积起来。

面试官

您能提供一个更好的估算吗？

更好的估计需要关于 \(n\) 的额外知识，这对于每个 \(m\) 都可能不同。例如，如果我们试图从一组预先打乱的索引中生成前 \(m\) 个斐波那契数的随机打乱序列，我们可能会调用 `nth_seq` \(m\) 次，对于 \(0 \le i < m\) 的每个值，以随机顺序调用。在这种情况下，我们为每个 \(i\) 生成 \(i+1\) 个斐波那契数（请记住，我们从零开始索引序列），并且生成的总项数为

这反过来对应于复杂度 \(O(m^2)\)。

面试官

那我们对话一开始提到的递归公式呢？

将这个公式直接放入代码中，我们可以得到一个相当优雅的函数

def nth_rec(n):
    assert (type(n) is int and n >= 0)

    if n < 0:
        raise ValueError("Item index must be non-negative")
    elif n == 0:
        return 0
    elif n <= 2:
        return 1
    else:
        return nth_rec(n - 2) + nth_rec(n - 1)

不幸的是，这个函数的性能估算要差得多。事实上，如果我们展开公式

我们可以看到 \(F_{i-2}\) 被计算了两次。因此，计算第 \(i\mbox{th}\) 个数字所需的工作量*至少*是其前前身的两倍。由于这种倍增也发生在第 \((i-2)\mbox{th}\) 个项目上，依此类推，我们可以得出结论，我们复杂性估算的*下界*将是

请注意，这个界限过于乐观：我们没有考虑计算 \(F_{i-3}\) 所需的工作量。

看着这个函数，我们可以得出结论，它是阶梯式的，非递减的，并且在 \(n\) 的偶数值处增长。

这项快速检查得出了一个不幸的结论：我们的 `nth_rec` 具有指数复杂度，这甚至比我们最初的尝试更糟。

面试官

还有其他改进的办法吗？

是的，我们可以使用“备忘录”技术，消除此函数中出现的组合爆炸。

class _NthMem:
    def __init__(self):
        self._nums = {}

    def __call__(self, n):
        assert (type(n) is int and n >= 0)

        if n < 0:
            raise ValueError("Item index must be non-negative")
        elif n == 0:
            return 0
        elif n <= 2:
            return 1
        else:
            f_n = self._nums.get(n, None)

            if f_n is None:
                f_n = self(n - 2) + self(n - 1)
                self._nums[n] = f_n

            return f_n


nth_mem = _NthMem()

这种方法的基本思想是：每个首次计算的斐波那契数都会以数字索引作为键保存到映射中。当以后需要时，我们从映射中获取并重用，而不是从头开始重新计算。

这个看似简单的改进却产生了巨大的影响

print(fib.nth_mem(50))

输出

12586269025

递归实现不太可能在合理的时间内产生这个结果。

面试官

是的，这种优化确实创造了奇迹。备忘录实现的开销是多少？

让我们计算 `nth_mem` 的 \(m\) 次调用的成本，其中 \(n_{max}\) 是这 \(m\) 次调用中使用的最大斐波那契数索引。鉴于我们有一个体面的字典实现，它为我们提供了单个添加/查找操作的恒定均摊成本，我们可以说填充 \(n_{max}\) 个斐波那契数的表格的成本是 \(O(n_{max})\)。实际上，从已知的前驱计算每个下一个数字将需要恒定的工作量（从字典中获取两个数字并存储它们的和）。在所有这些 \(n_{max}\) 个数字计算完毕后，`fib_mem` 的所有后续调用也需要恒定时间（从字典中获取预计算的数字）。

因此，我们有两种情况：当 \(n_{max}\) 主导 \(m\) 时，总时间复杂度为 \(O(n_{max})\)；否则，我们有 \(O(m)\)。综上所述，我们可以将最终估计写为 \(O(\max(n_{max}, m))\) 或 \(O(n_{max} + m)\)。

顺便说一句，这个估计特别意味着，如果我们使用 `nth_mem` 来生成斐波那契数列，并以从 \(0\) 到某个 \(n\) 递增的索引调用它，那么这个过程的总时间复杂度也将是 \(O(n)\)，与我们使用某个顺序实现（例如 `seq`）所能得到的相同。

面试官

太棒了！从最初的二次方到指数级，我们终于得到了线性时间！然而，我应该注意到，`fib_mem` 包含了与我们的应用领域（计算斐波那契数）相关的代码以及记忆化的实现细节，使其不够清晰。我们能做得更好吗？

遵循我们最初使代码可重用的目标，我们可以使用Python的一个特性，即装饰器，将表格查找的实现与一些特定计算分离。

def memoize(f):
    class _MemF:
        def __init__(self, f):
            self._vals = {}
            self._f = f

        def __call__(self, x):
            y = self._vals.get(x, None)

            if y is None:
                y = self._f(x)
                self._vals[x] = y

            return y

    return _MemF(f)

@memoize
def nth_dec(n):
    assert (type(n) is int and n >= 0)

    if n < 0:
        raise ValueError("Item index must be non-negative")
    elif n == 0:
        return 0
    elif n <= 2:
        return 1
    else:
        return nth_dec(n - 2) + nth_dec(n - 1)

正如我们所看到的，`nth_dec` 函数将斐波那契数的定义从实现细节中解放出来，而其性能与 `nth_mem` 相当。同时，`memoize` 装饰器也可以毫不费力地用于为其他函数添加记忆化。

级别2：越来越好奇

面试官

回到您之前所说，考虑到 `nth_mem` 或 `nth_dec` 这两种记忆化实现，当需要生成前 \(n\) 个斐波那契数时，它们的渐近时间复杂度都是 \(O(n)\)，那么我们能否用它们来替代我们面向序列的代码呢？

我不建议做出这样的决定，因为这个估算是一个渐近估算，包含一个隐藏的系数，这在实际场景中可能会造成很大的差异。简单来说，顺序生成器只是计算下一个数字并更新一对状态变量，而我们的记忆化递归函数最终需要维护一个字典，因此需要更多的精力。除此之外，我们还应该考虑内存消耗。

面试官

顺便问一下，我们能否也估算一下备忘录的内存复杂度？

与时间复杂度不同，我们通常可以分析某个数据结构的性能而忽略存储对象的性质，内存复杂度本质上取决于数据的性质，因此我们无法一概而论。

然而，斐波那契数列允许我们做得更好。为了简化问题，我们不考虑簿记成本，即存储一个包含 \(n\) 个条目的字典所需的内存量（这个量很大程度上取决于该字典的实现），而是尝试估计存储这些数字本身所需的内存。

让我们从一个简单的事实开始：存储某个数字 \(x\) 所需的内存可以通过其对数 \(\log x\) 来估计（对于渐近分析，对数基数可以是任意的）。

我们能否估算某个斐波那契数的对数？幸运的是，我们可以使用所谓的 *比内公式* 来做到这一点。

其中

让我们尝试估算这个表达式的下界。首先，我们可以注意到当 \(i\) 为奇数时，\(\psi^i < 0\)。因此，我们可以得出以下结论：

对于 \(i\) 的偶数值，我们可以利用 \(F_{i+1} > F_i\) 的事实，因此

后者的偶数索引下界也适用于奇数索引，尽管它会不太精确。然而，它允许我们得到一个通用估计。

因此

同样的方法也适用于 \(F_i\) 的对数

因此

面试官

看起来非常令人印象深刻！我以前从未想到斐波那契数与其索引之间存在这种关系。我们能否获得一些证据来证明这些估算值是正确的？

我们可以尝试计算序列某部分的这个下界，看看它是什么样子。顺便说一句，这将是一个很好的机会，看看我们的序列生成器如何与标准库中的一些工具协同工作。

phi = (1 + math.sqrt(5)) / 2

logF_lb = map(lambda i, F_i: ((i - 1) * math.log(phi) - math.log(math.sqrt(5)), math.log(F_i)), 
              itertools.count(1),
              itertools.islice(fib.seq(), 1, None))

print(list(itertools.islice(logF_lb, 10)))

这段代码片段以函数式风格编写。我们使用内置的`map`函数处理两个无限列表：第一个是索引流，第二个是斐波那契数列。序列的零项被省略以避免`math.log`引发`ValueError`。传递给`map`的lambda表达式计算下界估计和斐波那契数的有效对数，并将它们作为一对返回。

请注意，实际计算仅在最终序列被有效消费时发生，即当我们从 `logF_lb` 中提取前 10 个项目并将其转换为列表并打印时。

产生的输出是（为便于阅读分行）

[(-0.8047189562170503, 0.0), (-0.3235071311574468, 0.0), 
 (0.1577046939021567, 0.6931471805599453), (0.6389165189617603, 1.0986122886681098), 
 (1.1201283440213636, 1.6094379124341003), (1.601340169080967, 2.0794415416798357), 
 (2.082551994140571, 2.5649493574615367), (2.563763819200174, 3.044522437723423), 
 (3.0449756442597775, 3.5263605246161616), (3.5261874693193813, 4.007333185232471)]

正如我们所看到的，每个下界估计（第一项）确实小于相应的对数值（第二项）。

面试官

那么，我们如何利用这些估计来获得内存复杂度呢？

正如我之前所说，存储某个数字所需的内存与其对数成正比。假设我们已经生成了一些索引小于或等于 \(n\) 的斐波那契数。在这种情况下，存储记忆化值所需的内存可以估计为

请注意，我们忽略了 \(F_0=0\)，因为其对数未定义。在进行渐近分析时，允许在序列开头删除固定数量的项。

这个和的下界

这个不等式的右边又可以转化为

综上所述，我们有

面试官

所以，看起来我们注定要么花费时间从头开始计算每个斐波那契数，要么需要大量的内存来使用备忘录。当处理相当大的数字时，这两种选择都显得很痛苦。

有没有办法摆脱这种“打地鼠”的困境？我们是否可以使用比内公式直接计算所需的斐波那契数？

我不建议这样做，因为使用比内公式需要处理无法完全精确表示的无理数。此外，对实数的内置支持通常实现遵循无处不在的IEEE 754 标准的浮点算术。假设我们使用双精度数据格式，我们不能期望大于 \(2^{53}\) 的整数总能准确表示而不会损失精度。更糟糕的是，由于各种微妙的舍入和其他浮点计算的陷阱，即使远低于此上限，我们也可能得到不准确的结果。

幸运的是，斐波那契数有一些数学特性，这使得我们能够提出一个非常优雅的解决方案。让我们回顾一下我们的顺序实现：它基于保存斐波那契数列的最后两个项并在每一步更新它们。这个过程可以用向量表示法表达。

其中 \(f\) 是某种变换。斐波那契数列属于所谓的线性递推类，这种变换可以用矩阵乘法表示：

请注意，我们使用此矩阵乘积将斐波那契数列生成器的当前状态转换为下一个状态，即计算下一个序列项，该项始终保存在状态向量的第二个位置。执行下一步需要再进行一次矩阵乘积

代入我们之前的矩阵乘积，我们可以看到这个模式

也就是说，如果我们想让当前生成器状态前进 \(n\) 步，我们可以通过将该状态乘以矩阵的 \(n\) 次方立即完成。而奇妙之处在于： *我们可以在对数时间内计算这个幂*！实现这一魔法的秘方被称为平方求幂。

所以，我们可以用这个公式替换比内公式

以 \(O(\log n)\) 的时间得到 \(F_n\)（\(F_{n-1}\) 作为额外奖励）。

该算法的实现如下

def _mul_2x2(x, y):
    return [[x[0][0] * y[0][0] + x[0][1] * y[1][0], x[0][0] * y[0][1] + x[0][1] * y[1][1]],
            [x[1][0] * y[0][0] + x[1][1] * y[1][0], x[1][0] * y[0][1] + x[1][1] * y[1][1]]]

def _pow_2x2(x, n):
    res = [[1, 0], [0, 1]]
    sq_i = x

    while n > 0:
        if n & 1 != 0:
            res = _mul_2x2(res, sq_i)
        sq_i = _mul_2x2(sq_i, sq_i)
        n >>= 1

    return res

def _mul_2x2_v(x, y):
    return [x[0][0] * y[0] + x[0][1] * y[1], x[1][0] * y[0] + x[1][1] * y[1]]

def nth_mtx(n):
    assert (type(n) is int and n >= 0)

    if n < 0:
        raise ValueError("Item index must be non-negative")
    else:
        A_n = _pow_2x2([[0, 1], [1, 1]], n)
        st_n = _mul_2x2_v(A_n, [1, 0])
        return st_n[1]

让我们试试看

print([(i, len(str(fib.nth_mtx(i)))) for i in [200, 400, 600]])

如您所见，生成的斐波那契数中的十进制位数确实呈线性增长。

[(200, 42), (400, 84), (600, 126)]

最后，这条语句会立即执行

print(fib.nth_mtx(1000000) % 1000000)

产生

546875

我还应该注意到，如果你有一对连续的斐波那契数，比如说 \(\left\langle F_{i-1}, F_i \right\rangle\)，你可以用同样的方法计算相对于 \(i\) 的第 \(n\) 个数，即 \(\left\langle F_{i+n-1}, F_{i+n} \right\rangle\)。同样地，我们可以后退，这次使用另一个矩阵。对于斐波那契数列，这个矩阵也可以轻松写出。

面试官

看起来很棒！但是，这个公式有什么实际应用吗？还是说它只是一个沙龙技巧，只能娱乐我和那些有耐心读到这里的充满好奇的人？

如果你知道相应的矩阵，这种方法可以用于任何线性递推。特别是，许多流行的伪随机数生成器都基于某种线性递推，这种理论允许我们将它们分解成多个独立的“流”。这些流反过来在需要并行化或分布式计算时非常有用。（关于这个有趣问题的更多信息可以在这里阅读。）

面试官

今天就到这里。感谢您给我这个机会，从这个不寻常的角度看待斐波那契数！

结论

我们假想的面试结束了。我们假想的候选人从同样假想的面试官那里得到了假想的“是”。回到现实世界，我们可以展示哪些软件工程和 Python 技能呢？让我们按出现顺序将其列出：

• 在编码之前澄清任务所有细节的好习惯。
• 基本的编程技能，例如使用I/O和循环。
• 理解简单地解决问题和创建可重用、可维护的代码之间的区别——这对软件工程师非常重要，但有时会被从学术界进入软件开发领域的人忽视。
• 理解软件设计是寻求各种可能解决方案之间适当平衡的途径，更重要的是，这种平衡并非一成不变，最终将需要进行一些破坏性更改。
• 使用面向对象方法来改进我们的初始解决方案。
• 使用列表推导。
• 使用Python特殊方法使代码更具可读性。
• 通过迭代器协议将我们的解决方案与Python提供的标准库集成。
• 通过继承或聚合重用代码。
• 使用 `itertools` 进行“类函数式”编程。
• 使用Python生成器使我们的解决方案更加清晰。
• 使用“大 \(O\) 符号”执行一些基本的复杂度分析。
• 使用递归。
• 使用备忘录化改进递归解决方案的速度。
• 使用Python装饰器实现可重用的备忘录化。
• 用数学解决一个从纯粹工程角度看似乎无望的问题（在现实生活中这种情况相当罕见，但我认为，软件工程师应该意识到这种可能性并尽可能地寻找它）。

对于“新生级练习”来说，这看起来还不错，不是吗？这套技能真的足以通过面试吗？不同的职位需要设计、数学和纯粹编码的不同组合，所以没有一个单一的答案。从我个人角度来看，了解所讨论的主题至少应该给你一些额外的分数，而且不会有害。

至于我从这篇文章中获得的经验，我认为它是积极的：虽然我事先知道一些事情，但在进展中也探索了许多其他事情。希望您也学到了一些有用的东西。

参考文献

• [1] Edsger W. Dijkstra。结构化编程笔记。载于 *结构化编程*，第1-82页。Academic Press Ltd.，伦敦和纽约，1972年。（可在线获取。）

历史

• 2023年12月27日：初始版本