本节书摘来自华章计算机《从问题到程序：用Python学编程和计算》一书中的第3章，第3.1节，作者 裘宗燕，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

第3章

基本编程技术

第2章讨论了简单的计算和编程，展示了一些实例。通过对有关内容的学习，读者应该已经做了一些简单程序，对写程序和做计算有了些实际体会。虽然编程中细节较多，但也是很有趣的工作。为了完成一个程序，首先要分析问题、寻找解决方案，这些需要发挥人的聪明才智和想象力，也可能涉及一些相关领域的知识。要把设计变成可以运行的程序，既需要智力，也需要有条理的工作，一个小错误就可能使程序不能正确执行。当然，高度精确性也是现代社会对人的基本要求，写程序的过程能给我们许多有益的经验。

学习编程要经历一个过程，但这些并不表示这里的学习就是简单的经验积累，也不意味着只要多写程序就一定能把程序写好。人们通过多年的编程实践，总结出许多带有规律性的东西，总结出许多编程的模式、方法和技术，还进一步研究了许多理论问题。在学习编程时，一开始就应该注意前人的经验。正确的好程序不可能是随便写出来的，也不应该是修修补补凑出来的。只有认真学习怎样写好小程序，弄清其中的基本道理，才可能进一步写出更大更复杂的程序。这些都是本书希望特别强调的问题。

在进一步了解Python的其他功能之前，初学者需要更好地理解如何把已有基本知识应用于实际，这就是本章的目的。在三种基本的流程模式和相关语言结构中，顺序模式最简单，用复合语句描述也直截了当。使用选择模式，最重要的问题是正确描述条件，考虑不同情况下的动作，用条件语句实现也不困难。初学编程阶段的主要难点是重复执行模式。这种模式比较复杂，用循环语句实现时牵涉的问题较多，是本章讨论的第一个重点。

本章将首先讨论编写循环的一些基本技术，通过一批程序实例，展示一些典型的循环程序设计。这里的方式总是从分析问题开始，逐步发掘完成程序的线索，最终做出能解决问题的程序，以帮助读者看到“从问题到程序”的思维过程。对于一些问题实例，讨论中给出了能解决问题的多个不同程序，并特别讨论它们之间的差异及优缺点。这样做是希望读者理解：编程不是教条，也不应死记硬背。即使很典型的问题，也没有应该记住的标准解答。只要不是极端简单的问题，总有许多解决方法，可以写出许多形式或实质上或多或少不同的程序，而且它们往往各有长短。当然，也不能说这些程序都有同等价值。实际上，正确的程序也可能有优劣之分，讨论中也会对程序的评价提出一些看法。

在第2节里将介绍一种函数定义技术，称为递归定义，这种技术在处理一些问题时非常有效。最后一节讨论了定义函数的意义和相关的思考和设计问题。本章还将讨论一个非常重要的理论问题：程序的终止性。本章最后还将深入讨论定义函数的一些问题。

3.1　循环程序设计

前面说过，没有循环的程序都是平凡的程序。任何复杂一点的计算过程中必然会出现重复性的计算，需要用循环描述。本节集中讨论基于循环的编程问题。

3.1.1　循环的需求和问题

在程序里写循环，前提是我们发现计算过程中可能需要（或者应该使用）循环。在分析问题时，应该注意识别计算中需要重复执行的类似动作，这种情况说明可能需要引进一个循环，统一描述和处理计算中的一批类似工作。

需要循环的情况

需要写循环，常见情况如需要一批可以按统一规则计算的结果；需要对一系列类似数据做同样处理；需要反复从一个结果算出下一结果等。这些都属于重复性计算，如果重复次数较多，或者次数无法确定，就应考虑用循环。下面是一些典型情况：

1）需要多次执行类似操作而且操作次数较多，适合用循环处理。对这类情况，采用循环通常能缩短程序。用一段公共代码描述公共操作，更容易检查、维护和修改。

2）需要做一些重复性的操作，但在编程时无法确定操作的次数，结束条件由重复工作中数据的情况决定。这类情况就必须通过循环处理。

3）决定重复控制的因素来自函数的参数或程序的输入，也必须用循环描述。

举例来说，假设现在需要制作一个摄氏与华氏的温度对照表，要求从摄氏0度到200度，每5度一项。这就是典型的第一种情况。而前一章里通过牛顿迭代法，以不断改进猜测值的方式求平方根，就是典型的第二种情况。第2章里也给出了一些循环控制依赖于函数的参数或程序输入的例子。

