《从问题到程序:用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项的计算。例如,数学中有下面公式:

image

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

image

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

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

image

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

相关文章
|
2天前
|
设计模式 开发者 Python
Python编程中的设计模式:工厂方法模式###
本文深入浅出地探讨了Python编程中的一种重要设计模式——工厂方法模式。通过具体案例和代码示例,我们将了解工厂方法模式的定义、应用场景、实现步骤以及其优势与潜在缺点。无论你是Python新手还是有经验的开发者,都能从本文中获得关于如何在实际项目中有效应用工厂方法模式的启发。 ###
|
2天前
|
人工智能 Python
[oeasy]python039_for循环_循环遍历_循环变量
本文回顾了上一次的内容,介绍了小写和大写字母的序号范围,并通过 `range` 函数生成了 `for` 循环。重点讲解了 `range(start, stop)` 的使用方法,解释了为什么不会输出 `stop` 值,并通过示例展示了如何遍历小写和大写字母的序号。最后总结了 `range` 函数的结构和 `for` 循环的使用技巧。
11 4
|
2天前
|
算法 测试技术 开发者
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗;代码审查通过检查源代码发现潜在问题,提高代码质量和团队协作效率。本文介绍了一些实用的技巧和工具,帮助开发者提升开发效率。
8 3
|
3天前
|
数据采集 机器学习/深度学习 人工智能
Python编程入门:从基础到实战
【10月更文挑战第24天】本文将带你进入Python的世界,从最基础的语法开始,逐步深入到实际的项目应用。我们将一起探索Python的强大功能和灵活性,无论你是编程新手还是有经验的开发者,都能在这篇文章中找到有价值的内容。让我们一起开启Python的奇妙之旅吧!
|
5天前
|
设计模式 监控 数据库连接
Python编程中的设计模式之美:提升代码质量与可维护性####
【10月更文挑战第21天】 一段简短而富有启发性的开头,引出文章的核心价值所在。 在编程的世界里,设计模式如同建筑师手中的蓝图,为软件的设计和实现提供了一套经过验证的解决方案。本文将深入浅出地探讨Python编程中几种常见的设计模式,通过实例展示它们如何帮助我们构建更加灵活、可扩展且易于维护的代码。 ####
|
1天前
|
数据采集 存储 Web App开发
利用Python 的爬虫技术淘宝天猫销量和库存
使用 Python 爬虫技术获取淘宝天猫商品销量和库存的步骤包括:1. 安装 Python 和相关库(如 selenium、pandas),下载浏览器驱动;2. 使用 selenium 登录淘宝或天猫;3. 访问商品页面,分析网页结构,提取销量和库存信息;4. 处理和存储数据。注意网页结构可能变化,需遵守法律法规。
|
2天前
|
数据库 开发者 Python
“Python异步编程革命:如何从编程新手蜕变为并发大师,掌握未来技术的制胜法宝”
【10月更文挑战第25天】介绍了Python异步编程的基础和高级技巧。文章从同步与异步编程的区别入手,逐步讲解了如何使用`asyncio`库和`async`/`await`关键字进行异步编程。通过对比传统多线程,展示了异步编程在I/O密集型任务中的优势,并提供了最佳实践建议。
8 1
|
1天前
|
机器学习/深度学习 前端开发 数据可视化
解锁Python编程的魔法:从小白到高手的蜕变之旅####
【10月更文挑战第25天】 本文将带你踏上一场别开生面的Python学习探险,不讲枯燥语法,只谈实战乐趣。想象一下,编程不再是冰冷的代码堆砌,而是像组装乐高一样有趣,每一步都充满惊喜。我们将一起揭开Python的神秘面纱,通过几个生动有趣的小项目,让你在不知不觉中掌握这门强大的语言,从此开启你的技术超能力。准备好了吗?让我们边玩边学,成为编程世界的超级英雄! --- ####
7 0
|
5月前
|
Python Windows
Python基础教程(第3版)中文版 第18章 程序打包 (笔记)
Python基础教程(第3版)中文版 第18章 程序打包 (笔记)
|
5月前
|
搜索推荐 区块链 开发者
【python程序打包教程】PyInstaller一键打包Python程序为独立可执行exe文件
【python程序打包教程】PyInstaller一键打包Python程序为独立可执行exe文件