从零开始学习PYTHON3讲义(六)

for循环跟斐波那契数列

《从零开始PYTHON3》第六讲

几乎但凡接触过一点编程的人都知道for循环,在大多数语言的学习中,这也是第一个要学习的循环模式。
但是在Python中,我们把for循环放到了while循环的后面。原因是,Python中的for循环已经完全不是你知道的样子了。

for循环

以c语言为例,for循环几乎是同while循环完全相同的功能。在Python中,for循环经过全新的设计,实际只支持一个功能,当然也是编程最常用到的功能,就是“遍历”。
所谓遍历(Traversal),是指沿着某条确定的搜索路线,依次对序列中的每个结点(每个元素)均做一次且仅做一次访问。
比如最常见的字符串,实际就是一个序列。字符串“abcdefg”,中间包含7个字母,每个字母就是一个结点。“沿着某条确定的搜索路线”,其实指的就是按照何种规则来顺序访问字符串中的每个结点。最常见的可以使从开始到结尾,或者从结尾到开始。
我们先使用while循环来做一个字符串的遍历:

s="abcdefg"
i = 0
while i < len(s):
    print(s[i])
    i += 1

在这个例子中,我们先定义了一个字符串,设定循环初始值0。while循环的边界条件使用了内置标准函数len(),这个函数的功能是给出参数中包含的元素个数,在这里是字符的个数。
随后在循环体中我们使用print函数在每次循环中打印出来一个结点(一个字符)。s[i]是s字符串中,第i个字符(结点)的意思,i在这里有一个专有名词叫做“下标”,你可以相像数学中常用的$ S_i $形式。这种访问某个序列中具体某个元素的方式是今天的重点之一。
这里i的取值范围是从0开始,因此最大可以到字符串中字符总数-1。最后的i += 1,指的是按照从串头到串尾的方式,循环访问整个字符串中的所有字符。程序的执行结果是这个样子:

a
b
c
d
e
f
g

补充一个小知识,刚才的循环中,我们使用了while i < len(s):,这可以工作的很好,理解起来也不难。但实际上,下面这样做效率更高:
n=len(s)
while i < n:

原因是,在前一个写法中,len这个函数会执行很多次,循环每一次都要重新执行。而在后面的写法中,len函数只需要执行一次。在其后的循环中,直接使用一个变量的值就要快多了。

遍历是编程中最常用到的操作,也是最简单的算法,希望你理解“遍历”的含义了。
接下来我们看一看for循环来实现上面同样的功能:

for a in "abcdefg":
    print(a)

仅有两行代码,完成跟上面while循环程序完全相同的功能,简洁了很多。执行结果跟上面完全一样,就不再重贴了。为了便于理解,我使用伪代码把for循环的基本形式重写一遍:

for 遍历变量 in 序列型的数据:
    循环体,每次循环执行一遍,每次“遍历变量”会有一个新值

这就是for循环的最基本形式。for/in/:是Python中的保留字。循环最终会执行的次数,等同于“序列型数据”中的元素个数。“遍历”是对所有元素都要循环访问一遍。

列表

for循环遍历的对象必须是一个序列类型。序列类型并不是在Python中有一种特定的类型,而是一种统称。可以理解为有顺序、能顺序访问的类型都叫序列类型。列表类型是序列类型的一种。字符串类型也是序列类型的一种。
先看看数字的列表。这是一个数字列表的样子:

[2,3,8.3,34,55,23] 

使用中括号圈起来的,一组用逗号隔开的元素,就是列表。列表是Python六大数据类型中的一种,我们现在已经学习过了3种基本数据类型,数字、字符串、列表。这一讲我们只是简单引入列表的概念,来帮助我们理解“遍历”,在第八讲中,我们将正式而且更深入的讲解列表这种数据类型。
跟字符串一样,对数字的列表同样可以使用len函数:

>>> len([2,3,8.3,34,55,23])
6

我们同样可以使用for循环对数字列表进行遍历,比如:

datas = [2,3,8.3,34,55,23];
for x in datas:
    print(x)
#下面是执行的结果:
2
3
8.3
34
55
23