写循环时需要考虑的问题

写循环的第一步是看到计算中需要做一些重复的操作，而且有规律可循，但从发现计算中的重复性动作，到写好一个循环结构，通常也不是直截了当的，还需考虑和解决许多具体问题，考虑问题的基础是计算中需要做什么。

首先弄清楚需要重复做的处理工作，根据它描述循环的主体。另一方面就是循环的控制，要确定怎样开始、怎样继续或停止循环。这里有许多具体问题，包括：

• 为了完成重复性计算，需要为循环引进哪些变量？用什么变量控制循环？
• 循环开始前，这些变量应该取什么值（初值问题）？
• 在循环体里（在一次迭代计算中），哪些变量应该更新，其值应该如何变化？
• 在什么条件下结束（或者继续）循环？
• 循环结束后，如何得到所需的结果？

这些都是本节讨论的重点。还有些具体问题，如需要确定用语言里的哪种结构实现循环等。如前所述，如果需要重复的次数和方式比较清晰，有可能通过一个循环变量和一个迭代器（如range）控制，就应该用for语句实现，因为它更简单清晰。如果写程序时不能确知循环的次数，或循环控制的方式比较复杂，就必须用while语句。

在实际编程中，应该采用最简单、最清晰的循环描述方式，首先考虑用for语句和向上循环（循环变量的值递增）。在这里还应该注意Python的整数范围描述方式及其意义。在Python语言里说“从m到n”时总是指序列m, ..., n-1，也就是数学的区间 [m, n)，左闭右开，包括m但不包括n。Python语言中描述迭代器的range(n)、range(m, n)、range(m, n, d)、描述字符串切片时的参数等，都采用左开右闭的描述方式。后面还会看到许多实例。我们在编程中也应尽可能采用同样的规则。

每个循环都有可能用多种不同的方式描述。举个简单例子，假设现实中要求对13到26的整数循环（实际要求是包括13和26）。显然可以用for循环实现，迭代器描述可以用range(13, 27)或者range(26, 12, -1)。按上面说法，如果没有其他需求，就应该用前者（向上循环）。这类简单情况一般不考虑while。另一个问题，假设需用while写一个循环，要求在变量的值大于20时结束，用n <= 20或n < 21作为条件都是正确的。但按照Python的习惯，人们赞成后者（左闭右开）。

浮点数与循环控制

由于浮点数计算是近似计算，基于浮点数描述循环控制，需要特别关注计算的不精确问题，否则，写出的循环很可能没有反映我们的需求。

首先，range要求一个到三个整数类型的（表达式）参数，不能用浮点数。由于这种规定，在进入用range控制的for语句时，循环的次数就由（当时的）迭代器确定了。在循环里给循环变量赋值不会改变循环的控制情况。例如：

for i in range(0, 10, 2):
    print(i)
    i -= 1

还是会输出0、2、4、6、8。也就是说，在循环过程中，变量i一次次反复从迭代器得到值，每次得到的新值与当时i的值无关。

现在考虑用浮点数控制while循环的情况。用一个实际例子说明有关问题。

假设现在需要写一个函数，求sin (x2 + 1)·cos (x) 在 [0, 3] 区间的数值积分，也就是说，求出函数在这个区间的定积分的数值近似。根据高等数学的知识，可以用区间分割法求得这个近似值。现在考虑一种简单方法，把区间分为100份，基于每个区间左端点的值计算小矩形的面积，累积得到积分值。简单考虑可能写出下面程序：

from math import sin, cos

x = 0.0
value = 0.0
while x != 3.0:
    value += sin(x * x + 1) * cos(x) * 0.03
    x += 0.03
# 这时value的值应是所需结果

这段程序直接反映了区间分割法的数学定义，循环做到x等于3.0结束。然而，如果把这段程序送给Python解释器，执行将陷入无穷循环。原因很简单：浮点数是近似计算，从0开始反复加0.03，加100次后结果通常不是3.0，继续加也不会等于3.0。

这个实例说明，不应该用浮点数的等于关系作为循环结束的依据，因为这样做没有任何保证。改用小于关系，就可以保证循环一定结束：

from math import sin, cos

