资源简介

(共96张PPT)
函数
Chap6 Function
There is a road in the mountains of books, and diligence is the path
找前5个默尼森数
P是素数且M也是素数，并且满足等式M=2P-1，则称M为默尼森数
例如P=5，M=2P-1=31，5和31都是素数，因此31是默尼森数。
2
函数
3
较大规模的程序通常会被划分成一个个功能模块，这些功能模块就是函数（function）
函数的概念
6.1
4
函数
5
函数是一个独立的代码块
在解决大规模问题时采用“模块化”策略，将一个大而复杂的原始任务分解为多个较简单的子任务，再为每个简单的子任务设计算法
将描述其算法的一组语句封装为一个独立代码块，为每个独立代码块定义一个名字以及能与其他独立代码块通信的接口，这种独立的代码块定义就是函数。
找前5个默尼森数
P是素数且M也是素数，并且满足等式M=2P-1，则称M为默尼森数
例如P=5，M=2P-1=31，5和31都是素数，因此31是默尼森数。
6
使用函数可以在整体上简化程序结构，降低程序开发和修改的复杂度，提高程序的可读性。
Python中的函数
7
内建函数
01
第三方库
03
标准库函数
02
用户自定义函数
04
Python中的函数
8
内建函数
指包含在__builtins__模块中的函数，安装完Python后可以直接使用
标准库
需要先导入模块再使用函数，每个库有相关的一些函数
第三方库
非常多，是Python重要的特征和优势
用户自定义函数
有固定的定义、调用和参数传递方式等
常用python
标准库函数
6.2
9
常用Python标准库函数
10
os
re
math
shutil
random
urllib.request
datetime
已由系统事先定义
使用时直接导入后调用：
模块名.函数名(参数表)
函数名(参数表)
6.2.1 os模块中的函数
11
os模块中常用的处理文件及目录的函数
12
>>> import os
>>> os.getcwd()
'C:\\WINDOWS\\system32'
>>> path = 'd:\\temp'
>>> os.chdir(path)
>>> os.getcwd()
'd:\\temp'
>>> os.rename('current.txt', 'new.txt')
>>> os.remove('new.txt')
>>> os.mkdir('d:\\temp\\tempdir')
>>> os.rmdir('d:\\temp\\tempdir')
Source
dir(os)
6.2.2 random模块中的函数
13
random模块中常用函数的功能和使用方法
14
>>> import random
>>> random.choice(['C++', 'Java', 'Python'])
'Java'
>>> random.randint(1, 100)
37
>>> random.randrange(0, 10, 2)
4
>>> random.random()
0.38859914082194214
>>> random.uniform(5, 10)
5.776718084305783
Source
dir(random)
random模块中常用函数的功能和使用方法
15
>>> import random
>>> random.sample(range(100), 10)
[16, 49, 26, 6, 61, 64, 29, 28, 34, 72]
>>> nums = [1002, 1004, 1001, 1005, 1008]
>>> random.shuffle(nums)#将序列随机排列
>>> nums
[1002, 1008, 1001, 1005, 1004]
Source
6.2.3 datetime模块中的函数
16
datetime模块中的函数
17
>>> from datetime import date
>>> date.today()
datetime.date(2017, 2, 3)
>>> from datetime import time
>>> tm = time(23, 20, 35)#创建时间
>>> print(tm)
23:20:35
Source
datetime模块中的函数
18
>>> from datetime import datetime
>>> dt = datetime.now()
>>> dt
datetime.datetime(2017, 2, 3, 23, 25, 4, 125366)
>>> print(dt.strftime('%a, %b %d %Y %H:%M'))
Fri, Feb 03 2017 23:27
Source
形式1 形式2 含义
%a %A 星期
%b %B 本地月份
%d 月份
%y %Y 年份
%H %I 小时数
%M 分钟数
dt最后部分包含了毫秒“125366”
Datetime.strftime()将对象转换成固定格式的字符串
timestamp()和fromtimestamp()
19
>>> dt = datetime(2017, 2, 3, 23, 29)
>>> print(dt)
2017-02-03 23:29:00
>>> ts = dt.timestamp()#转换成全球统一时间戳
>>> ts
1486135740.0
>>> print(datetime.fromtimestamp(ts))#时间戳转化成本地日期和时间
2017-02-03 23:29:00
Source
函数的定义和调用
6.3
20
函数
函数调用之前必须先定义
21
内建函数或
标准库函数
自定义
函数
6.3.1 函数的定义
22
函数的定义
23
def 函数名([参数表]):
'''文档字符串'''
函数体
语 法
表示函数开始，在第一列书写，该行被称为函数首部，用一个冒号结束；
函数名是函数的名称，是一个标识符，取名时尽量要做到见名识义；
def
函数名
函数的定义
24
def 函数名([参数表]):
'''文档字符串'''
函数体
语 法
函数名后紧跟一对圆括号()，括号内可以有0个、1个或多个参数，参数间用逗号分隔，这里的参数称为形式参数（简称形参），形参只有被调用后才分配内存空间，调用结束后释放所分配的内存空间；
函数体需要缩进，它包含赋值语句和一些功能语句，如果想定义一个什么也不做的函数，函数体可以用pass语句表示。
参数表
函数体
文档字符串是可选的
自定义函数的创建
>>> def printStr(x):
'''print the string'''
print(x)
Source
25
一个非常简单的打印一个字符串的函数
6.3.2 函数的返回
26
函数的返回
27
return 表达式1, 表达式2, …, 表达式n
语 法
通常会通过return语句将值带回给主调函数
位置在函数体内
如果是返回多个值，则构成一个元组
如果不需要返回任何值，则不用return语句或用return None语句
返回值
函数的返回
28
>>> def square(x, y):
'''
计算参数的和与差
'''
return x + y, x – y
Source
返回两个参数的和与差的函数定义
6.3.3 函数的调用
29
函数的返回
30
函数名([参数表])
语 法
函数调用时括号中的参数称为实际参数（简称为实参），在函数调用时分配实际的内存空间。
如果有多个实参，实参间用逗号分隔。
可以没有实参，调用形式为：
函数名() 圆括号不能省略。
调用时实参将值一一传递给形参，程序执行流程转移到被调用函数，函数调用结束后返回到之前的位置继续执行。
调用
函数的导入和调用
>>> from pStr import printStr
>>> printStr('Hi, Python!')
Hi, Python!
31
pStr.py
printStr()
例6.1 编写函数gcd(x, y)求x和y最大公约数
32
# prog6-1.py
def gcd(x, y):
''' calculate the GCD of x and y '''
if x < y:
x, y = y, x
while x % y != 0:
r = x % y
x = y
y = r
return y # 函数返回
x = eval(input("Enter the first number: "))
y = eval(input("Enter the second number: "))
gcdxy = gcd(x, y) # 调用函数
print('GCD({0:d}, {1:d}) = {2:d}'.format(x, y, gcdxy))
File
Output:
Enter the first number: 16
Enter the second number: 24
GCD(16, 24) = 8
例6.2 求1~100之间的所有素数
输出1-100之间的素数
# prog6-2 .py
from math import sqrt
def isprime(x):
if x == 1:
return False
k = int(sqrt(x))
for j in range(2, k+1):
if x % j == 0:
return False
return True
for i in range(2, 101):
if isprime(i):
print( i, end = ' ')
File
33
Output:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
例6.2 求1~100之间的所有素数
# prog6-2 .py
from math import sqrt
def isprime(x):
if x == 1:
return False
k = int(sqrt(x))
for j in range(2, k+1):
if x%j == 0:
return False
return True
for i in range(2,101):
if isprime(i):
print( i, end = ' ')
File
34
if __name__ == "__main__":
for i in range(2,101):
if isprime(i):
print( i, end = ' ')
File
例6.3 编写函数计算平均成绩
根据给出的一组学生的3门课成绩信息，编写函数计算每个学生的平均成绩，返回平均成绩最高和最低两位学生的姓名。
35
36
# prog6-3.py
def search(scores):
maxScore = 0
minScore = 100
for k, v in scores.items():
aveg = (scores[k][0] + scores[k][1] + scores[k][2]) // 3
if aveg >= maxScore:
maxScore = aveg
maxName = k
if aveg <= minScore:
minScore = aveg
minName = k
return maxName, minName
if __name__ == "__main__":
dictScores = {'Jerry' : [87, 85, 91], 'Mary': [76, 83, 88], 'Tim': [97, 95,89], 'John' : [77, 83, 81]}
maxName, minName = search(dictScores)
print('{0} got the first place, {1} got the last.'.format(maxName, minName))
File
Lambda函数
37
def my_add(x, y) : return x + y
my_add = lambda x, y : x + y
lambda x, y : x + y
>>> my_add(3, 5)
8
lambda函数又称为匿名函数，即没有具体的函数名
lambda函数的目的是让用户快速地定义单行函数,简化用户使用函数的过程。
lambda函数
匿名函数
>>> r = lambda x : x + x
>>> r(5)
10
Source
38
>>> def addMe2Me(x):
'apply operation + to argument'
return x + x
>>> addMe2Me(5)
10
Source
例6.3 编写函数计算平均成绩——lamba函数
39
def search(scores):
t = sorted(scores.items(), key = lambda d : (d[1][0] + d[1][1] + d[1][2]) // 3)
return t[len(t)-1][0], t[0][0]
File
使用lambda函数确定了排序函数sorted()的参数key，
确定了scores.items()的排序关键字
例6.3 编写函数计算平均成绩——lambda函数
40
>>> dScores = {'Jerry' : [87, 85, 91], 'Mary': [76, 83, 88], 'Tim': [97, 95,89], 'John' : [77, 83, 81]}
>>> a = sorted(dScores.items() , key = lambda d:d[0])
[('Jerry', [87, 85, 91]), ('John', [77, 83, 81]), ('Mary', [76, 83, 88]), ('Tim', [97, 95, 89])]
>>> a = sorted(dScores.items() , key = lambda d:d[1][0])
[('Mary', [76, 83, 88]), ('John', [77, 83, 81]), ('Jerry', [87, 85, 91]), ('Tim', [97, 95, 89])]
File
例6.4 模拟一个简易的用户注册和登录系统
41
# prog6-4.py
account = {'Zhangsan': '123456'} # account为全局变量
def sign_up():
user_name = input("Please input your user name: ")
while user_name in account.keys():
user_name = input("User name exists, please choose another one:")
password = input("Please input your password: ")
account[user_name] = password
print("Successfully sign up!")
File
例6.4 模拟一个简易的用户注册和登录系统
42
def sign_in():
user_name = input("Please input your user name: ")
if user_name not in account.keys():
print("User name not found.")
else:
count = 0
password = input("Please input your password: ")
while account[user_name] != password:
count += 1
if count >= 3 :
print("Bye - bye")
break
password = input("Wrong password, please input again: ")
if account[user_name] == password:
print("Login success!")
File
例6.4 模拟一个简易的用户注册和登录系统
43
if __name__ == '__main__':
while True:
# 注册0登陆1
cmd = input("Sign Up or Sign In Please input 0 or 1:")
while cmd != '0' and cmd != '1':
print('Wrong command, please input again: ')
cmd = input("Sign Up: 0, Sign in: 1")
if cmd == '0':
sign_up()
continue
if cmd == '1':
sign_in()
break
File
例6.4 模拟一个简易的用户注册和登录系统
44
Output:
Sign Up or Sign In Please input 0 or 1:
0
Please input your user name: Lisi
Please input your password: 123456
Successfully sign up!
Sign Up or Sign In Please input 0 or 1:
1
Please input your user name: Lisi
Please input your password: 123456
Login success!
__main__模块调用了sign_up()和sign_in()函数。算法设计为注册部分不退出，登录成功或密码输入超过错误次数后退出
函数的参数
6.4
45
函数参数
函数调用时将实参一一传递给形参，通常实参和形参的个数要相同，类型也要相容，否则容易发生错误。
参数在调用过程中的变化
参数可以设定默认值
46
6.4.1 参数是否可变
47
实参是否可变的影响
48
不可变对象
可变对象
不会影响到实参
参数可变or不可变
49
def change(stringB):
stringB = 'Hello, Python! '

stringA = 'Hi, Python!'
change(stringA)
print(stringA)
File
def change(listB):
listB = [4, 5, 6]

listA = [1, 2, 3]
change(listA)
print(listA)
File
实参不可变
实参可变
Output:
Hi, Python!
Output:
[1, 2, 3]
参数可变or不可变
50
实参
形参
[1, 2, 3]
实参
形参
[1, 2, 3]
[4, 5, 6]
不管实参是否可变，在调用时实参和形参都引用了同一对象，但形参在函数中获得新的赋值，所以它又引用了新的对象，因此并不会影响到实参。
如何能获得改变过的形参值呢
用return语句将值返回主调函数使用
51
def change(stringB):
stringB = 'Hello, Python! '
return stringB

stringA = 'Hi, Python!'
print(change(stringA))
print(stringA)
File
def change(listB):
listB = [4, 5, 6]
return listB

listA = [1, 2, 3]
print(change(listA))
print(listA)
File
修改形参的值对实参的影响
52
def change(listB):
listB[0] = 88
return listB

listA = [1, 2, 3]
print(change(listA))
print(listA)
File
Output:
[88, 2, 3]
[88, 2, 3]
形参和实参引用同一个对象，形参修改了对象本身的值，引用不变，所以实参的值也跟着发生变化。
修改形参的值不影响实参的做法
53
def change(listB):
listB[0] = 88
return listB

listA = [1, 2, 3]
backup_listA = listA[:]
# 不能用“backup_listA = listA”语句
print(change(listA))
print(listA)
print(backup_listA)
File
Output:
[88, 2, 3]
[88, 2, 3]
[1, 2, 3]
用“backup_listA = listA[:]”给listA复制一个副本backup_listA，此时listA和backup_listA并不引用同一个对象，调用了change()函数后虽然实参改变了但其副本backup_listA的值不会改变，较为安全。
参数可变性结论
如果在函数内对形参重新进行了赋值，形参的值改变了不会影响到实参；
如果在函数内直接修改形参值，则会影响到实参。
54
在实际操作过程中可以根据自己的需要确定是否要给实参复制副本，为了安全起见，一般推荐进行复制。虽然在函数内直接修改形参会影响到原来的实参，但有时正是要利用函数参数的这个特性来解决问题。
例6.5 将一个列表中所有单词的首字母转成大写
55
# prog6-5.py
def capital(listB):
for i in range(len(listB)):
listB[i] = listB[i].capitalize()
listA = ["hope", "is", 'a', 'good', 'thing', '.']
listA_backup = listA[:]
capital(listA)
print(listA)
File
Output:
['Hope', 'Is', 'A', 'Good', 'Thing', '.']
比用return语句返回改变后的列表节省空间，也提高了效率。
6.4.2 不同类型的参数
56
1. 位置参数
57
>>> def printGrade(name, stuID, grade):
print("{0}({1})'s grade is {2}.".format(name, stuID, grade))
>>> printGrade('Mary', '1002', 'A')
Mary(1002)'s grade is A.
Source
实参写反会怎样？
>>> printGrade('A', '1002', 'Mary')
A(1002)'s grade is Mary.
Source
错误的结果
2. 关键字参数
58
>>> def printGrade(name, stuID, grade):
print("{0}({1})'s grade is {2}.".format(name, stuID, grade))
>>> printGrade(name = 'Jerry', stuID = '1005', grade = 'B')
Jerry(1005)'s grade is B.
Source
关键字参数是让调用者通过使用参数名区分参数。允许改变参数列表中的参数顺序。调用时每个参数的含义更清晰。
2. 关键字参数
59
>>> def f(x , y):
'''x and y both correct words or not '''
if y:
print(x, 'and y both correct ')
print(x, 'is OK')
>>> f(68, False)
68 is OK
>>> f(y = False, x = 68)
68 is OK
>>> f(y = False, 68)
SyntaxError: non-keyword arg after keyword arg
>>> f(68, y = False)
68 is OK
Source
3. 默认参数
在定义函数时给某些参数设定默认值，默认参数以赋值语句的形式给出
设定了π的默认值，确定了统一的精度，调用时如果使用默认值则该位置的实参可以省略不写
60
>>> def area(r, pi = 3.14159):
return pi * r *r
Source
>>> area(3)
28.274309999999996
Source
3. 默认参数
默认参数值在调用时可以修改
调用时也一样可以利用关键字参数改变参数顺序
61
>>> area(pi = 3.14, r = 4)
50.24
Source
>>> area(4, 3.14)
50.24
Source
3. 默认参数
62
>>> def printGrade(name, className = 'Courage', grade):
print("{0}({1})'s grade is {2}.".format(name, className, grade))
>>> printGrade('Mary', 'A')
Source
语法错误：非默认参数跟在了默认参数之后
默认参数是可以修改的，如果在定义时将默认参数放在非默认参数前面的话，Python解释器无法判断给出的第二个实参'A'是修改了默认参数的值还是对应了后面的参数
SyntaxError: non-default argument follows default argument
3. 默认参数
63
>>> def printGrade(name, grade, className = 'Courage'):
print("{0}({1})'s grade is {2}.".format(name, className, grade))
>>> printGrade('Mary', 'A')
Mary(Courage)'s grade is A.
Source
定义函数时必须将默认参数放在非默认参数的后面。
4. 可变长参数
Python中允许传递一组数据给一个形参，形参tupleArgs前有一个“*”号，是可变长位置参数的标记，用来收集其余的位置参数，将它们放到一个元组中
64
>>> def greeting(args1, *tupleArgs):
print(args1)
print(tupleArgs)
Source
4. 可变长参数
65
>>> def greeting(args1, *tupleArgs):
print(args1)
print(tupleArgs)
>>> greeting('Hello,', 'Wangdachuan', 'Liuyun', 'Linling')
Hello,
('Wangdachuan', 'Liuyun', 'Linling')
Source
实参中'Hello,'传递给位置参数args1，其余的三个字符串传递给可变长的位置参数tupleArgs，调用后将这组实参放到一个元组中输出。
4. 可变长参数
66
>>> def greeting(args1, *tupleArgs):
print(args1)
print(tupleArgs)
>>> names = ('Wangdachuan', 'Liuyun', 'Linling')
>>> greeting('Hello,', *names)
Hello,
('Wangdachuan', 'Liuyun', 'Linling')
Source
4. 可变长参数——可变长关键字参数
67
>>> def assignment(**dictArgs):
print(dictArgs)
>>> assignment(x = 1, y = 2, z = 3)
{'x': 1, 'z': 3, 'y': 2}
>>> data = {'x': 1, 'z': 3, 'y': 2}
>>> assignment(**data)
{'x': 1, 'z': 3, 'y': 2}
Source
用两个星号标记可变长的关键字参数。可变长关键字参数允许传入多个(可以是0个)含参数名的参数,这些参数在函数内自动组装成一个字典。也可先将参数名和参数构建成一个字典，然后作为可变长关键字参数传递给函数调用。
4. 可变长参数——可变长位置参数
和可变长关键字参数
68
>>> def greeting(args1, *tupleArgs, **dictArgs):
print(args1)
print(tupleArgs)
print(dictArgs)
>>> names = ['Wangdachuan', 'Liuyun', 'Linling']
>>> info = {'schoolName' : 'NJU', 'City' : 'Nanjing'}
>>> greeting('Hello,', *names, **info)
Hello,
('Wangdachuan', 'Liuyun', 'Linling')
{'City': 'Nanjing', 'schoolName': 'NJU'}
Source
例6.6 实现用户信息注册登记
要求必须登记姓名，性别和手机号码，其他如年龄、职业等信息不强制登记。
69
例6.6 实现用户信息注册登记
70
# prog6-6.py
def register(name, gender, phonenum, **otherinfo):
''' register users information '''
print('name: ', name, 'gender: ', gender, 'phone num: ', phonenum)
print('other information: ', otherinfo)
File
例6.6 实现用户信息注册登记
71
>>> register('Chenqian', 'M', '11111111111')
name: Chenqian gender: M phone num: 11111111111
other information: {}
Source
例6.6 实现用户信息注册登记
72
>>> otherinfo = {'age': 24, 'city': 'Nanjing', 'job':'teacher'}
>>> register('Limei', 'F','22222222222', **otherinfo)
name: Limei gender: F phone num: 2222222222
other information: {'age': 24, 'city': 'Nanjing', 'job': 'teacher'}
Source
除了name、gender、phonenum外如果没有登记额外的信息,则可变长关键字参数otherinfo收集不到任何参数，调用后输出一个空字典。如果有额外的信息登记，参数传递时这些参数被组装成一个字典。
变量的作用域
6.5
73
变量作用域
74
>>> def f(): x = 5
>>> f()
>>> print(x)
Traceback (most recent call last):
File "", line 1, in
print(x)
NameError: name 'x' is not defined
Source
变量作用域
每个变量都有自己的作用域，也就是在某个代码段内使用该变量是合法的，在此代码段外使用该变量则是非法的。除了作为全局作用域的变量外，每次函数调用都会创建一个新的作用域。
75
对不同作用域同名变量的处理
76
>>> def f(): x = 5
>>> x = 3
>>> f()
>>> print(x)
3
Source
>>> def f(): y = 5
>>> x = 3
>>> f()
>>> print(x)
3
Source
函数内部使用全局变量
77
>>> def f():
y = 5
print(x + y)
>>> x = 3
>>> f()
8
Source
函数内部虽然可以使用全局变量，但使用要慎重，如果在多个函数内部使用全局变量，则无法确定全局变量某一时刻的值，容易发生错误。
局部变量和全局变量同名时
78
>>> x = 3
>>> def f():
x = 5
print(x ** 2)
>>> f()
Source
在局部变量（包括形参）和全局变量同名时，局部变量屏蔽（Shadowing）全局变量
程序执行结果=？
函数内部同时出现局部变量和全局变量
79
>>> x = 3
>>> def f():
print(x ** 2)
x = 5
print(x ** 2)
>>> f()
Traceback (most recent call last):
File "", line 1, in
f()
File "", line 2, in f
print(x **2)
UnboundLocalError: local variable 'x' referenced before assignment
Source
函数内部同时出现局部变量和全局变量
80
>>> x = 3
>>> def f():
global x
print(x ** 2)
x = 5
print(x ** 2)
>>> x = 3
>>> f()
9
25
Source
使用关键字global声明将使用全局变量
递归
6.6
81
递归
82
生成斐波那契数列的方法
循环
递归
递归是最能表现计算思维的算法之一
函数的嵌套调用
83
f1()
main
…
End
f2()
f1()
…
…
f2()
…
…
End
End
①
②
③
④
函数间可以相互调用，如果在__main__模块中调用了f1函数，在函数f1中又调用了函数f2，就形成了函数的嵌套调用。
直接递归和间接递归
84
f2(…)
f1(…)
…
f1(…)
f2(…)
…
…
…
（a）间接递归调用
f1(…)
…
f1(…)
…
（b）直接递归调用
递归是特殊的嵌套调用，是对函数自身的调用
正确的递归调用的要求
有一个比原始调用规模小的函数副本；
有基本情况即递归终止条件。
85
def f():
f()
Source
无穷递归（infinite recursion）
递归调用的过程
每一次递归调用要解决的问题都要比上一次的调用简单，规模较大的问题可以往下分解为若干个规模较小的问题，规模越来越小最终达到最小规模的递归终止条件（基本情况）
解决完基本情况后函数沿着调用顺序逐级返回上次调用，直到函数的原始调用处结束
一般会包含一个选择结构，条件为真时计算基本情况并结束递归调用，条件为假时简化问题执行副本继续递归调用。
86
递归
递归的执行
87
系统资源消耗比循环大
逐层返回调用至最初层
03
遇到边界条
件停止递归
逐层递归调用
02
01
例6.7 编写递归函数计算n的阶乘
88
n! ＝
1 （当n=1）

n×(n-1)！ （当n>1）
n的阶乘的定义是一种递归定义
例6.7 编写递归函数计算n的阶乘
89
# prog6-7.py
def fac(n):
if n == 1:
return 1
else:
return n * fac(n–1)
File
递归必须要有边界条件，即停止递归的条件
例6.7 编写递归函数计算n的阶乘
90
fac(3)
fac(3):
if n == 1:
return 1
else:
return 3*fac(3-1)
fac(2):
if n == 1:
return 1
else:
return 2*fac(2-1)
fac(1):
if n == 1:
return 1
else:
return 1*fac (1-1)
①
②
④
⑤
⑥
③
递归函数的每次调用时系统都为函数的局部变量（包括形参）分配本次调用使用的存储空间，直到本次调用结束返回主调程序时方才释放。
递归和迭代
求n的阶乘
斐波那契数列
用二分法求方程的根
91
经典的Hanoi（汉诺塔）游戏
八皇后
有明显的迭代方式
适合用递归实现
例6.8 Hanoi塔问题
92
A
B
C
Hanoi塔问题的描述是：有3个底座（分别标记为A、B和C）各有一根针，A座的针上已从下往上从大到小依次叠放了64个（简单起见用3个盘子表示）大小不同的盘子，要求将A座针上的盘子全部搬到C座的针上。在搬运过程中可以借助于B座的针，每次只能搬一个盘子，任何时候每根针上的盘子都必须保持大盘子在下小盘子在上的叠放顺序。
例6.8 Hanoi塔问题
64个盘子需要搬运264-1次。当A座的针上只有一个盘子时（即n=1）数据规模最小，依据搬运要求和搬运规则可以很容易搬运这个盘子，因此直接输出搬运该盘子的操作指令后返回。当A座针上有多个盘子时（即n>1），可以将这n个盘子的搬运操作分解为三部分：
（1）输出将A座针上的前n-1个盘子借助C座针搬到B座针的搬运指令；
（2）输出将A座针上剩下的最后一个盘子（编号为n）直接从A座针搬到C座针的搬运指令；
（3）输出将B座针上的n-1个盘子借助A座针搬到C座针的搬运指令。
93
例6.8 Hanoi塔问题
94
Output:
input the number of plates: 4
a -> b
a -> c
b -> c
a -> b
c -> a
c -> b
a -> b
a -> c
b -> c
b -> a
c -> a
b -> c
a -> b
a -> c
b -> c
# Filename: 6-8.py
def hanoi(a,b,c,n):
if n==1:
print(a,'->',c)
else:
hanoi(a,c,b,n-1)
print(a,'->', c)
hanoi(b,a,c,n-1)
n = int(input('input the number of plates: '))
hanoi('a', 'b', 'c', n)
File
递归深度的设定
查看递归深度
>>> import sys
>>> sys. getrecursionlimit()
1000
手工修改默认值
sys.setrecursionlimit(20000)
95
小结
函数的概念
常用Python标准库函数
函数的定义和调用
函数的参数
变量的作用域
递归函数
96

展开更多......

收起↑