6.8算法的多样性（课件）-信息技术六年级上册同步备课（浙教版）

第8课 算法的多样性 学习内容 1. 同一问题存在多种算法。 2. 同一问题的多种算法验证。 讨论 现实中，解决一个问题的算法是不是唯一的？你能举例来说明吗？ 建构 现实中，解决一个问题的算法往往具有多样性，即可用多种不同的算法来解决同一个问题。 一、问题描述 利用计算机可以来实现一些小游戏。如猜数字游戏，计算机预先在1~100 范围内设定一个目标数 mb，同学 A 输入数字去猜该目标数。计算机根据同学 A 的输入数字给出“大了”“小了”或“对了”的提示，直到同学 A的输入数字等于目标数，游戏结束。 二、问题分析 这个猜数字游戏是一个“查找”问题，即在 1~100 范围内查找数 mb。针对该问题，可采用多种不同的策略来解决，例如： 策略一：顺序查找 依次将 1、2、3、…、99、100 （或 100、99、98、…、2、1）与 mb 比较，直到找到为止。 二、问题分析 策略二：二分查找 先取 1~100 的中间数 50 与 mb 比较，若 mb 等于 50，则查找成功；若 mb 小于 50，则取 1~49 的中间数 25 与 mb 比较；若 mb 大于 50，则取 51~100 的中间数 75 与 mb 比较……如此反复，直到找到为止。例如，在 1~100 范围内查找目标数 37 的过程如下所示： 二、问题分析 小知识 计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。 试一试 若采用“顺序查找”的策略，在1~100范围内查找数37，则一共需比较多少次？ 三、问题的多种算法设计 要解决这个问题，可分别采用上述策略，将取到的数分别和目标数进行比较，直到找到为止。假设目标数为 37，并用变量 mb 表示，取到的数用变量 qs 表示。 算法一：顺序查找。若变量 qs 的取值依次为 1、2、3、…、99、100，该过程可采用循环结构来实现。每取一个值都与目标数 mb 比较，若相等，则输出找到的信息，否则变量 qs 取下一个值，该过程可采用分支结构来实现。 三、问题的多种算法设计 对应的算法流程图，如图所示： 三、问题的多种算法设计 算法二：二分查找。 用变量 cz 和 zz 表示可取数的范围，初始范围为1~100，则 cz 的初始值为 1，zz 的初始值为 100。变量 qs 的值依次为变量 cz 和zz 所指范围的中间值，直到变量 cz 的值超过 zz 的值，该过程可采用循环结构来实现。每取一个值都与目标数 mb 比较，若相等，则输出找到的信息，否则改变变量 cz 或 zz 的值，调整变量 cz 和zz 所指范围，该过程可采用分支结构来实现。 三、问题的多种算法设计 对应的算法流程图，如图所示： 四、问题的多种算法验证 根据上述两种算法，可以通过编写程序或流程图的执行进行验证。算法一的程序验证： 想一想 上述程序中，若变量的值为137，则程序运行结果是什么？若要显示对应提示，则应如何修改程序？ 四、问题的多种算法验证 算法二的流程图验证： 根据上述算法二的流程图，可通过表格的形式列出变量 cz、zz 和 qs 的值来验证该算法。 通过 3 次循环，找到数 37。 试一试 若变量 mb 的值为 137，请用表格的形式列出变量 cz、zz 和 qs 的值。 练一练 在上述算法一中，若变量 qs 的取值依次为 100、99、…、2、1，则相应算法和程序如何修改？ 谢谢聆听！ INTERNET OF THINGS $$