x = 0.0
value = 0.0
while x < 3.0:
    value += sin(x * x + 1) * cos(x) * 0.03
    x += 0.03

print(value)

这时程序能输出一个结果，但结果对不对呢？[ 具体结果对不对，是否为函数积分的近似值，请读者自己想办法验证（利用Python）。]

要想计算的结果合理，一个基本要求是循环正好做了100次。如果加入一个计数变量，并在循环体里将其加一，最后检查该变量的值，就会发现一个奇怪的情况：这个循环执行了101次，得到的结果显然不对。这里的原因也很简单：由于是近似计算，加100次的结果完全可能大于或小于0.03的100倍。如果仍然小于，就会多循环一次。这个例子说明，用浮点数控制循环的次数，没有准确而清晰的保证。

解决这类问题，还是应该回到用整数控制循环，下面是一种解决方法：

from math import sin, cos

value = 0.0
for n in range(100):
    x = n * 0.03
    value += sin(x * x + 1) * cos(x) * 0.03

print(value)

由于整数计算没有误差，采用这种做法，既保证了正确的循环次数，又保证了所用的函数参数尽可能精确（不会积累舍入误差）。

上面例子反映了用浮点数控制循环的基本问题：计算不精确可能导致错过所考虑的精确值，累积误差可能导致循环控制的错误。总而言之，不应该基于浮点数去描述需要准确控制的循环过程。有些情况应该用浮点表达式控制循环，如前一章求平方根的函数所示，通常用于控制不断进展（逼近）的迭代，还要设置合理的允许误差。

3.1.2　常见循环形式

具体循环的情况千差万别，很难清晰地分类，但我们可以提出一些常见的类型。本节考虑几种典型的循环情况，供读者参考。但是，请不要把这里的分类看作教条，实际程序里的一个循环有可能属于这里的不止一个类型。

简单重复

需要重复地做一批类似的但又相互完全独立的工作，是可能用循环描述的最简单情况。如果这类工作的项数较多，用循环描述比较方便。如果要做的工作项数在编程时无法确定（例如，具体情况与输入有关，或者与函数的参数有关），就必须用循环描述。采用一个描述，除了可能缩短程序外，最大的优势是把有关处理问题集中到一处，便于设计、实现、调整和修改。如果需要，还可以把有关处理定义为函数，引进新的概念。

简单重复的特点就是需要对一批数据（或数据组）中的每一项做完全相同的计算，分别得到结果，并且分别使用。这样，同一循环的不同迭代之间相互无关，反映了原问题中不同工作相互无关的特性。例如，需要反复读入一批同类数据，对每个（或每组）数据分别处理，将得到的结果输出，或以同样方式保存。前一章示例中的温度转换、作业里的各种表格生成，都属于典型的简单重复计算。[ 以同样方式保存，可能牵涉到后面章节介绍的数据组合机制。]

这里的关键是计算或操作采用统一的模式，可以用同一段代码描述，不同计算之间的差异只是一个或几个变量的取值，而这些取值可以按同样的规律产生，或者按同样的方式获得。重复工作的识别和描述都比较简单，写好循环的关键是总结出共同的计算模式，确定循环中变量取值的变化规律。

下面的循环取自第2章的示例：

while True:
    n = int(input("Next int:"))
    if n < 0:
        break
    print("Factorial of", n, "is", fact(n))

它基于用户输入的整数，计算阶乘并输出，其中的数据统一通过输入获得，主要计算都调用同一个函数完成，输出的方式和形式相同，是典型的简单重复模式。另一方面，由于结束条件是根据用户输入确定的，编程时不知道具体循环次数，应该用while结构。

实际上，交互式方式下Python解释器的最高层就是一个简单重复计算：反复读入人的输入（表达式或语句），执行命令，最后输出计算的结果。一般交互式程序的最高层也都是这样，差异只在于输入的形式、功能和计算的实现方式不同。

累积

另一类典型的计算工作是累积，其特点就是在重复性的工作中用一个或几个变量不断积累信息。这里的重复表现为获得有关信息的方式类似，将得到的信息积累到变量里的方式相同。很显然，这种工作适合用循环描述，这种循环可称为累积循环。在这种循环中用于积累信息的变量可称为累积变量。

