14.算法效率比一比（教学课件）-五年级信息科技全一册同步备课系列（人教版2024）

算法效率比一比 算法效率比一比 五年级全一册 行业PPT模板http:///hangye/ 人教版 用不同方法统计物体数量 累加运算的效率分析 感受不同算法的运算效率 学科网 讲 授 新 知 讲 授 新 知 一、用不同方法统计物体数量 一堆物体摆放如下图所示，要统计有多少个，你能想到哪些方法？ 数一数，每层的物体个数是多少呢？总共有几层？ 这堆物体共有 10 层，从上到下，第一层1个，第二层2个，以此类推，第10层是 10 个。 讲 授 新 知 讲 授 新 知 一、用不同方法统计物体数量 第一种算法：把这堆物体每层的数量逐层进行累加。 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55 讲 授 新 知 讲 授 新 知 一、用不同方法统计物体数量 第二种算法：观察图形，这堆物体是个梯形，利用正反放置的两个梯形能够组成平行四边形。再利用求平行四边形中物体的个数来计算。梯形物体的个数。 组合后平行四边形共有10层，每层的个数都是11个。 讲 授 新 知 讲 授 新 知 一、用不同方法统计物体数量 平行四边形中物体的个数 = 每层个数 × 层数 =（1+10）×10=110 个 因此，梯形中物体个数 = 平行四边形中物体的个数 ÷2 =110÷2 = 55 个 讲 授 新 知 讲 授 新 知 一、用不同方法统计物体数量 依据上述计算方法，就可以得到求解一组连续自然数累加之和的公式。 例如，自然数从 1 到 n 的累加之和可以表示为： s = （1+n）* n / 2 累加之和 = ( 第一个数 + 最后一个数 ) × 数的总个数 ÷2 讲 授 新 知 讲 授 新 知 一、用不同方法统计物体数量 比较这两种算法，你有什么感受？ 从前面的分析可知，通过求“1+2+3+…+10”的两种不同算法，说明解决同一个问题时，不同的算法会有不同的步骤，也就可能存在不同的效率。 第一种算法很直观、很好理解。 第二种算法理解的时候难度大一点，但是计算步骤少，算起来更快。 讲 授 新 知 讲 授 新 知 二、累加运算的效率分析 通常，用计算机解决问题时会用以下两种方法来比较算法的效率。 一是比较算法运行所需要的时间。 二是比较算法运行时所需的步数或者占用的资源。 我们以主要从时间为例，进行分析。 讲 授 新 知 讲 授 新 知 二、累加运算的效率分析 数学家高斯在读小学时候,老师出了一道题:1+2+3+……+100。同学们马上开始把数字逐一相加,而高斯沉思了一会，就给出了答案，比其他孩子的速度都快。 高斯用的就是前面介绍的第二种算法，而他的同学用的则是第一种算法。 为什么会这样呢？ 讲 授 新 知 讲 授 新 知 二、累加运算的效率分析 我们先来做一个“合理假设”：如果做 1 次加法用时 1 秒、做 1 次乘法用时 10 秒、做 1 次除法用时 15 秒。 用第一种算法计算： 需要计算约 99 次加法，这样即使每次加法只用 1 秒，而且每次中间相加的结果都正确，最终也需要大约 99 秒的时间才能计算出结果。 讲 授 新 知 讲 授 新 知 二、累加运算的效率分析 我们先来做一个“合理假设”：如果做 1 次加法用时 1 秒、做 1 次乘法用时 10 秒、做 1 次除法用时 15 秒。 用第二种算法来计算： 只需要 1 次加法（即 100 + 1）、1 次乘法（即 101×100）和 1 次除法（即除以 2），需要约 1+10+15 = 26 秒。 在“合理假设”的前提下，单从计算步骤和时间上看，第二种算法似乎比第一种更高效，这是高斯比其他同学算得快的一种解释。 讲 授 新 知 讲 授 新 知 二、累加运算的效率分析 但是，问题并没有那么简单。 因为做乘法和除法时，通常比做加法需要更长时间。 因此，如果以上假设并不成立，比如，如果做 1 次乘法或 1 次除法都需要 50 秒，那么用第二种算法所需的时间就会变成 1 + 50 + 50 =101 秒 。 讲 授 新 知 讲 授 新 知 二、累加运算的效率分析 通过上述分析可知，从用算法解决问题的角度看，要准确地比较不同算法的效率，往往比我们预想的要难很多。通常需要从数据量、步骤多少、所需时间等方面综合考虑。 在设计算法用计算机解决问题时通常需要经过多次的比较、实验与探索来获得结论。 讲 授 新 知 讲 授 新 知 三、感受不同算法的运算效率 解决同一个问题通常可以用不同的算法，选择不同算法并编程实现后，程序一般会在运算速度、计算精度等方面有不同的表现。 下面通过用程序验证上述累加运算的两种算法，体会算法的效率差异以及不同程序实现引起的差异。 讲 授 新 知 讲 授 新 知 三、感受不同算法的运算效率 操作步骤： 第 1 步：打开配套资源中的“累加 1.py”程序，运行这个程序。 第 2 步：输入要重复执行的次数，观察运行结果。例如，分别输入500、1 000、10 000、100 000 等，对比两种算法所用的时间。 第3步：尝试用更多更大的数进行反复实验。这样经由多次数值实验得出的结论会更加趋于稳定，也更加可靠。 记录程序运行结果。 “累加 1.py”程序是用算式直接累加与用公式累加的对比。 讲 授 新 知 讲 授 新 知 三、感受不同算法的运算效率 操作步骤： 第 1步：打开配套资源中的“累加 2.py”程序，运行这个程序。 第 2 步：输入要重复执行的次数，观察运行结果。例如，同样分别输入500、1 000、10 000、100 000 等。 第3步：尝试用更多更大的数进行反复实验。这样经由多次数值实验得出的结论会更加趋于稳定，也更加可靠。 第4步：依据运行结果，对算法与程序实现的效率进行总结。 “累加 2.py”程序是用循环结构实现累加与用公式累加的对比。 讲 授 新 知 讲 授 新 知 三、感受不同算法的运算效率 运行次数（m) 500 1000 10 000 100 000 累加1.py 耗费时长 （纳秒） 算法1 算法2 累加2.py 耗费时长 （纳秒） n=100 算法1 算法2 结论 讲 授 新 知 讲 授 新 知 三、感受不同算法的运算效率 在“累加 1.py”程序中，即使执行 10 000 次的累加运算，所需时间仍然非常少，甚至人已经感觉不到所需时间，主要是因为现在的计算机处理速度非常快，只有当数据量或执行次数达到一定规模时，程序才能捕捉到运算时间，操作者才能感受到细微的差异。 不同算法的微小时间差，在数据量足够大时就会产生更大的时间差。 讲 授 新 知 讲 授 新 知 三、感受不同算法的运算效率 在“累加２.py”程序中，与直接用算式累加相比，用循环结构进行累加要占用一些时间。也就是说，编程解决问题时，计算机所进行的任何操作都需要时间，在分析算法效率时要考虑这些因素。 在大规模数据处理时，算法的选择与应用非常关键，如芯片制造、航空航天的轨道控制等。 拓 展 与 提 升 拓 展 与 提 升 拓 展 与 提 升 拓 展 与 提 升 圆周率作为数学中的一个重要常数，其更多位数的精确值求解一直是数学家们所追求的。我国南北朝时期的数学家祖冲之，经过刻苦钻研和反复演算，推算出圆周率 π 的值在 3.1415926 和 3.1415927 之间，这一结果在当时已经非常精确。祖冲之通过其卓越的数学才能和不懈的努力，为数学的发展作出了重要贡献。 拓 展 与 提 升 拓 展 与 提 升 配套资源中有两个计算圆周率的程序，打开这两个程序并运行，对比计算圆周率的效率。 提示：两个程序分别采用了两种不同的算法。 算法 1：17 世纪，有学者找到了一种计算圆周率的方法。根据这个方法，只要计算足够多的数据项，就可以获得圆周率的近似值。 算法 2：很多年后，又有学者提出了另一种计算圆周率的方法。同样，只要计算足够多的数据项，也可以得到圆周率的近似值。 总 结 总 结 1. 知道解决同一个问题可以有不同的算法，不同的算法具有不同的效率。 2. 通过实例比较和算法分析，了解算法执行的关键步骤和执行次数，体会算法存在的效率差异。 3.认识 算法效率的重要性，理解更少的步骤和更快的解决速度通常意味着更高的效率。 谢谢观看 学科网制作 Lavf58.29.100 Bilibili VXCode Swarm Transcoder v0.3.72 $$null