上面的数字列表中,我们混合了整数和浮点小数。从技术上讲,列表中还可以同时包含“布尔”和“字符串”类型的数据。只是因为不同的数据类型,难以有共同的处理方式,放到同一个列表中也没有办法得到程序效率上的优势,所以并不推荐那样使用。
只要是列表的形式,就可以使用for循环来进行遍历操作,从而提高处理速度。
我们再来对比遍历数字列表的while循环模式和for循环模式:

#首先看while循环
i=0
while i<5:
    print(i)
    i += 1

#下面是for循环的方式
for i in [0,1,2,3,4]:
    print(i)

#两种循环的执行结果都是一样的:
0
1
2
3
4

可以看到,for循环专门为了遍历操作而生,在处理序列数据的时候,程序简洁、代码少、效率高。而while循环则有更强的通用性,但在处理遍历任务的方面则略微麻烦。
为了让for能够处理更多通用的任务,Python提供了一个内置的标准函数range来自动生成一个序列,使用方法的伪代码是:

#单参数方式,生成由0开始,到小于最大值的整数序列
range(最大值)

#双参数方式,生成由最小值到最大值(不包含最大值本身)的整数序列
range(最小值,最大值)

#三参数模式,生成由最小值到最大值,以步长为递增的序列
range(最小值,最大值,步长)

我们来看一组实际使用的例子来加深印象:

for i in range(5):
    print(i)
#执行结果是:
0
1
2
3
4

for i in range(1,6):
    print(i)
#执行结果是:
1
2
3
4
5

for i in range(1,10,2):
    print(i)
1
3
5
7
9

range的注意事项是:range的参数、返回的序列都必须是整数。
我们前面见过了很多操作符,长得很不像关键字,比如+、-,今天我们终于看到了一个相反的例子,in操作符更像关键字,而不像操作符。当然操作符属于关键字的一种。
除了在for循环中使用in操作符,in还可以用于逻辑判断。比如:

"北京" in "今天下雨的地区有:北京、天津、河北"    #结果是true
59 in range(60,101)    #结果为:false

挑战

我们今天的挑战内容是编程生成斐波那契数列(Fibonacci sequence)。
斐波那契数列指的是这样一个数列: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…,这个数列从第3项开始,每一项都等于前两项之和。
今天学习的主要内容是for循环,所以当然这个挑战要使用for循环来完成,生成斐波那契数列的前100项。
老办法,请大家先认真思考,用流程图或者伪代码描述自己的思路,觉得思路清晰了,再看下面的内容。


我们继续使用快速原型法,首先是理清程序的需求,当做注释内容写入到程序:

"""
使用for循环生成前100项斐波那契数列
作者:Andrew

斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...
这个数列从第3项开始,每一项都等于前两项之和。
"""

接下来我们梳理在程序主体循环之前应当准备好的变量和初始值:

#以序列中任意连续3个数字来看
#a代表其中第一个数字,初始是1
a = 1
#b代表其中第二个数字,初始是1
b = 1
#c代表第三个数字,应当是a+b的和,但当前尚未进入循环,所以赋值为0
#因为python语言使用变量前无需声明,所以实际上c=0可以省略
c = 0
#遍历所用变量在for循环中定义,这里忽略

跟上一讲的例子不同,斐波那契数列肯定是边生成边输出,所以肯定是要在循环之内来完成输出的工作。所以不像上一讲的例子,可以先确定输出的内容。
直接进入到考虑循环体的环节,首先依然是循环的边界:

#从第3项开始,循环到第101项
for i in range(3,101):

循环到101项的意思是因为,前面讲过了,range函数所产生的序列,不包含给定的最大值本身,所以range(3,101)实际会产生从3、4、5到100的序列。
参考前面的内容,我们把主体部分的内容一起列出来:

#前两项不用计算,直接显示
print("第 1 项为:",a)
print("第 2 项为:",b)

#从第3项开始,循环到第101项
for i in range(3,101):
    c = a + b #计算第三项
    a = b #3个元素的窗口向后移,原第一个元素被抛弃
    b = c #第二个元素更新为新计算的项
    print("第",i,"项为:",c)    #显示

为了看起来更清楚,我们这次使用截图来展示上面程序的输出结果:
seqs1


程序优化

