浙教版高中信息技术高一《算法与程序设计》——“选择排序”教学案例.rtf

浙江教育出版版高一算法与程序设计“选择排 序”教学案例 一、设计思想一、设计思想 选择排序是排序中相对较简单的一种算法，在浙教版算法与程序设计中作为重点进行教 学。 根据浙江省普通高中新课程实验信息技术学科教学指导意见，在算法与程序设计模 块教学中，强调理论与实践结合，引导学生注意寻找、发现身边的实际问题，进而设计出算法和 计算机程序去解决问题。 本课算法在教学中采取形象的演示，如 flash 动画的示范，会给教学带来事半功倍的效果。 教材指出，选择排序教学可安排与第五章第 3 节“排序算法的程序实现”一起教学。 二、教材分析二、教材分析 1 教材第二章 2.3 节为排序，其中 2.3.1为排序综述，让学生了解排序的相关概念和意 义；2.3.2 是冒泡排序部分； 2.3.3 是本课要学习的选择排序。选择排序的学习是在 学生积累了对“排序”深入了解、并学习了“冒泡排序”之后，因此对于一些排序 概念稍加点拨即可。 2 教材中采取算法与程序实现分开编写的方式，但浙江省普通高中新课程实验信息 技术学科教学指导意见中指出实际教学未必要按顺序教学，可有针对性地调整教 学次序，如先学习“算法和算法表示”，再学习“面向对象程序设计的基本知识” 部分，有了二者结合的基础，再来学习 “算法实例的程序实现”就会迎刃而解。 3 本课为2 课时完成 三、学情分析三、学情分析 通过上学期算法与编程部分的学习，学生初步了解算法及其表示、比较熟悉流程图设计； 本学期课程为算法与程序设计，对算法的理解更加深入，要求能通过 visual basic 实 现简单算法； 在本课之前，学生应了解了流程图的应用，熟悉在一组数中求极值算法，对于排序及冒泡排 序，学生比较熟练。 对于本部分，学生可能会对选择排序算法的原理理解较为困难，需要教师的引导学习。学生 应当在学习过程中认真听取教师对于算法的分析，在教师指导下能解释该算法的流程图，进而实 现程序。 四、教学目标四、教学目标 知识性目标：知识性目标： 了解排序的概念、能在现实生活中列举出关于排序的实例 能对照冒泡排序，解释选择排序的优势，指出选择排序的策略，找出数字之间的逻辑联 系 有迁移应用能力，能由此及彼，归纳排序中的数字规律，探索更有效率的排序算法 技能性目标：技能性目标： 具有模仿水平，在教师指导下可以表达出选择排序的思想，能对流程图作出解释 能独立完成流程图的绘制，对选择排序的各个环节比较熟练，并能在 visual basic 环 境中规范地编写程序 情感、态度、价值观目标：情感、态度、价值观目标： 学生在学习过程中，通过亲身经历体验选择排序的实现过程，获得对此算法的感性认识 利用信息技术手段，开展交流合作，把自己对此算法的心得与他人交流，培养良好的信 息素养，提升热爱科学的理念 五、重点难点五、重点难点 重点：对选择排序原理的理解，绘制流程图，数据交换，调试程序 难点：分析流程图 六、教学策略与手段六、教学策略与手段 把握重点，先导入问题，复习排序定义，分析冒泡中数据交换次数多的问题，指出冒泡排序 法效率不高，从而引出数据交换次数较少的选择排序算法 在教学过程中，可通过 flash 演示材料，比较直观地把抽象的问题简单化，由“流程图雏形 绘制”-“逐步完善流程图”-“程序实现”-“调试”的过程，让学生熟练此算法与程序实现。 在教学中可灵活运用小组合作、分组讨论、小组间竞赛等手段进行教学，通过发散性思维的 培养，增强学生对知识的探索能力。 七、课前准备七、课前准备 1学生的学习准备：对流程图的绘制方法、vb 语法作巩固，对选择排序算法作预习；学生 分组：4 人一组 2教师的教学准备：准备充分的演示材料、相关数据、相关软件安装。 3教学环境的设计与布置：计算机教室 八、教学过程八、教学过程 简要点拨排序的概念。 演示已经学习过的冒泡排序flash 动画。 小组讨论在冒泡排序算法中，我们知道冒泡排序是依次把数组中相邻两个数据进行比较， 通过交换数据，把较小的数据逐次向上移动的算法。由于数据的移动是逐次进行的，数据交换的 次数相当多。大家想想它的实质既然是将一堆数据中的最小数据移动到某个位置，有没有必要让 这个数字逐个移动？比如，对于数组：4、8、3、9、6、5、11、10、2、9，如果要用冒泡法实现 排序，第一遍冒泡其实是把这组数据中最小数“2”移动到最前边，第二遍冒泡把“3”逐次移到 第二个位置，其它类推。它们的过程是逐次向前的，这样做很多无谓的交换。为了达到移动 2 到 最前边的目的我们可以怎么简化这个过程？ 学生直接把2 最前面的数4交换，再把3 与第二个位置的数8交换，其它类推 教师这个思想就是今天我们要学习的选择排序算法 小组讨论选择排序的实质是每次把一堆数据中的最小数移到某个位置，那么这样的操作在 规模为n 的数组中会做多少次？ n-1 次，因为经过 n-1次操作已经确定了第 1到 n-1 个位置的次序，第 n个位置也自然可 以确定。 小组讨论找出数组中的最小数用什么策略? 复习巩固可以借助一个自定义的integer 型变量 min，用它记录最小的一个数据的下标。 首先，不管实际情况如何，我们先假设数组中第 1 个元素为最小，于是有 min=1，再把这个 元素与从第 2 个元素开始的所有元素作比较，一旦有比 d(min)更小的元素存在，则修改 min 变量 值为新的较小元素下标。这样，在 d(min)经过了从第 2 个元素到最后一个元素的一一比较后，所 得到min 应该就是第1到 n 个元素中的选举出来的最小元素下标了。 然后用类似的方法，把第 2 到 n 个元素中最小数选举出来；把第 3 到 n 个元素中最小数选举 出来 最后把每次选举出来的结果依次输出即可实现升序排列。 学生完成第学生完成第1 1 遍处理过程的流程图片断遍处理过程的流程图片断 依据流程图写出代码 dim min as integer dim j as integer min=1 for j=2 to n if d(j) 1 then temp = d(1):d(1)=d(min):d(min)=temp end if 教师我们先前说过，对于规模为 n 的数组，需要遍历处理次数为 n-1 次，以上的流程就是 这n-1 次中需要重复做的事，对于重复处理的事，可以用什么结构？ 循环，以上的比较、交换比较、交换即为循环体 教师大家试着把这个循环结构流程图画出来 学生完善流程图及代码学生完善流程图及代码 for i = 1 to n-1 min = i for j = i + 1 to n if d(j) i then temp = d(i):d(i) = d(min):d(min) = temp end if next i for m = 1 to n print(str(d(m) next m 调试程序调试程序 扩展提高扩展提高 我们知道，冒泡排序的效率比较低，主要因为数据交换的次数多，那我们如何知道选择排序 中数据交换的次数？ 学生带着问题思考并实践 可利用一个自定义 integer 型变量，初值 0，记录数据交换次数，在程序交换数据部分 令其自加1，程序结束时输出结果。 完整的程序为 dim i,j,min,m,cishu as integer cishu=0 for i = 1 to n-1 min = i for j = i + 1 to n if d(j) i then temp = d(i):d(i) = d(min):d(min) = temp:cishu=cishu+1 end if next i for m = 1 to n print(str(d(m) next m print(str(cishu) 调试程序调试程序 【问题研讨】【问题研讨】 对于规模非常大时，计算选择排序与冒泡排序交换次数，研究时间、空间复杂度 利用网络、图书，发现更优秀的排序算法，并对各种算法进行效率分析 学生源程序