显然，要想在循环的一次次迭代中不断将信息“记入”累积变量中，在循环开始之前，所用的变量就应该有定义，而且针对具体的累积方式设置好初始值。循环的每次迭代中把一些数据的信息累积到变量里，更新变量的值。作为累积，所赋新值应包含变量原值的信息。而（这些）变量的最终值也就是循环的主要结果，在循环结束后使用。

在与数值有关的计算中，累积中常用的操作如 + 或 ，典型操作如x = x + e，其中e为某个表达式，这类赋值最适合用扩展赋值运算符 +=、= 等描述。这样写，既能使描述简洁，也更好地表现了基于变量原值计算并更新的事实。更一般的累积情况需要特殊的方式，可以考虑定义一个专门的累积函数g，用x = g(x, e)描述更新。

下面看几个累积程序（片段、函数等）的实例。

实际上，在前一章里已经展示过一些累积循环，例如求阶乘函数，其主体就是一个典型的累积循环（现在改用扩展赋值运算符描述）：

def fact(n):
    prod = 1
    for k in range(2, n+1):
        prod *= k
    return prod

这里的累积变量（只有一个）是prod，循环前设置其初值为1，在循环中不断乘以由循环变量k提供的值（统一更新方式），其最终值就是本函数的结果。

注意，对于累积变量，其初值通常都与循环中的更新方式有关。如果更新采用 +=，相应变量的初值通常总是0，如果更新用 *=，相应变量的初值通常是1。也就是说，按数学中的说法，变量的初值常用更新运算的单位元。

现在考虑数项级数中前n项的计算。例如，数学中有下面公式：

现在考虑定义一个函数计算前num项的值。将循环中的累积变量命名为ln2，由于是求和，其初值取0。相应的循环比较规范，通项可以通过一个取值为1到num（包括num）的循环变量n计算，因此可以用for循环实现。

最后一个问题是通项的符号，可以直接用表达式(-1)**(n-1)计算，进一步写出程序已经很简单了。但采用这种做法，每个通项都要进行上述乘幂运算，实际上做了很多乘法。能不能减少这种乘法？可以注意到，这个通项中的下一项的符号总与前一项相反，如果知道当前项的符号，将其乘以-1就得到了下一项的符号。这也是一种信息的累积。

引入另一个累积变量sign，可以写出下面的函数定义：

def ln_2(num):
    ln2 = 0.0
    sign = 1
    for n in range(1, num + 1):
        ln2 += sign * 1/n
        sign *= -1
    return ln2

for i in range(100, 200, 10):
    print("First", i, "term of series for ln 2:", ln_2(i))

最后的循环是做试验，程序执行中将输出：

First 100 term of series for ln 2: 0.688172179310195
First 110 term of series for ln 2: 0.6886223863178897
First 120 term of series for ln 2: 0.688997874401657
First 130 term of series for ln 2: 0.6893158191755918
First 140 term of series for ln 2: 0.6895885067652056
First 150 term of series for ln 2: 0.6898249580908314
First 160 term of series for ln 2: 0.6900319459942255
First 170 term of series for ln 2: 0.6902146544587359
First 180 term of series for ln 2: 0.690377118712483
First 190 term of series for ln 2: 0.6905225267244215

函数以很慢的速度逼近正确值0.693147180559945……。

在实际的计算中，累积工作也可能还有条件，只有满足条件的数据才应该累积。此时，就需要在实现这种计算过程的循环中加入条件判断，只在数据满足条件时才更新累积变量。实际上，这是一类很重要的计算模式，称为生成和筛选。一般情况是，以某种统一的方式不断获得（或者直接枚举出，或者生成、计算出）一些数据，然后用一个筛选条件检查，只将满足条件的数据“记入”累积变量。

下面是一个简单实例。现在希望求出1000以内所有除以7余数为2的数中不能整除3的整数之和。下面的简单循环能实现这一计算：

sum = 0
for i in range(1, 1001):
    if i % 7 == 2 and i mod 3 != 0:
        sum += i

再如，下面程序片段将求出用户输入的前10个偶数之和：

sum = 0
n = 0

while True:
    x = int(input("Next integer: "))
    if x % 2 == 0:
        sum += x
        n += 1
        if n == 10:
            break

这里的数据来自用户输入，程序里用另一个累积变量（计数变量）n记录已求和的数据项数，其值达到10就结束。循环结束后，变量sum的值即为所需。从这个程序里，还可以看到一些新情况：break语句可以嵌套在循环里任意深的条件结构中，在复杂的条件下退出循环。无论结构多复杂，break总是退出最内层循环。

