《从问题到程序:用Python学编程和计算》——2.8 重复计算和循环-阿里云开发者社区

开发者社区> 华章出版社> 正文

《从问题到程序:用Python学编程和计算》——2.8 重复计算和循环

简介:

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

2.8 重复计算和循环

在前面几节,我们首先看到如何通过语句的顺序组合构造最简单的程序,这种程序是直线型程序,就是简单的一系列语句。这样的程序中只有一条执行路径(一种可能执行方式):Python解释器顺序执行程序里的语句,每个语句执行一次,当语句序列中最后一条语句的执行结束时,整个程序的执行就结束了。

增加了if复合语句,能写出的程序更多,程序的形式也更丰富,其中出现了选择和分支。这样得到的程序可称为分支程序。在分支程序里,每条基本语句最多执行一次,如果实际条件导致的执行没进入某个分支,该分支里的语句就不会执行。这说明在处理不同数据时,实际执行的语句序列(执行路径)有可能不同,存在多条不同执行路径。但事情也很清楚,一个分支程序里的所有可能执行路径是可以列举出来的。

直线型程序和分支程序的描述比较简单,能完成的工作也简单,只是一组基本操作(包括表达式求值、变量赋值、输出输入等)的顺序组合。注意,分支只是表达了对不同基本操作或操作序列的选择。程序里的每个基本语句至多执行一次,程序的长度(语句的总条数)是所有执行路径长度的上限。这样,程序的功能就受到程序长度的限制,能完成的工作只是程序里基本操作的不同组合。我们写程序用了很多时间,解释器一瞬间就执行完了。要使写出的程序能完成更复杂的计算,就必须突破这种状况。

2.8.1 重复计算

最基本的复杂计算就是重复计算,例如:

  • 求1到10的整数之和;
  • 求2到30的偶数之乘积;
  • 求1 – 1/3 + 1/5 – 1/7 + 1/9 …– 1/19,等等。

这里的基本情况是:

  • 需要做一系列重复性的计算;
  • 计算中需要做的操作有规律,可以说清楚。

需要重复计算的情况很多,可以举出其中的一些类别。最简单的一类情况是写程序时能确定需要重复的次数。对这类情况,通过一个可能较长的表达式,或者通过一系列语句,可能描述这种重复计算。例如求1到10的十个整数之和,可以写:

s = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
print("The sum is", s)

或者

s = 0
s = s + 1
s = s + 2
s = s + 3
s = s + 4
s = s + 5
s = s + 6
s = s + 7
s = s + 8
s = s + 9
s = s + 10
print("The sum is", s)

但是,这些写法都太繁琐,也不能处理一般情况。按前面的说法,对连续的一个整数区间里的值求和是一个计算问题,求1到10的整数之和是其具体实例。上面程序只是解决了一个具体实例,没有太大用。而实际中可能有不同的情况和需要。例如,要求和的整数区间可能由输入得到,按上面方式就无法写出解决问题的程序了。当然,对上面这个简单问题,存在求和公式,但这种情况并不具有一般性。

计算中需要做重复性工作是计算的本质,各种编程语言(包括Python)都为描述重复计算提供了专门的结构,称为循环结构或循环语句。循环语句是Python里的一类复合语句,其性质与顺序和分支结构不同。在一个循环语句的执行中,其成分语句可能被多次执行,这就使很短的程序可能导致非常长的操作执行序列。

Python语言里有两种循环语句:for语句用于描述比较简单比较规范的循环;while语句用于描述一般的复杂循环。它们都控制一个语句组的重复执行。

2.8.2 for语句和重复计算

for语句用一个循环控制器(在Python里称为迭代器)描述其成分语句组的重复执行方式。其基本语法形式是:

image

for和in都是关键字,语句中包含了三个成分,最关键的是迭代器。由关键字for开始的行称为循环的头部,语句组称为循环体。与if语句的情况类似,这里语句组中的语句也是下一层的成分,同样需要退格,组中各语句必须相互对齐。

迭代器是Python语言里的一类重要机制。一个迭代器描述一个值序列(也就是说,一系列的对象),可以在一些特殊上下文中使用,例如用在for语句的头部。for语句的语义是:让变量顺序取得迭代器表示的值序列中的各个值,对每个值执行语句组一次。由于循环体里可以使用头部引进的变量,在循环体每次执行时,该变量的值可能不同,所以,虽然反复执行的是同一段语句,但每次执行的效果却可能不同。

下面是使用for语句的一个简单实例,它求出0到99这100个数之和:

s = 0
for x in range(100):
    s = s + x

