编程任务往往有多种解决方案，然而一种方案可能运行速度比另一种快。编写运行速度快的程序不仅需要编程者拥有艺术眼光，还要拥有坚实的编程基础。在下列习题中会有一些示例。

第1部分：避免进行重复计算

斐波那契数列是一个既简单又吸引人的数列。前两项是1，1，接下来每一个数字是前两个数字的和。比如，下一个数字是1+1=2。这样前三项就确定了，

1, 1, 2

第四项是1+2=3，然后是2+3=5，以此类推：

1, 1, 2, 3, 5, 8, 13, ...

斐波那契数列原本是用来解决兔子数量的问题，但是还和植物建筑相关。下面是一个有关斐波那契数列视频：

斐波那契数列的定义会令人很自然地想到递推方程。下一个练习题定义了一个方程Fibonacci(n)，返还上述序列中第n项（从n=1开始）。

综合练习: Nibofacci

整理这个程序，返还一个斐波那契数列递推定义。判分系统会打印出它们的前十项。

• if (n==1 or n==2):
• return 1
• def Fibonacci(n):
• return Fibonacci(n-1) + Fibonacci(n-2)
• else:

在下方输入测试语句，例如 print(myfunction("test argument")) 。

然而，这个递推方程运行起来很慢。点击输入测试语句，输入print(Fibonacci(80))。测试它时会得到"超出时限"提示。

为什么运行地这么慢？因为这个方程没有复杂的指示或循环，只有加法，总共调用方程的次数太多。如果我们调用Fibonacci(3)，递推方程总共会被调用三次：最开始的调用，然后是两个递推调用。如果我们调用Fibonacci(4)，递推方程被调用了五次：最开始的调用，刚刚讲过的三次n=3，还有一个递推调用n=2。Fibonacci(5)总共会有九次调用，Fibonacci(6)会有9+5+1=15次调用。调用的次数会随着n增长而迅速增长！

粗略估计，Fibonacci(n+2)的调用次数至少是Fibonacci(n)调用次数的两倍。因为Fibonacci(n+2)直接调用一次Fibonacci(n)，还有通过递推非直接调用Fibonacci(n+1)。所以计算时间与指数函数成正比，至少有(√2)ⁿ这么大。比如，Fibonacci(80)需要多于2⁴⁰ = 1099511627776次递推调用。

这个论据还略述了概念性的问题：调用Fibonacci(n)两次，从零开始重新计算结果太浪费时间了。如何用相同的方法，但是不重复计算？

答案

让我们试试类似于介绍中所写的东西。我们从1, 1开始。此后，我们把最后两项相加来扩充序列。下面是这个想法的代码形式，在这个基础上是否进行整理取决于你。

综合练习: Fast Fibonacci

计算斐波那契值的最快版本。

• return sequence[n]
• sequence.append(sequence[i-1] + sequence[i-2])
• def Fibonacci(n):
• sequence = [0, 1, 1] # Fibonacci(0) is 0, Fibonacci(1) and Fibonacci(2) are 1
• for i in range(3, n+1):

在下方输入测试语句，例如 print(myfunction("test argument")) 。

因为不需要每次调用的时候重新计算整个数组，所以在这个基础上还有提升的空间。但是这个版本就能够满足我们的要求，n值很大的时候运行也很快！

第2部分：避免计算不重要的事情，一次也不要

第二个例子是关于检查数字是否是质数，这在加密和计算机安全方面非常重要。如果一个数只有两个因子：1和它本身，那么这个数字是质数。从1开始的几个质数是2，3，5，7，11，13，17，19，23（21不是质数因为除了是1和21外，21还有因子3和7）。

Python中如何测试一个数字是否是质数？我们之前讲过如何测试整除性：

N % D == 0  # will be True if D is a divisor of N, False otherwise

下列程序测试所有可能的因子。

示例

测试数字是否是质数

def isItPrime(N): for D in range(2, N): # 测试 D 从 2 到 N-1 if N % D == 0: # D是N的除数么? print(N, "is not prime; divisible by", D) return print(N, "is prime") # 没有除数

在下方输入测试语句，例如 print(myfunction("test argument")) 。

这个程序可以满足我们的要求！但是如果数字很大，这个程序也会很慢。选输入，输入isItPrime(324635459)。你会得到超出时间限制的提示。尝试更多的值……对于大于10000000的质数，这个代码总是超出时间限制，打分器只能以每秒一千万次的速度进行整除性检查循环。如果想检查比较大的数字，我们需要其他更有效率的想法。让我们把代码变得更有效，可以处理十亿以上的数字！

是否有必要检查所有的数字，2和N-1之间，以查看N是否是质数？提示

主意和参数

如果你阅读了提示或者进行了多次尝试，你可能会注意到当N不是质数，这个程序通常能找到一个与N相比相当小的因数。比如，isItPrime(34827948723948723984729834)运行地非常快：尽管数字很大，但找到的因子却是D=2。

或许我们不需要检查所有的因子。但是是否有一些因子我们一定要检查，然后才可以确定N是质数？没错！实际上，我们可以认为如果N不是质数，它的质数最大不超过sqrt(N)。为什么？因为如果N不是质数，那么它就有一个因子A。作为一个因子就意味着还有另一个数字B，使得

A*B == N

让我们继续论证。如果A <= sqrt(N)或B <= sqrt(N)，那么皆大欢喜：我们找到了N的一个比较小的因子。实际上这里只有这些可能：否则，我们就会得到矛盾

N = A*B > sqrt(N)*sqrt(N) > N

那么现在，让我们在Python中施行这个新的主意。改变旧方法的最简单的方法是在for循环中加入一个测试：一旦D > sqrt(N)（或者D*D > N），可以（break）跳出循环，停止测试。

示例

运行速度更快的质数测试

def isItPrime(N): # 和之前的一样 for D in range(2, N): if (D * D > N): # 被加上的第一行 break # 被架上的第二行 if N % D == 0: print(N, "is not prime; divisible by", D) return print(N, "is prime") isItPrime(1000006000009) isItPrime(1666666009999)

这个程序可以处理很大的质数！

最后的练习题

在这个练习中，我们将这节课后半部分的质数与序列为核心的前半部分结合。你的代码应该能够填写一个长为1000001表格，使得如果N是质数isPrime[N]等于True；如果N是合数，就是False。在这里N小于等于一百万（比如，isPrime[0]和isPrime[1]应为False）。

点击这里查看提示。很重要！

编程练习: Primed for Takeoff

编写我们上述描述的程序isPrime（注意isPrime是一个序列，不是方程）。提示
判断器时间限制是7秒，以确保你的程序运行成功。然而，单独使用isItPrime方程还不够快。

你需要创建一个账号并登录才能问一个问题。

更多的动作... 帮助

这是CS Circles网站最后的练习题。恭喜完成所有课程的同学！查看resources page，里面有些建议告诉你接下来可以学什么。希望你可以从中找到乐趣，编写出好程序！祝你好运！