最后这两个例子反映了生成和筛选模式的共性情况：循环体中包含一个生成部分，每次产生一项候选数据；而后有一个筛选部分，从得到的数据中选出满足条件的合格数据。有一些实际情况，其中很难直接生成所需要的数据（数据序列），这时可以考虑找一种较为简单的生成方式，得到一个更大的数据序列，再从中选出实际需要的数据。

递推

递推是一种更一般的循环计算模式，在循环的每次迭代中，基于某个（或者某些）变量的当前值，按某种特定方式算出该变量的下一个值。在实现递推的循环中，循环体里总有一个或者一组语句实现如下形式的计算：

d = f(d, ...)

也就是说，变量d的下一个值需要通过d本身（和其他数据），利用某种方法计算出来。这种操作实现从d的现值推出其下一个值。这种d也称为递推变量。实际上，累积也可以看成一种简单而且规范的递推，其计算规则简单而直接。

递推变量也需要初值，必须在循环之前给定。有时在一个循环中有可能有多个递推变量，它们相互扶持、同步前进。某个或某些递推变量的最终值就是需要的结果。要写好一个递推循环，需要做几件事情：

• 选定循环中使用的递推变量；
• 确定这个（这些）递推变量的初值；
• 确定如何从已知信息（包括递推变量的当前值）计算出各个递推变量的下一个值的方法，用程序语句实现相关计算。

第2章中求x平方根的程序包含一个典型的递推循环。递推变量guess以1.0作为初值，通过不断应用迭代规则推出下一个猜测值，最终得到一个满意的近似值。下面修改过的函数能显示出递推的收敛情况：

def sqrt(x):
    guess = 1.0
    n = 0
    while abs(guess * guess - x) > 1e-8:
        guess = (guess + x/guess)/2
        n = n + 1
        print(str(n) + "th iteration:", guess)
    return guess

求sin函数的值

考虑函数sin的计算，数学家提出了下面无穷级数：

现在考虑用这个公式计算sin函数的近似值，要求算到级数项的绝对值小于1e-6。

由于级数项的结构比较复杂，可以考虑定义一个独立的函数计算它。再根据上述级数定义计算sin的函数，程序写出如下：

def term(x, n):
    t = (-1)**n * x ** (2 * n + 1)
    for i in range(2, 2 * n + 2):
        t /= i
    return t

def mysin(x): # 自己定义的计算sin的函数
    sn = 0.0
    n = 0
    while True:
        t = term(x, n)
        if abs(t) < 1e-6:
            return sn
        sn += t
        n += 1

函数term里的循环实现除以 (2n+1)!的计算。我们不希望在函数mysin里两次计算同一个项，这里采用先算出项值存入变量，而后检查和使用的方法。通过几个常见值的计算，可以看到这个函数定义应该没错：

>>> mysin(0.0)
0.0
>>> mysin(pi/2)
0.999999943741051
>>> mysin(pi)
-7.727858895417119e-07

仔细思考上面程序实现的计算过程，其中最重要的部分就是反复算出一个个项的值。可以想到，这里级数项的计算中出现了许多重复计算：在后一项的计算中，大部分工作都是计算前一项时已经做过的。不难写出级数项之间的递推关系：

级数的首项是x，根据递推公式可以算出随后的各项。

把这个递推关系融合到mysin的定义里，修改后的函数定义如下：

def mysin(x):
    sn = x
    t = x
    n = 0
    while True:
        n += 1
        t *= - x * x / (2*n) / (2*n + 1)
        if abs(t) < 1e-6:
            return sn
        sn += t

通过检查运行，可以看到这个函数得到的结果与前一个定义相同。在这个函数的执行中避免了大量重复工作，这件事在实践中非常重要。

有趣的是，做更多的试验却可能发现问题：

>>> mysin(10*pi)
0.00034023652139616377
>>> mysin(20*pi)
-4562371877.727803

用更大的值计算，情况更甚。数学上的sin是周期函数，上面计算的正确结果都应该是0，但为什么会出现误差越来越大的情况？对20π的计算结果已经毫无意义了，但为什么会出现这种情况？罪魁祸首应该是计算误差，但误差为什么会积累到这种程度？请读者仔细分析这两个表达式的计算过程（提示：请考虑利用Python做些试验）。