这个for语句的循环体里只有一个语句,每次执行把变量x的值加在变量s原有的值之上,在循环语句开始执行前给s赋值0。

要理解上述程序段,最重要的问题就是range(100)的意义。range是Python的一个内置函数,调用这个函数,就能得到一个迭代器(因此适合放在for语句头部)。函数range有几种不同调用方式,不同方式得到的迭代器情况如下:

  • range(n) 得到的迭代器表示序列0, 1, 2, ……, n-1。因此range(100) 表示序列0、1、2、……、99。
  • range(m, n) 得到的迭代器表示序列m, m+1, m+2, ……, n-1。例如range(10, 16)表示序列10、11、12、13、14、15。
  • range(m, n, d) 得到的迭代器表示等差序列m, m+d, m+2d, ……,按步进值d递增(如果d为负就是递减),直至那个最接近但不包括n的等差值。例如,range(10, 16, 2) 表示的序列是10、12、14,而range(15, 4, -3) 表示的序列是15、12、9、6。

对于range(n),在n不大于0时序列为空。如果用这样的迭代器控制for循环,其循环体将一次也不执行,整个for语句立即结束。对于range(m, n),如果m≥n则序列为空。对于range(m, n, d),d可以是正整数或负整数,表示增量是向上或者向下,也可能出现空序列的情况。很容易看清楚,这里range函数的参数也描述了一个左闭右开的区间(或等差序列区间),与字符串切片的情况类似。

在上面for循环的循环体里,只写了一个给变量s赋值的语句。实际执行时,每次执行这个语句就会给s赋一个新值。在循环中反复修改(更新)一个或几个变量的值,是程序里最常用的一种技术。下面会看到很多这样的例子。易见,简单修改程序中range函数的参数,同一个程序就能完成对不同整数区间的求和。进而,用变量控制迭代器的范围,同一个程序就能在不同的执行中完成对不同整数区间的求和。这些说明,有了循环语句,我们对计算机的工作方式和过程进行控制、安排其执行方式的能力大大增强了。

下面是一个一般的等差整数序列的求和程序:

a = int(input("Start from: "))
b = int(input("End at: "))
c = int(input("Step: "))

s = 0
for n in range(a, b+1, c):
    s = s + n

print("The sum is", s)

这里range的参数用b+1,因为range产生的序列总不包括这个参数值。

现在考虑一个实际问题:通过输入指定对照表的范围和温度值间隔,生成摄氏与华氏温度的对照表。一方面,这个问题与前一个类似,要求对一系列值做同样计算。但又不同,其中对不同值的计算相互无关,只是用了同一个计算公式。

从摄氏温度C到华氏温度F的计算公式是:

F = C ×9/5+32

很容易写出下面程序:

begin = int(input("Start from: "))
end = int(input("End at: "))
step = int(input("Step: "))

for x in range(begin, end, step):
    print(x, "->", x * 9 / 5 + 32)

如果这个程序运行时依次输入0、50、10,它将输出:

0 -> 32.0
10 -> 50.0
20 -> 68.0
30 -> 86.0
40 -> 104.0

考虑另一个计算问题:求阶乘。由数学可知,正整数n的阶乘是:

n! = 1×2×…×n

0的阶乘定义为1。完成这个计算需要乘起一系列整数,直至某个在写程序时不能确定的n。这种工作必须用循环处理。在重复计算中需记录不断增长的部分乘积,使用一个变量。

基于for循环实现这一计算,还需要确定range的调用方式,做出正确的迭代器(生成正确的整数序列)。考虑了各种情况后写出的程序如下:

n = int(input("Factorial for: "))

prod = 1
for i in range(2, n + 1):
    prod = prod * i

print("The factorial of", n, "is", prod)

如果认为需要,也可以加入检查输入的结构。这里实际上假设了输入是非负整数,如果输入的n值是0或1,range(2, n + 1) 生成的迭代器产生空序列,循环立即结束,结果正好为所需。用range(1, n + 1) 也对,不改变程序的意义。

下面程序重复三次要求输入和求阶乘的计算:

for i in range(3):
    n = int(input("Factorial for: "))

    prod = 1
    for j in range(2, n+1):
        prod = prod * j

    print("The factorial of", n, "is", prod)

在这段程序里,一个for循环的循环体里出现了另一个for循环。由于for循环也是语句,可以出现在任何要求写语句的程序结构里,包括循环体。有人把这种情况称为嵌套循环,或者多重循环。实际上,这种情况并不特殊。

在执行中,上面程序与用户交互三次,每次通过输入得到一个整数,完成阶乘计算后输出一个结果。这是一个简单的阶乘计算器,只能做3次阶乘。

