1、微微项目项目 6 6 用用分治算法提高查找效率分治算法提高查找效率 一、目标确定一、目标确定 （一）一）学科核心学科核心素养要求素养要求 信息意识：学生能够根据解决问题的需要，自觉、主动的寻求恰当 的方式处理信息，具备分析和了解算法的需求，进而尝试用算法解决问 题。 计算思维：具备计算思维的学生，在信息活动中能够采用计算机可 以处理的方式界定问题，抽象特征、建立结构模型，合理组织数据；通 过判断、分析语综合各种信息资源，运用合理的算法形成解决问题的方 案。 通过体验分治算法的程序设计养成运用计算机思维解决问题的习惯。 数字化学习与创新：能够认识数字化学习环境的优势和局限性，适 应数字化学习环境
2、，养成数字化学习与创新的习惯。 信息社会责任：具备信息社会责任的学生，具有一定的信息安全意 识与能力，能有效维护信息活动中个人的合法权益，又能积极维护他人 合法权益和公共信息安全；通过文件的保存提高学生的信息社会意识。 （二）课标解读（二）课标解读 关于“用算法高效寻找问题答案” ，信息技术课程标准 （以下简 称课程标准 ）的描述是“从生从生活实例出发，概述算法的概念与活实例出发，概述算法的概念与特征特征， 运用恰当的描述方法和控制结构表示简单运用恰当的描述方法和控制结构表示简单算算法法，通过解决实际问题，体通过解决实际问题，体 验程序设计的基本流程， 感受算法的效率， 掌握程序验程序设计的基
3、本流程， 感受算法的效率， 掌握程序调调试和运试和运行行的方法的方法” 。 该标准中的行为动词 “概述” 是过程性目标行为动词， 属于“经历水平” 的要求；“体验”是技能性目标行为动词，属于“内化水平”的要求。 （三）教材分析（三）教材分析 泰山出版社初中信息技术教材中，分治查找是计算机科学中的一个 基础算法。对于一个基础算法的学习，可以让学生在一定的情境下，经 历分析问题、确定算法、编程求解等用计算机解决问题的基本过程。本 堂课以一个游戏暖场，同时激活学生的思维，引导学生去探索游戏或生 活背后的科学原理。为了让学生在教师的引导下能自我解析算法的形成 过程，本课分解了问题动作，找出问题的全部可
4、能情况，在对全部可能 情况总结归纳的情况下，得出分治查找的基础算法，最后在程序中得到 实现，从而使学生建立起对分查找算法形成的科学逻辑结构。 （四）学情分析（四）学情分析 初一年级的学生在第一学期初步了解 Python 的使用，能够知道赋值 语句、选择语句、循环语句的基本用法。这节课学生可能会遇到的最大 问题是： 如何归纳总结对分查找解决不同情况问题的一般规律， 鉴于此， 在教学中要积极引导学生采取分解动作、比较迁移等学习策略。 （五）教学目标（五）教学目标 （1）通过猜价格的游戏激活学生的思维，引导学生去探索游戏或生 活背后的科学原理，引出分治算法的概念。 （2） 了解分治查找的原理和特点，
5、 通过分步解析获取分治查找过程， 归纳分治查找的基本思想和方法。 （3）通过分析多种不同的可能情况，构建分治查找的流程。 （4）通过实践体验程序设计，感受分治查找算法的魅力，养成始终 坚持、不断积累才能获得成功的意志品质。 （六）重点难点（六）重点难点 1.教学重点教学重点： 分解并理解分治查找的过程 整理并学习流程图的画法 2.教学难点：教学难点： 尝试编写程序 二、评价设计二、评价设计 （一）过程性评价（一）过程性评价 1.针对目标 1 达成情况的评价 评价目标：能够说出分治查找的方法。 评价任务：猜价格游戏的背后隐藏着一个重要的算法：分治算法。 评价方式：教师在在全班交流时的倾听。 评价
6、标准：每个同学能够说出数据是有序的，然后折半再查。 2. 针对目标 2 达成情况的评价 评价目标：分解分治查找的过程 评价任务：画出 key=17 的查找示意图。 评价方式：教师在学生分解时深入到学生中的查看，课后收回老师 检查。 评价标准：每个学生都能够写出分治查找的示意图。 3. 针对目标 3 达成情况的评价 评价目标：画出分治算法的查找流程图 评价任务：画出分治算法的查找流程图。 评价方式：教师在学生画图时深入到学生中查看，课后收回老师检 查。 评价标准：每个学生至少能画对一半的流程图。 4. 针对目标 4 达成情况的评价 评价目标：体验程序设计。 评价任务：根据流程图写算法，并能正确输
7、入计算机并调试程序， 找出程序的语法错误。 评价方式：教师在学生输入程序时深入到学生中查看。 评价标准：有一半的学生能正确输入程序并调试程序。 （二）终结性评价（二）终结性评价 评价目标：如何根据任务需求，能主动的运用分治算法解决问题。 评价任务：明确分治算法中的核心思想：分而治之，查找中被查找 的数据必须是有序的。每次循环可以将查找规模缩小一半 评价方式：交流分享 评价标准：以描述清楚为主要评价依据 【教学过程】【教学过程】 一一、新课新课导入导入 游戏：游戏：教师展示一件物品，让一个学生来猜这个物品的价格，老师 根据这个学生猜出的价格提示“高了”或是“低了”，如果学生能在四 次内猜对这个物
8、品的价格，就把这件物品“赠送”给他。 思考：思考：你觉得怎么样猜可以猜的快一点呢？有什么技巧吗？ 教师引导：教师引导：我们不是缺少问题，而是缺少发现，其实在这个游戏的 背后，含有一个非常经典的算法。引出分治查找的的概念 二、项目要求：二、项目要求： （一）分析分治算法查找的原理和思想 （二）分解分治算法查找的过程 （三）构建分治算法查找的流程图 （四）分治算法的初步程序实现 三、项目实施及三、项目实施及项目交流项目交流： （一）分析分治算法查找的原理和思想 （1）分治查找中被查找的数据必须是有序的。 （2）首先将查找的数与有序数列表内处于中间位置的数据比较，如 果中间位置上的数与查找的数不同，
9、根据有序性，就可确定应该在数组 的前半部分还是后半部分继续查找。 （3）在新确定的范围内，继续按上述方法进行查找，直到获得最终 结果。 （二）分解分治算法查找的过程 1.列表序号是从 0 开始。 2.弃用 0 号元素，用 a 表示查找范围的起始位置下标，b 表示终止 位置下标，m 表示中间位置元素，所以设置 a 初值为 1,b 的初值为 len(s)-1，m=(a+b)/2（整除） 。 第一种情况，要找的值在后半部分，以 key=47 为例 第第一次一次： a=1a=1 b=10b=10 m=(a+b)/2 =5m=(a+b)/2 =5 SmkeySmkey a=m+1 =6a=m+1 =6
10、第二次： a=6a=6 b=10b=10 m=(a+b)/2 =8m=(a+b)/2 =8 SmkeySmkey a=m+1 =9a=m+1 =9 第三次： a=9a=9 b=10b=10 m=(a+b)/2 =9m=(a+b)/2 =9 Sm=keySm=key 当当 key=51key=51 呢呢 第第一次一次： a=1a=1 b=10b=10 m=(a+b)/2 =5m=(a+b)/2 =5 SmkeySmkey a=m+1 =6a=m+1 =6 第二次： a=6a=6 b=10b=10 m=(a+b)/2 =8m=(a+b)/2 =8 SmkeySmkey a=m+1 =9a=m+1
11、=9 第三次： a=9a=9 b=10b=10 m=(a+b)/2 =9m=(a+b)/2 =9 Sm=keySm=key 第第四次：四次： a=10a=10 b=10b=10 m=(a+b)/2 =10m=(a+b)/2 =10 Sm=keySm=key 第二种情况，要找的值在前半部分，以 key=17 为例，让学生画出查 找示意图。 学生活动主动画出查找示意图： 设计设计意图意图 让让学生自己感觉查找的学生自己感觉查找的过程过程， 能够， 能够明确分治明确分治查找的思想。查找的思想。 a 和 b 的取值范围 if key=sm: b=m-1 else: a=m+1 （三）构建分治算法查找的
12、流程图 学生活动绘制算法流程图 设计设计意图意图再再一次让学生感受计算一次让学生感受计算思维思维的的魅力魅力 （四）分治算法的初步程序实现 1.打开 Python 2.FlieNew File 3.编辑输入 s=-99,1,5,7,12,15,18,21,27,29,31 key=int(input(key=) a=1 b=len(s)-1 while a=b: m=(a+b)/2 print(m=,m) if sm=key: print(key,位于列表中) break elif key=sm: b=m-1 else: a=m+1 学生活动在磕磕碰碰的输入过程中了解程序的语法， 以及写程序时 需要注意的问题，能够调试并解读程序。 设计设计意图意图通过通过程序的输入，明白做一件事情，写一个算法都需要程序的输入，明白做一件事情，写一个算法都需要 有耐心。有耐心。 项目总结项目总结： 分治查找中被查找的数据必须是有序的。 分治查找中每次循环可以将规模缩小一半 课后探究课后探究：设计一个能用分治查找算法思想解决的实际问题。
