资源简介

(共21张PPT)
知识回顾
算法效率的高低由算法复杂度来度量，时间复杂度反映算法执行所需的时间，空间复杂度反映算法执行所占用的存储空间。
算法运行需要时间，一般将算法中语句的执行次数作为时间复杂度的度量标准。
时间复杂度大O阶推导：
用常数1取代运行时间中的所有加法常数；
在修改后的运行次数函数中，只保留最高项；
若最高阶项存在且不是1，则去除此项的系数。
如何量化算法的时间复杂度？
时间复杂度O(n2)
知识回顾
n = int(input())
s = (1+n)*n/2
print(s)
n = int(input())
s = 0
for i in range(1,n+1):
s += i
print(n)
n = int(input())
s=0
x=0
for i in range(1,n+1):
for j in range(1,n+1):
x += 1
s += x
print(s)
请使用大O阶方法计算下列三种算法的时间复杂度。
O(1)
O(n)
O(n2)
算法的时间复杂度反映了程序的执行时间随问题规模增长而增长的量级，在很大程度上能很好地反映算法的优劣。
CHZX
5.2 迭代与递归
浙江省高中信息技术 选择性必修一 《数据与数据结构》
昌化学 应彤鑫
迭代算法
算法思想
程序实现
01
迭代算法
Diedai suanfa
某饲养场引进了1对刚出生的新品种兔子，第2个月进入成熟期，第3个月开始生育兔子，新生的兔子成熟后的下月又会新生1对兔子……若所有的兔子都不会死去，则到第12个月时，该饲养场共有多少对兔子？
兔子繁殖过程：
1月：兔①新生，共1对
2月：兔①成熟，共1对
3月：兔①生兔②，共2对
4月：兔①生兔③，兔②成熟，共3对
5月：兔①生兔④，兔②生⑤，兔③成熟，共5对
6月：兔①生兔⑥，兔②生兔⑦，兔③生兔⑧，兔④⑤成熟，共8对
......
迭代算法
Diedai suanfa
1月 2月 3月 4月 5月 6月 7月 8月 9月 10月 11月 12月 …月
1对 1对 2对 3对 5对 8对 13对 21对 34对 55对 89对 144对 …对
规律：第3月开始，当月兔子数=上月兔子数+当月新生兔子数
规律：第3月开始，当月兔子数=上月兔子数+当月新生兔子数=上月兔子数+上上月兔子数
f1 = 1 # 1月兔子数
f2 = 1 # 2月兔子数
i = 3
while i <= 12:
f = f1 + f2
f1 = f2
f2 = f
i += 1
print(f"第{i-1}月共有{f}对兔子“)
迭代算法：旧值不断推出新值的过程
时间复杂度O(n)
迭代算法
Diedai suanfa
迭代算法：利用计算机运算速度快、适合做重复性操作的特点，让计算机重复执行一组指令，这组指令每执行一次时，都会将变量从原值递推出一个新值，即由旧值不断推出新值的过程。
f1 = 1
f2 = 1
i = 3
while i <= 12:
f = f1 + f2
f1 = f2
f2 = f
i += 1
print(f"第{i-1}月共有{f}对兔子“)
迭代算法处理问题：
确定迭代变量：由旧值递推出新值的变量；
建立迭代关系式：从变量的前值推出下个值的公式；
控制迭代条件：经过若干次重复执行后能够结束。
迭代算法
Diedai suanfa
欧几里得算法又称辗转相除法，用于计算两个整数m、n的最大公约数。基于定理：gcd(m,n)=gcd(n,m%n),即整数m、n的最大公约数等于n和m除以n的余数的最大公约数，当余数为0时取当前算式的除数即为最大公约数。现任意输入两个正整数，请编程实现计算最大公约数的功能。
m = int(input("请输入正整数m："))
n = int(input("请输入正整数n："))
while n != 0:
temp = n
n = m % n
m = temp
print("最大公约数是：",m)
迭代算法处理问题：
确定迭代变量：
建立迭代关系式：
控制迭代条件：
确定迭代变量：m、n
建立迭代关系式：n→m，m%n→n
控制迭代条件：余数为0
迭代算法
Diedai suanfa
0
e+1/jc
0
e+1/jc
递归算法
算法思想
程序实现
02
递归算法
Digui suanfa
俄罗斯一票否决了“乌克兰提出的取消俄罗斯一票否决权”的提案
一网民因造谣“自己因为造谣被公安拘留15天”而被拘留15天
美国谴责“中国谴责美国干涉中国内政”是中国干涉美国内政
禁止套娃→禁止禁止套娃→禁止禁止禁止套娃→……
套娃
递归算法
Digui suanfa
在计算机科学中，指一种通过重复将问题分解为同类的子问题而解决问题的方法，
它通过函数自己调用自己来实现，即一个函数在其定义中直接或间接调用自身的一种方法。
概念
思想
把大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，规模较小的又转化为规模更小的问题求解，当问题小到一定程度时，可以直接得出它的解，从而回归求解问题原来的解。即“大事化小，小事化了”的思想。
1、每一步解决问题的方法有一致的规律：递归公式
2、可以达到某个边界条件：递归出口
条件
案例
整数的阶乘、斐波那契的兔子问题、汉诺塔问题、八皇后问题、猴子吃桃问题等
斐波那契的兔子问题
“大事化小，小事化了”
递归算法
Digui suanfa
问题提出
“大事化小”
n个月兔子的对数？
n→n-1→n-2→……→3→2→1
“小事化了”
1个月有1对，2个月有1对
递归出口
寻求规律
…
fibo(n)
递归公式
假如有一对刚出生的小兔子，只需要一个月小兔子就能长成大兔子，从第三个月开始，这对大兔子每个月都会生下一对小兔子。新出生的小兔子又会花一个月长大，再花一个月开始生兔子…
如果每对兔子都经历这样的出生、成熟、生育的过程，并且永远不死，那么每个月兔子的对数是多少呢？
=fibo(n-1)+fibo(n-2)
递归算法
Digui suanfa
迭代：速度快，效率高；但程序冗杂
递归：程序简洁易懂；但速度慢，效率低
问题解决
def fibo(n):
if n<=2:
return 1
else:
return fibo(n-1)+fibo(n-2)
问题思考
和迭代相比时空复杂度？
def fibo(n):
i=3
a,b=1,1
while i<=n:
a,b=b,a+b
i+=1
return b
时间复杂度：O(N)
空间复杂度：O(1)
时间复杂度：O(2^N)
空间复杂度：O(N)
O(2^N)
O(N)
递归算法
Digui suanfa
汉诺塔游戏
汉诺塔游戏的装置是一块铜板，上面有三根针，其中最左侧一根针上放着从大到小的n个圆盘。游戏的目标是把所有圆盘从最左侧一根针上移动到最右侧一根针上，中间一根针作为过渡。游戏规定每次只能移动一个圆盘，并且大盘子不能压在小盘子上面。
抽象与建模
A
B
C
1
2
3
A
B
C
A
B
C
A
B
C
A
B
C
A
B
C
A
B
C
A
B
C
A
B
C
A→C，A→B，C→B，A→C，B→A，B→C，A→C
将n-1个圆盘从A柱经过C柱移动到B柱
将A柱中剩下的一个圆盘移动到C柱
将n-1个圆盘从B柱经过A柱移动到C柱
将n个圆盘从A柱经过B柱移动到C柱子，建立模型：
递归算法
Digui suanfa
汉诺塔游戏
汉诺塔游戏的装置是一块铜板，上面有三根针，其中最左侧一根针上放着从大到小的n个圆盘。游戏的目标是把所有圆盘从最左侧一根针上移动到最右侧一根针上，中间一根针作为过渡。游戏规定每次只能移动一个圆盘，并且大盘子不能压在小盘子上面。
设计算法
将n有关的问题变成n-1的问题，
重复该过程，每次n减1，
最后当n=1时，直接移动该圆盘。
1
2
3
实现圆盘移动函数
利用建立的模型实现递归调用
实现将n个圆盘从A柱经过B柱移动到C柱子
重复执行步骤2，直到n=1时，直接移动圆盘，递归结束。
move(n,a,b,c)
move(n-1,a,c,b)
a→c
move(n-1,b,a,c)
将n-1个圆盘从A柱经过C柱移动到B柱
将A柱中剩下的一个圆盘移动到C柱
将n-1个圆盘从B柱经过A柱移动到C柱
当n=1时，a→c
递归算法
Digui suanfa
汉诺塔游戏
汉诺塔游戏的装置是一块铜板，上面有三根针，其中最左侧一根针上放着从大到小的n个圆盘。游戏的目标是把所有圆盘从最左侧一根针上移动到最右侧一根针上，中间一根针作为过渡。游戏规定每次只能移动一个圆盘，并且大盘子不能压在小盘子上面。
编写程序
1
2
3
实现圆盘移动函数move
利用建立的模型实现递归调用
实现将n个圆盘从A柱经过B柱移动到C柱子
重复执行步骤2，直到n=1时，直接移动圆盘，递归结束。
move(n,a,b,c)
move(n-1,a,c,b)
a→c
move(n-1,b,a,c)
当n=1时，a→c
def move(n,a,b,c):
if n==1:
print(a,"→",c)
else:
move(n-1,a,c,b)
move(1,a,b,c)
move(n-1,b,a,c)
move(3,"A","B","C")
递归算法
Digui suanfa
已知列表li=[23,87,3,98,45,35,70],求其最大值？
1
利用max()函数直接求解
2
利用递归实现？
def listmax(a,n):
if n==1:
return a[0]
else:
m=listmax(a,n-1)
if mm=a[n-1]
return m
抽象与建模
求n个长度的列表n中的最大值
先求n-1个元素中的最大值
接着将其与第n个元素作比较，并返回较大值
长度为1时，该元素即为最大值
设计算法
1、实现求列表元素最大值的函数listmax(a,n)
a表示列表，n表示列表长度
2、先求n-1个元素的最大值listmax(a,n-1)
3、将其与第n个元素作比较
4、确定递归出口，长度为1时，返回该元素
编写程序
递归算法
Digui suanfa
已知列表li=[23,87,3,98,45,35,70],求其最大值？
def listmax(a,n):
if n==1:
return a[0]
else:
m=listmax(a,n-1)
if mm=a[n-1]
return m
思考：如何利用栈实现“递”和“归”？
递归算法
Digui suanfa
通过重复将问题分解为同类子问题而解决问题的方法，通过函数自己调用自己来实现。
概念
大事化小，小事化了
思想
递归和迭代？
递归公式和递归出口
条件
递归和栈？
递归是重复调用函数自身实现循环；迭代是函数内某段代码实现循环。
练一练
猴子吃桃问题：一只猴子摘了一堆桃子，具体多少它没数。猴子第一天吃了总数的一半多一个，第二天吃了剩余桃子的一半多一个，……，直到第十天，猴子发现只剩1个桃子了。
设计一个递归算法，编程计算猴子总共摘了几个桃子，请在划线处填入合适的代码。
def fun(n)：
if ________①________：
return 1
else：
return ________②________
n==10
f(n)=(f(n+1)+1)*2

展开更多......

收起↑