最后再强调一下,内置函数range的使用,实际上反映了Python有关一个值序列描述的原则:描述的总是左闭右开的序列。后面还会多次遇到类似的情况。

2.8.3 while语句和迭代

另一种循环语句是while语句,它用一个表示逻辑条件的表达式控制循环,在条件成立的情况下反复执行循环体,直至条件不成立时结束。while语句的形式很简单:

image

解释器执行while语句时首先求值其条件表达式,如果值为真就执行循环体语句组一次,然后重复上述动作;表达式的值为假时while语句立刻结束。

显然,while语句可以实现for语句能实现的所有计算,例如,不难基于while语句写出另一个求阶乘的程序,其中用一个变量记录不断增长的乘数:

n = int(input("Factorial for: "))

prod = 1
i = 2
while i <= n:
    prod = prod * i
    i = i + 1

print("The factorial of", n, "is", prod)

与前面采用for语句的程序相比,采用while语句时,必须自己管理循环中使用的变量i,自己做增量操作。这样写出的程序不如前一个简单。

如果循环比较规范,循环中的控制比较简单,事先可以确定循环次数,人们提倡用for语句而不用while语句,因为用前者写出的程序往往更简单,也更清晰。但是,也有一些循环无法用for语句写出,必须用while描述。

举个例子说明这种情况。现在计划开发另一个更好的阶乘计算器,希望它能任意次地接受输入并计算阶乘值,直至用户希望结束为止。

这里的情况与前面三次计算阶乘的程序有些类似,需要把一段计算阶乘的代码包在一个循环里。但是现在循环次数无法事先确定,而且,这个程序每次执行中需要计算阶乘的次数有可能不同,根据用户的需要确定。另外,我们也不要求用户在程序开始时先决定计算的次数,并把这个次数告知(通过输入)计算阶乘的程序,而是允许用户在程序工作中随时提出结束的要求。为了处理这种情况,我们需要给用户提供一种表达结束的方式。由于负数的阶乘没有定义,我们可以规定一旦用户输入负数,循环就结束,而是否为负数就是计算器继续工作(重复执行)的条件,可以用一个while语句描述。

确定了上面的问题解决方案之后,写出程序已经不困难了:

print("This is a factorial calculator. -1 to stop.")
n = int(input("Factorial for: "))

while n >= 0:
    prod = 1
    for i in range(2, n+1):
        prod = prod * i

    print("The factorial of", n, "is", prod)
    
    n = int(input("Factorial for: "))

print("Bye!")

下面是本程序一次执行的情况:

>>> 
This is a factorial calculator. -1 to stop.
Factorial for: 10
The factorial of 10 is 3628800
Factorial for: 5
The factorial of 5 is 120
Factorial for: -1
Bye!

这是一个典型的交互式的计算程序,它不断要求输入,得到一个整数就做计算,而后输出结果。实际上,这个程序可以看作是一台专用的计算机——阶乘计算机,其行为恰如第1章的图1.2所示。这台计算机的命令就是正整数,任何负整数都是它的停机命令。它的功能就是一条条地执行“指令”(计算阶乘)并输出结果。

上述程序有一个缺点:同样的输入语句在程序里写了两次。多次重复写同样代码是不好的现象。以上面程序为例,如果我们想修改提示符,就需要在两个地方同时改,还需要维护一致性。这种情况应该尽可能避免。然而,采用直至目前已经介绍的机制,上面程序的问题还没有解决办法。后面介绍的Python功能可以解决这个问题。

还有一大类计算问题需要使用while循环。对于这类问题,人们通过研究设计出一套反复计算的规则,称为迭代规则,并证明了反复使用规则就一定能得到解,但何时结束要看实际计算的实际进展情况。下面考虑一个具体问题。

现在考虑求实数平方根的问题。人们提出的计算规则如下:

0.假设要求实数x的平方根,任取y为某个实数值
1.如果y×y=x,计算结束,y就是x的平方根
2.令z=(y+x/y)/2
3.令y的新值为z,转回步骤1

通过这样反复计算,可以得到一个y值的序列。人们已经证明这个序列将趋向于x的平方根。这种方法称为计算平方根的牛顿迭代法。

根据上述方法可以直接写出一个程序,显然其中需要循环。程序如下:

x = float(input("Square root for: "))

guess = 1.0

while guess * guess != x:
    guess = (guess + x/guess)/2

print(guess)

这里的guess表示对平方根的猜测,在循环的反复迭代执行中,这个猜测值被不断改善,在其平方不等于x的情况下继续改善。

