《从问题到程序:用Python学编程和计算》——第3章 基本编程技术 3.1 循环程序设计

本节书摘来自华章计算机《从问题到程序:用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项的计算。例如,数学中有下面公式:

《从问题到程序:用Python学编程和计算》——第3章 基本编程技术   3.1 循环程序设计

现在考虑定义一个函数计算前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的计算,数学家提出了下面无穷级数:

《从问题到程序:用Python学编程和计算》——第3章 基本编程技术   3.1 循环程序设计

现在考虑用这个公式计算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

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

《从问题到程序:用Python学编程和计算》——第3章 基本编程技术   3.1 循环程序设计

级数的首项是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章将讨论从文件输入的问题,届时会看到一些情况。

上一篇:优势特征蒸馏(Privileged Features Distillation)在手淘信息流推荐中的应用 | KDD论文解读


下一篇:黑马程序员 七、集合框架(1)