第三节 常用算法及其程序实现 复习 括号的运算级别最高 复习 枚举法 在生活中,人们有时会遇到数字密码锁打不开的情况。遇到这种情况,大部分人会采用类似的解决方法,那就是逐个数字进行尝试,直到打开为止,如图所示。这种逐一尝试的方法在算法中被称之为枚举法,它是处理问题常用的算法思想之一。 枚举法 基本原理： 是根据已知条件,在给定的范围内对所有可能的答案按某种顺序进行逐一列举和检验,从中找出那些符合要求的答案。即列举出所有可能的情况,然后逐个判断有哪些符合问题所要求的条件,从而得到问题的解答。其一般模式可以总结如下: ① 确定范围:问题所涉及的情况有哪些,情况的种数是否可以确定; ② 验证条件:这些情况需要满足什么条件才能成为问题的解答。在生活中,我们经常会使用到枚举法。例如,在果农挑选苹果的 时候,“待选苹果”为枚举范围,“苹果是否符合规格”则为验证条件,其算法的流程图描述如图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=1 times=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+333 1813=333×5+148 333=148×2+37 148=37×4+0 显然37是148和37的最大公约数，也就是8251和6105的最大公约数. 例：如何算出8251和6105的最大公约数？ 所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。 辗转相处法 4800=350×13+250 350=250×1+100 250=100×2+50 100=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.抽象与建模 要显示用户的跑步课程完成情况,就需要对课程每日的训练内容以及完成后自动上传的已消耗卡路里数进行统计。 输入:跑步课程中的每日训练内容和对应训练内容消耗的卡路里数,这些信息由程序自动读取数据库中存储的数据,不需要用户输入; 输出:完成的项目数和未完成的项目名称; 计算模型:已完成项目数=????=1????????????????????????, ???????????????????? = 1(消耗的卡路里数 ≠0); 未完成 ... ...
~~ 您好，已阅读到文档的结尾了 ~~
