资源简介

(共23张PPT)
算法的多样性
浙教版六年级上册
第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
谢谢
21世纪教育网（www.21cnjy.com)
中小学教育资源网站
兼职招聘：
https://www.21cnjy.com/recruitment/home/admin

展开更多......

收起↑