上述程序的写法应该没错(很简单,是牛顿迭代法的直接翻译),运行后给输入2.0,我们会发现程序一直不能给出结果,看来可能是进入了死循环。在IDLE里可以通过Ctrl-C组合键中断正在执行的程序。现在修改程序,在循环中加一个输出语句:

x = float(input("Square root for: "))

guess = 1.0

while guess * guess != x:
    guess = (guess + x/guess)/2
    print(guess, guess * guess)

print(guess)

可以看到,程序反复输出同样信息(在作者机器上是1.414213562373095 1.9999999999 999996),变量guess的平方总也不能恰好等于2.0,循环无法终止。

实际上,这里遇到的也是近似计算带来的问题。由于2.0的平方根是无理数,浮点数只能表示其近似值,而且精度有限,再加上所做的乘法是近似计算。两者叠加,迭代中变量值的平方总不能等于2.0,导致循环永远也无法结束。

浮点数计算是近似的,使用浮点计算,只能希冀得到近似的结果。由于这个情况,对求平方根问题,我们只能考虑在guess的平方足够接近x时结束,不能用等于判断。例如,可以取两者误差的绝对值不超过10-8。基于这个想法,很容易写出下面程序:

x = float(input("Square root for: "))

guess = 1.0

while abs(guess * guess - x) > 1e-8:
    guess = (guess + x/guess)/2

print(guess)

对给定浮点数,这个程序很快就能算出结果。这里的abs是前面介绍过的Python内置函数,它求出参数的绝对值。显然其参数应该是数值。

为了了解程序迭代的情况,我们可以修改程序,让它多输出一些信息:

x = float(input("Square root for: "))

guess = 1.0
n = 0

while abs(guess * guess - x) > 1e-8:
    guess = (guess + x/guess)/2
    n = n + 1
    print(n, guess)

print(guess)

这里增加了一个计数变量,帮助统计循环的次数,用print同时输出当时的guess值,使人可以看到猜测值逼近最终结果的过程。对浮点数2.0的试验情况如下:

Square root for: 2.0
1 1.5
2 1.4166666666666665
3 1.4142156862745097
4 1.4142135623746899
1.4142135623746899

迭代4次就得到了结果,说明牛顿迭代法计算收敛得非常快。读者可以修改程序的精度要求,或者换一些其他数值做试验,观察程序执行情况的变化。

Python的一个优点是很容易做各种计算试验,本质上是利用计算机可编程的优点。但Python语言的设计使人在做这些事情时非常方便。读者可以自己考虑一些有趣的计算问题,做些试验,观察分析计算中的情况和问题。

2.8.4 循环控制

for语句和while语句都是通过头部控制循环的进行,一旦执行进入循环体,就会完整地执行一遍其中的语句,然后再重复。实际中也存在一些情况,其中在一定条件下应该只执行循环体的一部分,然后就退出循环,或者立刻转去做循环的下一次迭代。为了满足这类需要,Python提供了两个特殊的循环控制语句。

循环中断语句的形式很简单,只是一个关键字break。如果在循环体的执行中遇到这个语句,当前的循环语句立刻结束,解释器转到循环之后的语句。

循环继续语句的形式也很简单,就是一个关键字continue,如果在循环体执行中遇到这个语句,循环体的本次执行结束,执行回到循环头部,根据头部的要求继续。

显然,这两个语句都只能出现在循环体里面,而且只能控制包含着它们的最内层循环语句(请注意,循环可以嵌套)。此外,这两个语句通常总是出现在某个条件语句里,在一定条件下才做相应的动作。两者中break使用得更广泛一些。

现在考虑前面遗留的一个问题,利用break改造前面的阶乘计算器,消除其中重复的语句。由于用break可以从循环的中间退出,下面程序能完成同样的工作:

print("This is a factorial calculator. -1 to stop.")

while True:
    n = int(input("Factorial for: "))
    if n < 0:
        break
    
    prod = 1
    for i in range(2, n+1):
        prod = prod * i

    print("The factorial of", n, "is", prod)
    

print("Bye!")

这里的循环条件是True,表示条件永远成立,这个循环不会由于头部检查而结束。但由于在循环里出现了带条件的break语句,一旦其条件成立,循环就会结束。因此,不能说这是一个死循环,只要计算中break的条件成立,循环就会结束。对于这个例子,只要用户输入小于0,执行就会到达break语句,循环就结束了。

后面会看到更多使用break的例子,也可以看到使用continue的例子。

版权声明:如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:developerteam@list.alibaba-inc.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:

华章出版社

官方博客
官网链接