2.4常用算法及其程序实现 课件-2022—2023学年高中信息技术华东师大版（2020）必修1.pptxVIP

第三节 常用算法及其程序实现 复习括号的运算级别最高 复习 枚举法在生活中,人们有时会遇到数字密码锁打不开的情况。遇到这种情况,大部分人会采用类似的解决方法,那就是逐个数字进行尝试,直到打开为止,如图所示。这种逐一尝试的方法在算法中被称之为枚举法,它是处理问题常用的算法思想之一。 枚举法基本原理：是根据已知条件,在给定的范围内对所有可能的答案按某种顺序进行逐一列举和检验,从中找出那些符合要求的答案。即列举出所有可能的情况,然后逐个判断有哪些符合问题所要求的条件,从而得到问题的解答。其一般模式可以总结如下:① 确定范围:问题所涉及的情况有哪些,情况的种数是否可以确定;② 验证条件:这些情况需要满足什么条件才能成为问题的解答。在生活中,我们经常会使用到枚举法。例如,在果农挑选苹果的时候,“待选苹果”为枚举范围,“苹果是否符合规格”则为验证条件,其算法的流程图描述如图2.19所示。 枚举法优缺点：实际解决问题的过程中,如果需要枚举的范围较小,采用枚举法会比较直观;但当枚举范围比较大的时候,则会显得繁琐,需要花费大量的时间去逐一尝试。而能用计算机实现枚举法解决问题的关键是依赖于计算机运算快和自动化的特点。 求解给定的两个正整数m和n的最大公约数方案一：枚举法逐一检验从2到m和n中较小数的范围，最大能够同时被m和n整除的数，则该数就是m和n的最大公约数。试求8251和6105的最大公约数 程序实现枚举法：m=int(input("输入m:"))n=int(input("输入n:"))if(m>n): #如果m比n大 m,n=n,m #则交换两个变量的值gcd=1times=0 #设定循环计数变量初值for i in range(2,m+1): #枚举法求最大公约数 if(m%i==0 and n%i==0): gcd=i #公约数从i开始往上逐个尝试 times=times+1 #循环计数增加print(gcd)print(times) 调试运行枚举法： 求解给定的两个正整数m和n的最大公约数方案二：辗转相除法所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。试求8251和6105的最大公约数 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0显然37是148和37的最大公约数，也就是8251和6105的最大公约数. 例：如何算出8251和6105的最大公约数？ 所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。辗转相处法 4800=350×13+250350=250×1+100 250=100×2+50100=50×2+0显然50是4800和350的最大公约数，也就是4800和350的最大公约数. 求4800和350的最大公约数？ 程序实现辗转相除法：m=int(input("输入m:"))n=int(input("输入n:"))if(m>n): #如果 m比 n大 m,n=n,m #则交换两个变量的值times=0 #设定循环计数变量初值while(n!=0): #辗转相除法求最大公约数 t=m%n m=n n=t times=times+1 #循环计数增加print(m)print(times) 调试运行辗转相除法： 请设计算法,显示某用户在训练课程中完成了哪几项训练内容,未完成哪几项训练内容。1.抽象与建模?0(消耗的卡路里数=0), 空字符串(消耗的卡路里数 ≠0),其中,n 为该跑步课程共有多少项训练内容,消耗的卡路里数为大于等于零的整数,∑ 为求和符号。 请设计算法,显示某用户在训练课程中完成了哪几项训练内容,未完成哪几项训练内容。2.设计算法② 读入对应课程训练内容消耗的卡路里数 ① 读入一周的跑步课程训练内容 ③ 初始设定已完成项目数finished 为0 未完成项目名称unfinished 为空字符串 ④ 逐一列举一周的对应训练内容消耗的卡路里数 ⑤ 如果当前枚举的卡路里数为0 则将对应的训练内容名