资源简介

(共17张PPT)
5.2.1迭代
情境导入
第一天往钱罐子里面投入1元，存钱罐总金额为1元
第二天往钱罐里面投入2元，存钱罐总金额为3元
第三天往存钱罐里面投入3元，存钱罐里面总金额为6元
那么第n天时存钱罐里面一共有多少钱？
n=int(input("存钱天数："))
s=0
for i in range(1,n+1):
___________
print("存钱罐的钱数：",s)
我们利用循环不断执行累加求和，从原值s算出新值s，最终计算出存钱罐的钱数，这种将变量从原值递推出一个新值的算法，我们称之为迭代算法。
s=s+i
迭代算法
迭代是重复反馈的过程，其目的通常是为了接近并达到所需的目标或结果。每一次对过程的重复被称为一次迭代，而每一次迭代得到的结果会被用来作为下一次迭代的初始值。
·迭代的概念
·迭代的特性
迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机重复执行一组指令（或一定步骤），这组指令（或这些步骤）每执行一次，都会将变量从原值推出一个新值。
迭代算法
利用迭代算法解决问题，需要做好三个方面：
·迭代算法的设计方法
·确定迭代变量
在能够用迭代算法处理问题中，至少具有一个直接或间接地不断有旧值推出新值的变量，这个变量就是迭代变量。
·建立迭代关系式
所谓迭代关系式，指如何从变量的前一个值推出下一个值的公式（或关系）。
·控制迭代过程
迭代过程在经过若干次重复执行以后要能结束，因此，要设定迭代结束的条件。
迭代算法
n=int(input("存钱天数："))
s=0
for i in range(1,n+1):
___________
print("存钱罐的钱数：",s)
s=s+i
迭代算法：
①确定迭代变量
②建立迭代关系式
③控制迭代过程
思考：试分析上述程序的迭代变量？迭代关系式？如何控制迭代过程？
①确定迭代变量
②建立迭代关系式
③控制迭代过程
迭代算法
任务一：兔子问题（斐波那契数列）
假定我们有一雄一雌一对刚出生的兔子，它们在长到一个月大小时开始怀孕（真实情况是六个月左右），在第二月结束时，雌兔子产下另一对兔子，过了一个月后它们也开始繁殖，如此这般持续下去。每只雌兔在开始繁殖后每月都产下一对兔子，假定没有兔子死亡，在n个月后总共有多少对兔子？
a1 = 1
a2 = 1
an=an-1+an-2(当n>2时)
时间 0 1月 2月 3月 4月 5月 6月 ……
幼兔 1
成兔 0
总数 1
请列出求解兔子总对数an的数学表达式：
时间 0 1月 2月 3月 4月 5月 6月 ……
幼兔 1 0 1 1 2 3 5
成兔 0 1 1 2 3 5 8
总数(an) 1 1 2 3 5 8 13
迭代算法
请编程实现：
a = [1,1]
n=int(input('请输入月份：'))
for i in range(2,n+1):
_________________
a.append(x)
print(a[n])
x=a[-1]+a[-2]
时间 0 1月 2月 3月 4月 5月 6月 ……
幼兔 1 0 1 1 2 3 5
成兔 0 1 1 2 3 5 8
总数 1 1 2 3 5 8 13
思考：试分析上述程序的迭代变量？迭代关系式？如何控制迭代过程？
数学关系式：
a1 = 1
a2 = 1
an=an-1+an-2(当n>2时)
迭代算法
任务二：欧几里得算法——辗转相除法
辗转相除法求两个数的最大公约数的步骤如下：
先用大的数除以小的数，得到第一个余数；
再用小的数除以第一个余数得到第二个余数；
再用第一个余数除以第二个余数，得到第三个余数；
这样逐次用前一个余数除以后一个余数，直到余数是0为止。
那么,最后一个除数就是所求的最大公约数。
例如求1515和600的最大公约数：
第一次：用1515除以600，商2余315；
第二次：用600除以315，商1余285；
第三次：用315除以285，商1余30；
第四次：用285除以30，商9余15；
第五次：用30除以15，商2余0。故1515和600的最大公约数是15.
迭代思想是如何体现的？
自然语言 流程图 程序设计语言
输入两个正整数m和n 以m除以n，相除得到余数为r 若r=0，则输出n，算法结束；否则执行步骤 令m=n，n=r，返回步骤继续执行 m=int(input(“请输入正整数m：”))
n=int(input(“请输入正整数n：”))
____________
while ____________:
r=m%n
____________
print(“最大公约数为，”,n)
迭代算法
r!=0
m,n=n,r
思考：试分析上述程序的迭代变量？迭代关系式？如何控制迭代过程？
r=m%n
迭代算法
任务三：校运动会求各班总分
每年的校运动会每个班级都会参加一些项目，最后会统计每个班级的总分进行排名，现假定每个班级都参加10个项目，每个项目的得分在0-7之间，我们如何来编程实现统计每个班级的总分？
每个班级都参加10个项目，每个项目的得分在0-7之间，并且每个项目分数之前添加班级序号，最后将各个班级的总分最后放在数组的最后。如3个班级的数据结构如下所示：
[[1, 3], [1, 4], ……, [2, 3], [2, 5], ……, [3, 0], [3, 7], ……, [1, 32], [2, 28], [3, 41]]
上述数据中1班总分为32,2班总分为28,3班总分为41。
第一步：获得班级各项目的分数。
第二步：对它们累加求和。
利用随机数函数获得
利用循环实现求和
迭代算法
from random import randint
a=[]
n=int(input('请输入班级数：'))
for i in range(1,n+1):
for j in range(1,11):
a.append( )
print('各班各项分数为：\n',a)
请编程实现：
第一步：利用随机数函数产生各个班级各个项目的分数。
[i,randint(0,7)]
迭代算法
for i in range(1,n+1):
s=0
j=(i-1)*10
while __________:
#迭代求和，用变量的原值推算出变量的新值
s+=a[j][1]
j+=1
print(_________+"班同学的总分为"+str(s))
请编程实现：
第二步：利用循环编写程序实现求各个班级各个分数的和。
jstr(i)
课堂小结
迭代算法的概念
迭代算法的三要素
迭代算法的实现
迭代算法的数学原理与注意事项
练一练
更相减损术
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。
以18和8为例：18//2=9，8//2=4，9-4=5，5-4=1，5-1=4，4-1=3，3-1=2，2-1=1.减数和差相等。
最大公约数为：1*2=2。
def gys(m, n):
ys=1
while ____________________:
ys=ys*2;m=m//2;n=n//2
while m!=n:
if m>n:
__________________
else:
n=n-m
ys=_________________
return ys
a=[[12,4],[20,25],[32,48],[48,60]]
b=[]
for i in range(4):
b.append(gys(a[i][0], a[i][1]))
print("各组数为：",a)
print("它们的最大公约数为：",b)
m%2==0 and n%2==0
m=m-n
ys*m
练一练
1.Python从最初发布到现在的版本不断更新的过程可以看出，一款
软件从上市到最终框架的成型，是不断试错、不断根据用户体验反馈
快速调整和完善得到的结果。这个例子体现的算法思想是（ ）
A.枚举 B.解析 C.迭代 D.递归
C
练一练
2.下列Python程序的功能是使用迭代算法求c的值（ ）
list1=[1,3,2,4,5,8,7,6,9,4,2,3]
c=0
n=int(input(‘请输入n的值：’))
for i in range(2,n):
a=list1[i]-list1[i-1]
b=list1[i-1]-list1[i-2]
c=c+a+b
print(c)
D
THANK YOU
Speaker :wps powerpoint

展开更多......

收起↑