第2课 判断质数效率高（教学课件）信息科技泰山版五年级下册（新教材）

第1单元 校园趣事算法计 判断质数效率高 第2课 泰山版 学习目标 01 课堂导入 02 新知探究 03 知识总结 04 课后练习 05 目录 CONTENTS 2 学习目标 1 理解质数的定义，掌握判断一个大于 1 的自然数是否为质数的核心思路：检查是否存在除 1 和自身之外的因数。 2 学会用N—S图描述判断质数的算法，并能使用积木式编程工具实现该算法，验证其正确性。 3 了解算法优化的意义，知道不同算法在效率上的差异 PART 1 课堂导入 课堂导入 同学们，在数学课上我们已经知道了什么是质数。现在老师这里有一个数字：1000003，谁能快速判断它是不是质数？ 大家是不是觉得手动计算又慢又容易出错？其实，我们可以设计一个高效的算法，让计算机来帮我们完成这个任务。今天，我们就来学习《判断质数效率高》，一起用算法的思维，让判断质数变得又快又准！ PART 2 新知探究 新知探究 做中学 一个大于0的自然数，如果只有1和它本身两个因数，就称这样的数为质数。那么怎样判断一个数是不是质数?请用你喜欢的方式进行描述。 新知探究 建构 方式一：步骤描述法 步骤 1：先判断这个数是否大于1，若小于等于1，它就不是质数。 步骤 2：从2开始，依次用这个数去除以比它小的自然数，检查是否能整除。 步骤 3：如果除了 1 和它本身之外，找不到任何能整除它的数，这个数就是质数；如果存在其他能整除的数，它就不是质数。 方式二：流程图描述法 方式三：循环结构描述法 先判定目标自然数 n是否大于 1，若 n≤1，直接判定为不是质数；若 n>1，使用循环结构：设定除数i从2开始，循环判断 i<n是否成立；循环内核心操作：若n%i=0（即n能被i整除），说明存在 1 和自身外的因数，判定为不是质数，终止循环；若 n%i=0，将 i加 1，继续下一次循环；若循环正常结束（所有 i<n都无法整除 n），判定为是质数。 新知探究 建构 根据质数的性质可知，质数仅有1和自身两个因数。因此，判断一个大于1 的自然数是不是质数的算法就是看这个数是否存在除了1 和本身之外的因数。我们可以利用循环结构，让输入的自然数依次除以2，3，4 等，直到除以输人的自然数的前一个自然数，若其间该自然数被整除，则该自然数不是质数，反之该自然数是质数。 如图所示，用N-S图把判断质数的算法描述出来。 思维导航 新知探究 建构 根据 N—S 图，尝试用以下积木制作判断质数的程序吧! 新知探究 建构 可用以下参考程序验证算法: 新知探究 建构 运行验证，并记录所发现的问题: ①效率低下：当判断的数很大时，程序会从2一直除到这个数本身，运算量极大，运行时间会非常长。 ②存在冗余计算：程序会尝试用偶数去除一个奇数，或者用合数去除一个数，这些都是不必要的计算。 ③对数字1的判断不准确：如果输入数字1，程序会从除数2开始循环，直接判定1是质数，这与质数的定义不符。 ④没有优化终止条件：程序只在除数大于输入数时才停止，而实际上只需要判断到这个数的平方根即可。 新知探究 想一想 如果要判断的数字很大，如1234567891，程序需要从2一直判断到1234567890，这个运算量很大。想一想应该怎样优化程序呢? 新知探究 想一想 优化方法： 1.先排除偶数，减少一半计算 在设置除数之前，先判断输入的数是否为 2（是质数）。 如果不是2，再判断它是否为偶数。如果是，直接输出“不是质数”，不进入循环。 2.只判断到“输入数的一半”就停止 告诉学生：如果一个数能被大于它一半的数整除，那它只能被它自己整除。所以，把“重复执行直到”的条件从“除数>回答-1”修改为“除数>回答/2”。 3.只判断奇数除数 在排除了偶数之后，我们知道输入的数是奇数，它不可能被偶数整除。所以，我们可以将除数的初始值设为 3，并且每次增加 2，只判断奇数作为除数。 新知探究 建构 小秘诀 解决同一个问题的不同算法在相同输入数据规模下的执行时间可能相差很大。 新知探究 知识拓展 质数的应用 质数被广泛应用在密码学上，将想要传递的信息在编码时加入质数变成公钥，之后将公钥传送给收信人，任何人收到此信息后，若没有收信人才拥有的密钥，则在解密的过程中(实为寻找质数的过程)将会因为找质数的过程过久，使得即使取得信息也会毫无意义。 在汽车变速箱齿轮的设计上，将相邻的两个齿轮齿数设计成质数，可以增加齿轮内相同齿相遇啮合次数的最小公倍数，以增强耐用度减少故障。在害虫生长周期与杀虫剂的使用上，杀虫剂的质数次数的使用也得到了证明。实验表明，质数次数地使用杀虫剂是最合理的一一在害虫繁殖的高潮期使用，让害虫很难产生抗药性。 PART 3 知识总结 知识总结 这节课我们一起解锁了高效判断质数的实用技能：我们明白了判断质数的核心是检查是否存在除1和自身之外的因数，学会了用循环结构设计判断质数的算法，并用编程工具实现了它。我们还发现，解决同一个问题的不同算法，在相同输入数据规模下的执行时间可能相差很大。通过先排除偶数、缩小判断范围等优化方法，能让程序效率大幅提升。最重要的是，我们认识到了算法优化的意义，理解了高效算法在处理大数据时的价值。 PART 4 课后练习 课后练习 1.班里要制作“环保小标签”，用一张A4 纸大小的贴纸可以制作100个小标签。小丽负责设计标签上的标语，她想在电脑上通过复制粘贴的方式“克隆”完成100个标语，请问，小丽最少粘贴的次数是多少?( ） A.10 B.7 C.99 D.50 2.有一份20页的文件，打印了2份，打印出的纸张页码排列顺序是1、1、2、2、3、3请设计一个算法，快速地将打印出的纸张分成两份。 谢谢 下节课见！ Thanks！ 泰山版 $