有人说“好文章是改出来的。”,其实好的程序也是一样。程序编写第一项任务是完成需求所定义的基本工作。随后就要根据程序的表现,有针对性的优化。程序优化最基本的任务通常是速度和内存的占用。因为我们目前的学习还比较基础,暂时不会涉及到那些部分,所以我们先对程序的结构和代码量进行优化。目标是结构更清晰易读,代码更精简高效。
首先我们要根据当前程序的情况进行分析评估,根据评估的结果决定下一步的改进方向。以当前的程序情况来说,可以容易的发现以下几项问题:

  • 斐波那契数列生成的过程中,前两项的生成是单独处理的,跟后面的98项不统一,这会造成将来对程序修改、重用的时候,这两项都要单独处理,维护性差。
  • 也因为对头两项单独的处理,多次使用了print函数,造成代码冗余。
  • 变量c在显示完成后实际可以不用保存,没有必要使用,这造成内存的浪费。
  • 最后是没有进行函数化,可重用性差。

根据我们的分析结果,进行程序优化之前,我们补充一点知识。在第四讲的做练习的时候,为了求甲、乙双方的速度,我们曾经自定义一个函数,最后求得结果的时候是这样一句:

#计算原题:当甲乙双方相距36千米时双方的速度
x,y = getSpeed(36)	#getSpeed函数,最后使用了return x,y

这种使用方法很自然,跟单独一个变量的赋值比起来,效率也更高。我们在这里总结一下为变量赋值的几种形式:

#常规的赋值
a=1
c="abcd"

#多元赋值
x,y = 2,3
x,y = 3,2
x,y = y,x	#注意不是数学等式,这是交换两个变量的值
x,y = y,x+b

#连续赋值
a=b=c=d=10	#赋值结束后,变量a/b/c/d都将是10

好了,我们对程序进行优化。刚才讲到的多元赋值也能用来优化这个程序:

"""
使用for循环生成前100项斐波那契数列
作者:Andrew

斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...
这个数列从第3项开始,每一项都等于前两项之和。
"""
a = 1
b = 1

print("第 1 项为:",a)

for i in range(2,101):
    print("第",i,"项为:",b)    #显示
    a,b = b,a+b #采用多元赋值,直接完成下一项计算和窗口的后移

不错吧?怎么看都能感觉到清晰的进步。然而,两个存在的问题依然没有解决:

  1. 队列中第一项数字仍然单独处理;
  2. 仍然没有函数化。

函数化其实比较简单,把第一项数字也纳入整体生成的考虑就需要算法的调整。这个过程一般只能进行数学上的分析和经验的积累。所以这里我直接说答案:
在第一版的时候,我们使用了3个数字的“窗口”,因为第三个数字是前两个数字之和。
第二版的优化,我们知道了第三个数字其实可以省略不保存,所以只使用了2个数字的“窗口”,因为队列中第三个数字需要前两个数字之和,所以这2个数字的窗口,实际无法继续省略。
既然无法省略,并且要保持2个数字的窗口。我们把数字向前延伸一位,增加一个第0项,值是0,并且无需显示,这个问题就简单了,直接看源码:

#我们省略了开始的注释
def fibonacci(n):
    #为斐波那契数列之前添加一个不显示的第0项:0
    #0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...
    #以序列中任意连续2个数字来看
    #a代表其中第一个数字,初始是0
    #b代表其中第二个数字,初始是1
    a,b = 0,1   #使用连续赋值简化代码

    #从第1项开始,循环到第n项,结尾边界为n+1
    for i in range(1,n+1):
        print("第",i,"项为:",b)    #显示
        a,b = b,a+b #采用多元赋值,直接完成下一项计算和窗口的后移

#调用函数,生成前100项
fibonacci(100)

以我们课程涉及的范畴看,当前基本算最优的算法了,优化至此结束。


练习时间

请用户输入一个整数n,使用for循环的方法,求整数1、2、3一直到n(包含n本身)的和。


本讲小结

  • 本讲讲述了for循环在遍历操作中的应用以及跟while循环的对比
  • 遍历是计算机重要的一种操作模式,会经常用到,从而也让for循环成为最常用的循环模式
  • 运算符也是关键字,关键字、语法、函数组成了语言学习的主要部分
  • 算法方面:一个复杂的问题要逐步拆解,从微小处开始优化。如果还感觉难,就把问题想办法再拆的小一点
  • 其实语言很好学,但一门语言是死的,配合上算法才能完成具体的工作
  • 多元赋值是python的特色,也是优点,能在很多场合简化代码、清晰结构

参考答案

练习题参考答案请参考源码ex.py。