5.2迭代算法专题复习课件2025届高三高中信息技术复习

5.2 迭代算法专题复习 《数据与数据结构》 code = ’’ + ‘今’ code =‘今’ + ‘天’ code = ‘今天’ + ‘的’ code = ‘今天的’ + ‘你’ code =‘今天的你’ + ‘真’ code = ‘今天的你真’ + ‘的’ ....... ①迭代变量： 旧值推出新值，每一次迭代得到的结果是下一 次迭代的初始值 ②迭代关系式： ③迭代过程： 执行若干次重复操作后，要设定迭代结束条件 知识回顾：迭代 code 累加器 code = code +s[x] for i in range(len(s)) 迭代的三要素： 2 【24.11绍兴一模】实现“解密”功能的部分Python程序如下，请在划线处填入合适的代码 3 一、迭代的基本思想 是一种不断用变量的旧值推出新值的过程。它是解决问题的一种基本方法，通过让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，这次迭代的结果都会用来作为下一次的初始值。 常见的算法： 辗转相除法&辗转相减法求最大公约数 数列求和 斐波那契数列 欧几里得算法 进制转换 1 1 2 3 5 8 13 21 34 55 ... 斐波那契螺旋线 斐波那契数列： f(n）= f(n-1)+f(n-2) 1 1 3 2 5 8 21 13 34 用f(n)来表示数列的第n项： 斐波那契数列 5 斐波那契螺旋线 任务：尝试利用程序实现绘制斐波那契螺旋线。 #用turtle 绘制螺旋线，代码略 f0=f1=1 #斐波那契数列第1、2项赋值 for i in range(2,10): #绘制前10项 f2=f1+f0 draw(f2) 6 斐波那契螺旋线 推导过程： 1 1 2 3 5 8 13 21 f0 f1 f2 f0 f1 f2 f0 f1 f2 f0=f1=1 #斐波那契数列第1、2项赋值 for i in range(2,10): #求解斐波那契数列第3-10项 f2=f1+f0 draw(f2) #以f2为半径作图 f0=f1 f1=f2 7 斐波那契螺旋线 旧值 新值 旧值如何推出新值 f0、f1 f2 f2 f0+f1 f0 f1 f0 f1 f2 f1 迭代变量 迭代关系式 f1 f2 8 有n名同学参加秋游，已知每位同学随身携带一些现金。秋游地点有不同类型自行车若干辆供游客租用，每位同学优先使用自己携带的现金租车，现金不够时可使用公用经费补足费用。为方便财务管理，规定每位同学只能为自己租用自行车，且不会相互借钱。请编写程序计算这n 个同学全部租到自行车所需要公用经费，并且要求公用经费尽可能少。 出谋划策：租车问题 9 1.抽象与建模 （1）每种类型的自行车存储在数组info中（包括租金和数量）。 （2）n位同学随身携带的现金，用数组cash存储。 （3）bike存储自行车的租金。 （4）公用经费total=total+租车差价 (5) i表示当前最便宜的自行车的索引、每个同学所携带的现金索引。 出谋划策：租车问题 10 结合模拟过程，写出计算total过程中的迭代三要素： ①设定迭代变量： ； ②确定迭代关系式：_____ ； ③重复步骤②，直到 迭代结束。 1.抽象与建模 total total+=bike[i]-cash[i] i>=n 若人数n=5,cash=[50,35,55,30,35],info=[[65,2],[45,2],[25,2]], bike=[25,25,45,45,65,65],则公用经费最少为_____元。 20 出谋划策：租车问题 11 2.设计算法 (1) 读取 cash数组存储每个同学携带的现金，读取info数组存储自行车的租金及数量。 (2) 对 cash 数组进行升序排序。 (3) 对info数组按租金升序排序。 (4) 初始化公用经费 total为 ____ 。 (5) 表示每辆自行车的租金bike初始化为空列表。 (6)bike依次读取info数组中每辆自行车的租金。 (7) 表示当前最便宜的自行车的索引i(每个同学所携带的现金索引)初始化为 0。 (8) 当________时，则转（9）；否则，转（10）。 (9) 如果 cash[i] 大于等于 bike[i]，该同学可以支付当前最便宜的自行车，不用补差价，更新 i，指向下一辆自行车，指向下一位同学；否则：计算差额____________，计算total=____________________________，更新 i，指向下一辆自行车，指向下一位同学。然后转(8）。 (10)输出公用经费total。 出谋划策：租车问题 0 i<n total+bike[i]-cash[i] bike[i]-cash[i] 12 3.程序设计 出谋划策：租车问题 cash=sorted(cash)#对cash进行升序排序 info=sort(info)#对info进行升序排序 n = len(cash) bike=[] for i in range(len( info)): for j in range(info[i][1]): bike.append(info[i][0]) j =0 total=__①__ for i in range(__②___): if bike[i]>cash[j]: total=total+______③______ j+=1 print('公用经费：',total,'元！') 13 小结： 迭代的基本思想 ①迭代变量 ②迭代关系式 ③迭代过程 14 Lavf57.83.100 $$