(共36张PPT)
第8单元 第1课
步骤执行次数体现效率
（黔教版）五年级
下
1
核心素养目标
3
新知讲解
5
拓展延伸
7
板书设计
2
新知导入
4
课堂练习
6
课堂总结
课后作业
8
01
核心素养目标
信息意识
计算思维
数字化学习与创新
信息社会责任
遵循规则并尊重其他参与者的体验，一起促进良好的网络行为和社会互动，提升采用高效算法解决问题的意识。
借助编程或算法来优化猜数的过程，例如使用二分查找法来减少猜测次数，以便高效的解决方案。
通过“猜数游戏”学会运用逻辑推理和系统化的思考方式来缩小猜测范围，明白步骤执行次数如何体现效率。
知道解决同一问题的算法可能有多种，能够快速分析和处理信息，判断解决同一问题的不同算法在时间效率上的高低。
02
新知导入
活动背景
“猜数游戏”是小朋友喜欢的益智活动，怎样才能快速猜对数字呢
猜数次数受什么因素影响呢 怎样比较不同算法的效率才合理呢 在生活中也能使用猜数算法的思想吗
02
新知导入
活动目标
1、知道解决同一问题的算法可能有多种，理解算法步骤的执行次数与问题的规模有关。
2、比较不同数据规模下算法步骤的执行次数变化趋势，判断解决同一问题的不同算法在时间效率上的高低。
3、培养应用算法思维解决问题的兴趣和热情，提升采用高效算法解决问题的意识。
02
新知导入
02
新知导入
那就需要对大家用的算法进行比较。可是，怎么比较呢
我想从大家的步骤执行次数体现效率猜数方法中找到一个最佳算法。
需要关注算法中关键步骤的执行次数。
03
新知讲解
活动：比较所用的猜数算法
1.“猜数字”程序可以在 0~10之间生成一个随机数作为要猜的数，并根据用户的猜数结果提供“猜大了”或者“猜小了”的反馈，直到猜对后反馈“猜对了”。运行程序后，开始猜数游戏。记录猜数过程和猜对次数，比一比谁猜得快。
一、问题解决有多种算法
猜数游戏有多种算法，谁用最少的次数猜中数字，谁就获胜。
03
新知讲解
猜数过程 1
提问:请在 0~10之间猜数。回答:5。提问:猜小了。 回答:8。
提问:猜大了。 回答:6。
反馈:猜对了。
猜数过程 2
提问:请在 0~10之间猜数。 回答:0。
提问:猜小了。 回答:2。
提问:猜小了。 回答:4。
提问:猜小了。 回答:6。
反馈:猜对了。
猜数过程 3
提问:请在0~10之间猜数。回答:3。提问:猜小了。 回答:6。
反馈:猜对了。
猜数过程 4
提问:请在 0~10之间猜数。 回答:0。
提问:猜小了。回答:1。提问:猜小了。回答:2。
提问:猜小了。回答:3。提问:猜小了。回答:4。
提问:猜小了。回答:5。提问:猜小了。回答:6。
反馈:猜对了。
03
新知讲解
2.交流猜数过程，分享不同的猜数算法。参考下列猜数算法，你认为哪种更好
猜数算法1
(1)从中间的数字开始猜。
(2)根据反馈的结果在猜数范围的一半内继续猜。
(3)不断重复步骤(1)(2)直到猜对为止。
猜数算法2
(1)从0开始猜。
(2)如果这次猜小了，下次猜数增加 2;如果这次猜大了，下次猜数减少 1。
(3)重复步骤(2)，直到猜对为止。
03
新知讲解
2.交流猜数过程，分享不同的猜数算法。参考下列猜数算法，你认为哪种更好
猜数算法3
(1)从猜数范国随机猜数字。
(2)如果猜错了，在余下数宇内随机猜一个数字。
(3)不断重复步骤(1)(2)，直到猜对为止。
猜数算法4
(1)从0开始猜。
(2)如果猜错了，将猜数增加1。
(3)不断重复步骤(2)，直到猜对为止。
03
新知讲解
有多种算法可以猜中数字，但是需要的猜测次数不同。解决同一个问题往往会有不同的算法，不同算法的效率可能不同。
03
新知讲解
二、算法步骤的执行次数可“数”
为什么不用时间衡量猜数算法的效率呢
猜数游戏中，大家计算和抢答的速度快慢不同，电脑运行速度也有差异，因此直接利用猜中的时间判定算法的效率并不合理，可以通过猜测次数的多少衡量算法效率。猜中数字所需要的次数越少，说明效率越高。
基于给定的算法，可以通过“数出”算法中某些步骤执行的次数，近似分析该算法解决问题的效率。
03
新知讲解
然而，猜测步骤的执行受什么影响呢 用同一个算法猜数，并且针对同样的猜数范围，如果要猜的数字不同，需要猜测的次数会有改变吗
目标数字的位置：如果目标数字接近范围的边界，可能需要更多的猜测次数来确认其位置。例如，在1到100的范围内，目标数字为1时，可能需要较多的猜测次数，而目标数字为50时，使用二分法可以更快找到。
03
新知讲解
然而，猜测步骤的执行受什么影响呢 用同一个算法猜数，并且针对同样的猜数范围，如果要猜的数字不同，需要猜测的次数会有改变吗
数字范围：如果猜测的数字范围较大，通常需要更多的猜测次数来找到正确答案。相反，范围较小时，猜测次数会减少。
使用的算法：不同的猜测算法（如随机猜测、线性猜测、二分查找等）会显著影响猜测的效率。使用更高效的算法可以减少猜测次数。
03
新知讲解
活动：分析猜测次数的变化
合作完成数字范围在0~20内的猜数游戏，一人在0~20内随机出题(要求6、0、20必须出现，其他数字随机出现且不重复)，并反馈猜数结果;另一人用固定的算法猜数。
1.填写表8-1-1，记录猜数结果。
03
新知讲解
表 8-1-1 0~20 范围内猜数过程记录
游戏序次 要猜测的数字 猜对数字所用次数
第1次 0 1
第2次 6 1
第3次 20 1
第4次 8 2
第5次 7 2
第6次 0 1
03
新知讲解
2.该算法最少需要猜几次 最多需要猜几次 平均猜了多少次
3.同学之间分享不同算法的猜数效果，你会选择哪种算法，为什么
最少需要猜的次数是1次，这种情况发生在猜的数字是0、6或20时，因为这些数字在第一次猜测时就对了。最多需要猜的次数取决于算法的效率。假设使用二分查找算法即最多需要5次。
我会选择二分查找算法，因为它的效率较高，平均猜测次数较少。二分查找算法每次将搜索范围减半，能够快速缩小猜测范围，从而减少猜测次数。
03
新知讲解
4.假设猜数字“6”,当猜数范围是10或者20时,猜测次数是否有改变
猜数范围是10时：
如果猜数范围是0到10，使用二分查找算法，最多需要猜 log2 (11)≈3.46 次，即最多需要4次。
猜数范围是20时：
如果猜数范围是0到20，使用二分查找算法，最多需要猜log2(21)≈4.39 次，即最多需要5次。
因此，猜数范围的变化会影响猜测次数，范围越大，猜测次数可能越多。
03
新知讲解
利用固定的算法玩猜数游戏，猜测同一个数字，如果猜数范围增加，猜测次数可能发生变化;即便猜数范围不变，由于所猜测数字不同，需要的猜测次数也会有所不同。因此，猜数字算法中，猜测步骤的执行次数同时受到猜数范围和所猜测数字的影响。
03
新知讲解
自动结算商品总价的算法流程图如下图所示，“将商品价格累加到商品总价变量中”只与输入商品编码的数量有关。因此，有些算法中某些步骤的执行次数，只和数据输入规模有关。
小科提示
04
课堂练习
一、选择题
1、在“猜数游戏”中，使用哪种算法可以最小化猜测次数？
A. 随机猜测 B. 线性猜测
C. 二分查找 D. 递归猜测
2、猜数游戏的反馈信息（如“太大”或“太小”）主要用于：
A. 增加游戏难度 B. 帮助玩家调整猜测
C. 记录玩家的表现 D. 结束游戏
C
B
04
课堂练习
3、在“猜数游戏”中，若玩家每次猜测的数字范围是1到100，且每次猜测后都能得到提示（太高或太低），那么最坏情况下，最多需要多少次猜测才能找到正确的数字？
A. 7 B. 10 C. 14 D. 20
二、判断题
1、使用更高效的算法可以减少猜测次数。 （ ）
2、在猜数游戏中，猜测次数与目标数字的位置无关。 （ ）
3、在“猜数游戏”中，玩家的每一次猜测都是独立的，与之前的猜测无关。 （ ）
B
√
X
X
04
课堂练习
三、操作题
请编写一个简单的程序，使用二分查找法来实现猜数游戏。要求用户输入一个范围（如1到100），然后程序随机选择一个数字，用户通过输入猜测的数字，程序给出反馈，直到用户猜中为止。
05
拓展延伸
优化策略
在解决问题时，优化策略可以通过减少计算量、避免重复计算、利用问题的特性等方式来显著减少步骤执行次数。如：
动态规划（Dynamic Programming）：动态规划是一种通过将问题分解为子问题，并记录子问题的结果来避免重复计算的优化策略。它通常用于解决具有重叠子问题和最优子结构的任务。
05
拓展延伸
优化策略
案例：斐波那契数列
传统的递归方式会重复计算同一个子问题。比如计算`fib(10)`时，`fib(9)`和`fib(8)`都会被多次计算。而动态规划通过记忆化（Memoization）或自底向上的方式将计算结果保存下来，只计算一次，从而减少了计算步骤。
递归方式：每次计算时重复计算相同的子问题，时间复杂度是 `O(2^n)`。动态规划：通过保存每个子问题的结果来避免重复计算，时间复杂度是 `O(n)`。
05
拓展延伸
算法复杂度
大O符号分析常见算法的复杂度。
时间复杂度（Time Complexity）和空间复杂度（Space Complexity）是评估算法效率的两个关键因素。我们通常使用大O符号来表示算法在最坏情况下的复杂度。
冒泡排序（Bubble Sort）：最坏情况时间复杂度是 `O(n^2)`，空间复杂度是 `O(1)`。每次比较相邻元素并交换位置，效率较低。
选择排序（Selection Sort）：最坏情况时间复杂度是 `O(n^2)`，空间复杂度是 `O(1)`。通过逐一选择最小（大）元素来排序，虽然时间复杂度与冒泡排序相同，但通常会有稍微少一点的交换操作。
05
拓展延伸
算法复杂度
插入排序（Insertion Sort）：最坏情况时间复杂度是 `O(n^2)`，空间复杂度是 `O(1)`。适用于小规模数据集。
归并排序（Merge Sort）：时间复杂度是 `O(n log n)`，空间复杂度是 `O(n)`。通过分治法分解问题，效率较高，适合大规模数据集。
快速排序（Quick Sort）：平均时间复杂度是 `O(n log n)`，最坏情况是 `O(n^2)`，空间复杂度是 `O(log n)`。通过分区法快速分割数据集，通常是最快速的排序算法。
05
拓展延伸
不同数据结构对算法效率的影响
数组
查找操作：`O(1)`（直接访问索引位置）
插入/删除操作：`O(n)`（需要移动元素）
链表
查找操作：`O(n)`（需要遍历）
插入/删除操作：`O(1)`（在已知位置插入/删除）
05
拓展延伸
不同数据结构对算法效率的影响
哈希表（Hash Table）
查找/插入/删除操作：`O(1)`（平均情况），但在哈希冲突较多时，最坏情况下会退化为 `O(n)`。
哈希表可以提供非常高效的数据查找，但会有内存消耗，并且对于哈希函数设计不当时性能较差。
05
拓展延伸
不同数据结构对算法效率的影响
通过优化策略，如动态规划、贪心算法和分治法等，可以有效减少步骤执行次数，从而提升算法的效率。在选择算法时，结合大O符号分析时间和空间复杂度，有助于评估不同算法在处理特定问题时的表现。数据结构的选择也直接影响算法的效率，不同的算法在不同的数据结构上运行时，表现会有所不同，因此需要根据实际问题的需求选择合适的算法和数据结构。
06
课堂总结
1
引入新知内容
步骤执行次数体现效率
2
学习问题解决有多种算法
3
算法步骤的执行次数可“数”
4
完成课题练习
5
进行相关知识拓展
1
2
3
4
5
07
板书设计
步骤执行次数体现效率
1、进行新知引入
2、学习问题解决有多种算法
3、算法步骤的执行次数可“数”
4、完成课堂练习
5、进行知识拓展
课后作业。
1、递归算法计算。
08
课后作业
1、考虑以下递归算法：
要求：
1. 分析该递归算法的时间复杂度。
2. 用递归树来解释每一层的调用次数。
3. 给出该算法的时间复杂度的推导。
该递归算法在每次调用时递归调用两次，直到`n`小于等于1为止。每一层有两个递归调用，递归树呈二叉树结构。树的高度是`n`，每一层有`2^k`个节点，总的节点数为`2^n`。
因此，该算法的时间复杂度是 **O(2^n)**，因为递归树的节点数在指数级别增长。
https://www.21cnjy.com/recruitment/home/fine