要解决上述问题，一种可能方法是用数学包里的fmod函数对参数规范化，因为sin (x) = sin +(x + 2nπ)，可以先把实参归结到 [0, 2π] 的范围内。修改后的定义如下：

from math import fmod, pi

def mysin(x):
    x = fmod(x, 2*pi)
    sn = x
    t = x
    n = 0
    while True:
        n += 1
        t *= - x * x / (2*n) / (2*n + 1)
        if abs(t) < 1e-6:
            return sn
        sn += t

下面是几个计算实例：

>>> mysin(100*pi + pi/2)
0.999999943741051
>>> mysin(-pi/2)
-0.999999943741051
>>> mysin(-pi)
7.727858895155385e-07

可以看到，上面的问题不再出现了。

这个例子反映出几个问题：

• 程序完成后的测试必须比较充分，不仅应该包括最简单的数据实例（如前面的0，pi/2，pi等），还要选择一些不那么常规，但也可能出现的数据实例。
• 在浮点数计算中，误差的积累有可能使结果完全失去价值。对于实际程序里与浮点数有关的部分，必须针对可能情况做充分的测试。
• 选择测试实例，应该找那些容易判断结果正误，但又能反映测试需要的实例。

判断素数

素数是非常重要的基本数学概念：如果一个大于1的自然数除了1和其自身以外没有其他因子（没有真因子），它就被称为素数（或者质数）。

自然数n的因子，就是能整除n的正整数。而所谓k整除n，也就是说n除以k的余数为0。在Python里，这一条件可以用表达式n % k == 0描述。

根据上面定义，可以直接得到一种朴素的素数判断方法：对给定的自然数n，取从2开始的一些整数，逐个检查它们是否为n的因子。如果发现了n的真因子，那么n就不是素数。如果一直没有发现真因子，而且做的试验已经足够多，已经能确定n不可能有真因子, 就可以结束检查并断定n是素数。

要实现这个判定方法，可以用循环描述检查的过程。循环中从2开始检查，最简单的方法是从小到大检查每一个整数。采用这种做法，剩下的问题就是检查到什么时候结束？

从2一直检查到n肯定可以做出正确判断，但稍微考虑就能看到一个事实：如果n有真因子，那么它一定有小于等于n的平方根的真因子（请读者自己证明这个结论）。这样，检查循环只需进行到等于或者超过了n的平方根。[ 显然，这样的检查过程中会做很多不必要的工作，但都比较简单。改变检查的方式可能需要存储一些信息，需要有更高级的数据设施。后面还会讨论这个例子。]

基于上面考虑定义出的判断函数（谓词）is_prime如下：

def is_prime(n):
    if n < 2:
        return False
    k = 2
    while k * k <= n:
        if n % k == 0:
            return False
        k += 1
    return True

术语谓词是指返回逻辑值（真假值）的函数，它们通常用于完成程序中的判断，经常被用在条件语句或者循环语句的头部。

基于函数is_prime，很容易写出一个程序，检查一定范围内的偶数，看看哥德巴赫猜想是否成立。例如下面循环检查直至200的偶数：[ 哥德巴赫猜想是数论中的著名猜想，它断言：任何一个大于等于6的偶数都可以分解为两个奇素数之和。我国数学家，特别是陈景润，在有关哥德巴赫猜想的研究中取得了举世瞩目的成果。但是，这个猜想至今还没有被证明或证伪。]

for n in range(6, 201, 2):
    for i in range(1, n//2 + 1, 2):
        if is_prime(i) and is_prime(n - i):
            print(n, "=", i, "+", n-i)
            break

请读者通过试验考察前面素数判断函数的工作效率。不难看到，随着整数值的增大，该函数得到结果的时间越来越长。这件事很自然，例如，对于一个100位的整数，用上面函数判断，过程中需要检查1050个数，显然太耗费时间了。

在有关数论的研究中取得了很多与素数有关的成果，其中一些成果有可能用于素数判断。基于有关成果，人们提出了一些不同的算法。在网上可以搜索到许多情况。建议读者自己找到一些有趣的算法，也可以自己实现一下，作为编程练习。

最近对于素数判断有一个重要进展，2002年印度科学家提出了一个新算法，用发明者的名字首字母缩写命名，称为AKS算法。该算法在理论上优于已有其他算法。

素数判断在许多计算领域中有重要的应用，特别是在密码和安全领域。素数问题及其算法已经成为今天计算机和信息系统安全的基础。

3.1.3　输入循环

与输入有关的循环是程序里的一类常见循环。在这种循环中，程序不断从外部获得数据，并将其用于内部的计算，得到了足够多的数据后结束循环，继续进行循环之后的工作。考虑这类循环的控制和结束，可以看到下面两种典型情况：

• 在编程时已经明确知道需要输入的数据的项数情况。循环中只需一项项读入数据，完成输入后结束。这种输入循环完全由程序内部控制，是最简单的循环输入情况，相关编程中没有新问题。当然，这种循环输入也存在一些变形，见下。
• 编程时只知道需要从外部输入一批数据，但并不确知输入数据的具体项数。前面说过，这种情况只能通过循环描述。这里的新问题是如何确定循环应该结束。显然程序执行中应该反复循环，直到使用者认为应该结束的时刻。也就是说，这是一种由程序外部控制的输入循环，应称为由输入控制的循环。

下面分别讨论与输入有关的这两类循环。

简单输入循环

简单输入循环完全由程序内部确定，这种方式适合在写程序时就能确定方式的循环。当然，具体方式需要根据实际情况来设计。

例如：假设现在要求获得一年中各月的降雨量数据，求出全年的降雨量。显然，这个计算需要正好12项数据。假设数据由用户通过键盘输入，下面程序段能解决这个问题：[ 实际中可能是由其他来源取得数据，例如数据来自已经存在于计算机系统里数据文件，或者来源于网络。虽然获取数据的方式可能不同，但所需循环的形式相同。]

print("Calculating year's rainfall")
rainfall = 0.0
for i in range(12):
    x = float(input("Rainfall of a month: "))
    rainfall += x
print("The total amount of the year", rainfall)

对于这类简单循环，体代码段的重复执行次数事先已知，原则上说，完全可以将其展开，用该段代码的一串拷贝实现同样功能。用循环描述只是使代码大大简化，写起来也更方便。此外，在这种循环里，输入只作为信息源，没有扮演任何特殊角色。

此类简单循环也有一些可能的扩充方式。一类典型问题是需要从输入中筛选出“合格”数据，换句话说，假定实际输入中只有一部分数据满足要求，处理过程中需要把“不合格”的数据筛选丢掉。看一个例子。

【例】假定需要输入一系列数值，求出其中前10项非负数据的平均值。

首先，问题描述已经说明了输入中可能出现数据为负的情况，而且负数是无用数据，在考虑平均值时应该丢弃。进一步说，虽然程序要求处理10项数据，实际输入数据的项数却不可知。还有，在同一程序的不同运行中，需要实际输入的数据项数可能不同。这些情况说明两点：首先，这个程序必须用循环实现；其次，for语句不能处理这种情况，只能用while循环，而且需要自己记录实际获得的有效数据项数。

把上述问题都考虑清楚后，可以很自然地写出下面的程序：

print("Calculate average of 10 input positives.")
sum0 = 0.0
num = 0
while num < 10:
    x = float(input("Next number: "))
    if x > 0:
        sum0 += x
        num += 1
print("Average of 10 positives:", sum0 / num)

这里有一个问题值得提出：最后一个语句里写的是sum0 / num，写成sum0 / 10好不好？显然，对于所给的问题，这两种写法都能得到正确结果。但如果把这个num改为10，程序里就出现了两个10，而且它们必须保持一致。如果问题需求有变化，实际情况要求处理12项（而不是10项）数据，我们就必须把这两个10统一改为12。少改一个程序就错了（逻辑错误），而且不会有任何错误信息。这是很危险的。采用上面程序里的做法，需求变动时，只需要做一处修改，循环结束时总能得到正确的平均值。

细心的读者可能注意到另一个情况：程序里的两个输出字符串中也有10的信息。这件事也可以解决，请读者自己设法修改上面程序。

输入控制的循环

现在考虑另一种常见情况：需要以某种方式统一处理用户输入的一批数据，但并不知道用户将提供多少项数据。显然，这种情况只能通过循环，在反复执行中处理输入。但是，如何控制循环的执行和结束，还是一个需要解决的问题。

这里的情况意味着输入提供方（用户）可以输入任意多项数据，可以*决定在任何时刻结束输入。在这种情况下，显然，处理输入的程序不能自行决定结束循环，只能被动地接受用户决定。而另一方面，用户希望结束的意图也只能通过输入传给程序。这就意味着我们需要为用户提供一种表达实际数据结束的方式，而且必须采用某种特殊的输入形式。这样安排之后，程序在运行中不断读入并检查得到的数据，区分两种情况：确定是正常输入时按正常方式处理，一旦遇到表示结束的特殊输入就结束循环。

这种循环的模式应该是：

while True:
    data = input(…)
    if data是表示结束的特殊输入:
        break
    正常输入的处理

如果一个程序在运行中不断与使用者交换信息，它就是我们一再说到的交互式程序。使用者启动这种程序之后，程序将反复向使用者要求信息。如果得到符合需要的数据，它就完成一定的工作，而后重复这种循环，直至遇到某种预先确定应该结束的情况。显然，交互式程序中通常都会有一个或多个输入循环，可以是内部控制的输入循环，也可以是输入控制的循环。任何输入控制的循环都需要确定一个表示结束的特殊输入。

这种表示正常输入结束的特殊输入（特殊命令），实际上是程序与使用者之间的一种约定。使用者需要知道这种约定，藉此表达他们的输入结束要求。程序也知道（并处理）这种约定，遇到结束信号时就结束循环。作为编程者，需要设计这种约定，在程序里加入对它的检查，并且告知程序的使用者。这种约定是程序使用方式的重要组成部分。作为一个具体例子，如果在Python IDLE的交互状态下调用函数quit()或者exit()，Python解释器的交互窗口就会结束执行。这就是IDLE（的设计者）与我们的约定。

为实现一个具体的这种循环，我们必须设定一种具体约定。显然，任何正常（正确）的输入数据都不能作为结束循环的信号。例如，对于一个要求输入一串整数的程序，我们不能用0作为结束循环的特殊输入；但如果程序要求的是一串正整数，用0或者负数作为结束信号就都是合理的设计。如果程序的功能是对一系列输入数值做一些统计工作，例如求它们的平均值和其他统计计算，那么任何合乎Python对数值转换要求的输入都是合法数据，因此不能以数值判断作为结束判断。Python的input函数返回输入串，要求程序做转换。因此这时就可以考虑用其他形式的字符串作为结束标志，例如：

while True:
    item = input("...")
    if item == "end":
        break
    data = float(item)
    正常输入的处理

这样写程序，也就是约定用字符串end作为结束标志。为方便用户，提示符串可以考虑用 "Please give next number, 'end' to finish."。相应程序可以写出如下：

print("Calculating average.")
ss = 0.0
n = 0
while True:
    snum = input("Next number ('end' to stop): ")
    if snum == "end":
        break
    ss += float(snum)
    n += 1
print("The average of these " + str(n) + " numbers is", ss/n)

下面是另一个简单的实例：

name = ""
while name != "no more":
    name = input("Hi, friend! What is your name? ")
    print("Hello, " + name + "!\n")

这个循环要求输入是字符串，用特殊字符串no more表示不再有更多人名输入了。最后的输出语句里用到字符串拼接，是为了做出符合需要的输出形式，避免多个输出项之间不必要的空格。注意，这里假设了用户的输入是人名，而人名就是字符串。由于编程时选定的结束约定，如果有个人名叫no more，程序就无法对其表达问候了。

为避免表示结束的字符串不能正常处理的问题，可以考虑另外安排一个输入，专门处理有关结束的字符串。例如，把前面程序改为：

while True:
    name = input("Hi, friend! What is your name? ")
    print("Hello, " + name + "!\n")
    yesno = input("Next? (Yes/No): ")
    if yesno == "No":
        break

在这个循环里，实际数据和控制循环的输入是分开考虑的。

在实际应用中，输入未必是字符串，可以是任何数据，甚至可以是若干数据项的组合。另一方面，处理数据的操作也可以任意复杂。上面两个例子展示了最常用的两种控制方式：或者是基于数据输入自身，或是引入专用于控制是否继续的输入。

正如前面的脚注所言，实际程序可能有不同的输入源。例如程序的输入可能来自文件，或者来自网络，这些输入也经常需要通过循环处理。虽然输入源可能不同，但都会遇到上面讨论的问题，都需要有表示输入结束的约定和相应处理。后面第6章将讨论从文件输入的问题，届时会看到一些情况。