《新疆版八年级信息技术第十二课冒泡程序数组的应用计算机数据结构与算法_高等教育-大学课件.pdf》由会员分享，可在线阅读，更多相关《新疆版八年级信息技术第十二课冒泡程序数组的应用计算机数据结构与算法_高等教育-大学课件.pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、学习必备 欢迎下载 布尔津镇初级中学教案 课 题 第十二课 冒泡程序 课时及授课时间 1 课时 20XX 年 5 月 30 日 授课人 教学目标(学习目标)知识目标：掌握冒泡排序的原理；理解冒泡排序的流程图；编写冒泡排序的主要代码；能力目标：学会使用冒泡排序思想设计解决简单排序问题的算法；进一步理解程序设计的基本方法，体会程序设计在现实中的作用；情感目标：培养学生分析问题、发现规律的能力，激发学生学习热情；培养良好的程序书写习惯；教学重点 理解冒泡排序原理及它的流程图 教学难点 理解冒泡排序中的遍、次等概念（即对变量使用的理解）教学用具 计算机 多媒体教室 教学方法(学习方法)采用讲解法、演示
2、法、讨论合作、分析归纳法引导学生参与思考，用逐步求精的方式降低学生的理解难度，化抽象为具体，由特殊到一般，有效地突出重点突破难点。教学过程 一、导入：创新情景 我们经常会碰到要排队的情况，比如排座位，做操、排大合唱队伍等。今天我想请四位同学上来表演一下排队。我报了四位学生的名字，让他们上来，并让他们按报到的次序排起来。问：他们现在是按什么排的？学号（我有意按学号报的）。好，现在请你们按身高从矮到高排起来。不一会四位学生就排好了。我指着其中一位换到前面去的学生，问大家他是怎么知道自己矮的。这时下面有学生在喊，他本来就是矮的，还有学生说一看就知道了。我又请这位学生谈谈他当时的想法。一般学生会提到与
3、别人比一下，矮的话就换上去了（如果说不出来，教师可以适当引导一下）。师：对，肯定要比一下才知道，而且需要交换。有些学生说一看就知道，其实也是看了以后经过大脑思维飞快比较得出的结论。排队其实是一种排序：通过调整位置，把杂乱无章的数据变为有序的数据。如 Excel 中的排序功能，通过本节课的学习我们自己也可以设计出类似的小软件。二、新课 备 注 (补充)【设计意图】一开始让四位学生上来，其他学生觉得挺有意思的，所以注意力一下都集中过来。学习必备 欢迎下载 排序的方法很多，这节课我们来学习其中一种比较典型的排序方法冒泡排序。1.冒泡排序的基本思想 教师可以先让学生根据字面意思想像一下“冒泡”是一个怎
4、么样的情景气泡一个一个从下往上不断地冒上来。然后一边讲解一边以文字形式给出冒泡排序的基本思想（书 P31 略）。特别要强调怎样算一遍处理，而且每遍总是从“最下面起”，“自下而上”，比较“相邻”两数。我请刚才那四位学生仍先按学号排回来，然后演示利用冒泡排序法进行从矮到高排序的过程。学生在进行表演时，教师可以充当解说员，关键的地方进行提示，如每遍的开始和结束，同时引导学生认识到第几遍处理完找到的应该是第几矮的同学（或第几小的数）。演示完毕，教师提出一个问题：4 位学生共进行了几遍查找？为什么？然后再用一个 flash 动画演示规模为 4 的数组变量 d 的数据按非减次序进行冒泡排序的逐个过程，再次
5、强化学生对冒泡排序过程的理解。也为下面每一遍中两两交换情况的分析做了铺垫。2.画流程图（按非减次序排序）这块内容是本节课的重点，采用自顶向下逐步求精的方式，由特殊到一般归纳总结，利用模块化，各个难点一一突破。以具体的情况 4 个数为例，由最简单的流程图一左侧的图开始，让学生将冒泡排序过程用形象的语言表示出来：不断冒起一个泡（最小数），于是转化成右侧流程图。流程图一（4 个数）思考：以 4 个数为例，这里的“不断”有没有限定，到底是几遍呢？为什么？流程图二（4 个数）【设计意图】学生的表演比单独拿出几个数来比较往往更能吸引学生的注意力，学生们在轻松活跃的气氛中明确了冒泡排序的基本方法。i:记录正
6、在执行的排序的遍数 月日知识目标掌握冒泡排序的原理理解冒泡排序的流程图编写冒泡排序的主要代码能力目标学会使用冒泡排序思想设计解决简单排序问题的算法进一步理解程序设计的基本方法体会程序设计在现实中的作用情感目标培养学生分析问理解冒泡排序中的遍次等概念即对变量使用的理解教学用具计算机多媒体教室教学方法学习方法教学过程采用讲解法演示法讨论合作分析归纳法引导学生参思考用逐步求精的方式降低学生的理解难度化抽象为具体由特殊到一般有效位同学上来表演一下排队我报了四位学生的名字让他们上来并让他们按报到的次序排起来问他们现在是按什么排的学号我有意按学号报的好现在请你们按身高从矮到高排起来不一会四位学生就排好了我
7、指着其中一位换到前面去的学学习必备 欢迎下载 给出流程图二左边的图之后，教师可以让学生思考一下，这种结构实际上属于什么结构循环结构。但是左图是不规范的，我们需要用一个变量来控制循环次数，从而引出用变量 i 来记录正在执行的排序的遍数，它的值应该是从 1到 3，每次做完后加 1。让学生回顾一下循环结构的流程图模式，两两学生讨论，合作将上面流程图二左侧的图转换成右侧规范的流程图。思考：如果参与排序的是 n 个数呢？比较遍数与个数关系：遍数个数1 为了分解后面一个难点，教师让学生用简单的语言描述每次“冒起一个最小数”是怎么冒出来的：不断两两比较交换，这也是冒泡排序也叫“比较交换”法的原因。于是下面左
8、侧流程图又可转化成右侧的形式。流程图二（n 个数）现在只剩下“不断两两比较交换”还需要进一步细化。如何进行不断两两比较交换？以 4 个数为例，可以回看刚才的 flash 动画。在程序中有些数据规律不是很明显，如果用表格来列一下，可以极大地提高数据分析的有效性和准确性，规律也更容易找出来。【设计意图】遍数与个数关系算是其中一个难点，但无论是通过学生上台表演以及 4 个数的 flash 动画演示，还是学生已有的认知规律，他们还是可以比较容易得出这个结论的。所以将上面流程图中的“i=3”改成“i=n-1”即可得到下面左侧这个流程图。月日知识目标掌握冒泡排序的原理理解冒泡排序的流程图编写冒泡排序的主要
9、代码能力目标学会使用冒泡排序思想设计解决简单排序问题的算法进一步理解程序设计的基本方法体会程序设计在现实中的作用情感目标培养学生分析问理解冒泡排序中的遍次等概念即对变量使用的理解教学用具计算机多媒体教室教学方法学习方法教学过程采用讲解法演示法讨论合作分析归纳法引导学生参思考用逐步求精的方式降低学生的理解难度化抽象为具体由特殊到一般有效位同学上来表演一下排队我报了四位学生的名字让他们上来并让他们按报到的次序排起来问他们现在是按什么排的学号我有意按学号报的好现在请你们按身高从矮到高排起来不一会四位学生就排好了我指着其中一位换到前面去的学学习必备 欢迎下载 第几遍 依次与它的前一个数进行比较的第一个
10、数 依次与它的前一个数进行比较的最后一个数 共第 1 遍 d(4)d(2)第 2 遍 d(4)d(3)第 3 遍 d(4)d(4)引导学生发现规律：每次都是从最后面一个数开始比较，最后一个参与比较的数的下标与比较的遍数有关：遍数1 思考：共 n 个数呢？让学生讨论共 n 个数，各遍比较的情况，特别是第 i 遍，完成下表的填写：第几遍 依次与它的前一个数进行比较的第一个数 依次与它的前一个数进行比较的最后一个数 共比较次数 第 1遍 d(n)d(2)（n-2）+1=n-1 第 2遍 d(n)d(3)（n-3）+1=n-2 第i遍 d(n)d(i+1)（n-(i+1)）+1=n-i 第 n-1 遍
11、 d(n)d(n)(n-n)+1=1 这里又需要用一个变量来标识正在参加比较的数组元素的下标，引进变量 j：记录一遍处理过程中，当前数组元素下标。小结论：共 n 个数，第 i 遍处理时，j 的值从 n 到 i+1 之间递减，每次 d(j)与它的前一个数 d(j-1)进行比较。我一边讲解，一边手绘了如下的表格，说明当要进行第i 遍处理时，即要找第 i 个最小数时，此时前面 i-1 个最小数已经找到（阴影部分），这部分不需要再参与以后的两两比较，所以第 i 遍处理时，第一次两两比较应该是 d(n)与它的前一个数 d(n-1)，以此类推，最后要比的是 d(i+1)与它的前一个数 d(i)，至此此轮最
12、小数就冒到第 i 个位置了。所以最后一个的“它”的位置应该是 i+1。【设计意图】本节课最大的难点就是变量 j的取值范围，尤其是它的终值为什么是 i+1学生往往更是难以理解，因为它是在动态变化的。而由特殊的 4 位数开始找出规律，然后归纳推广到一般的 n 个数就相对比较简单。我花了比较长的时间让学生自己探讨，目的是经过充分思考得出的结论才会记忆深刻。为了加深他们的理解，我又用下表更直观地来说明这个问题。月日知识目标掌握冒泡排序的原理理解冒泡排序的流程图编写冒泡排序的主要代码能力目标学会使用冒泡排序思想设计解决简单排序问题的算法进一步理解程序设计的基本方法体会程序设计在现实中的作用情感目标培养学
13、生分析问理解冒泡排序中的遍次等概念即对变量使用的理解教学用具计算机多媒体教室教学方法学习方法教学过程采用讲解法演示法讨论合作分析归纳法引导学生参思考用逐步求精的方式降低学生的理解难度化抽象为具体由特殊到一般有效位同学上来表演一下排队我报了四位学生的名字让他们上来并让他们按报到的次序排起来问他们现在是按什么排的学号我有意按学号报的好现在请你们按身高从矮到高排起来不一会四位学生就排好了我指着其中一位换到前面去的学学习必备 欢迎下载 位置 数组变量d 1 2 i-1 i i+1 n “如果下面一个数比上面一个数小，就交换”。如果就否则，其实是一种分支结构。教师可以用生活中的实例说明（如果天气好的话就
14、去打球；如果 60 分以上就显示合格，否则就显示不合格），并简单回顾一下分支结构的流程示意图 流程图三(n 个数)不断两两比较交换 【设 计 意图】因为已学过 VB 基本知识，对赋值、选择和循环这三种语句都有基础，所以流程图画出来以后，转换成程序语言 并 不 太难。趁热打铁，顺理成章之间完成了主要代码的编写，为下节课学生上机实践打下基础。说明：虚线框部分即为第 i 遍处理时“不断两两比较交换”的流程图 n:参加排序的数组元素总个数 i:记录正在执行的排序的遍数，由 1 变到 n-1 j:记录一遍处理过程中，当前数组元素下标，由 n 变到i+1 最后一次两两比较 第一次两两比较 月日知识目标掌握
15、冒泡排序的原理理解冒泡排序的流程图编写冒泡排序的主要代码能力目标学会使用冒泡排序思想设计解决简单排序问题的算法进一步理解程序设计的基本方法体会程序设计在现实中的作用情感目标培养学生分析问理解冒泡排序中的遍次等概念即对变量使用的理解教学用具计算机多媒体教室教学方法学习方法教学过程采用讲解法演示法讨论合作分析归纳法引导学生参思考用逐步求精的方式降低学生的理解难度化抽象为具体由特殊到一般有效位同学上来表演一下排队我报了四位学生的名字让他们上来并让他们按报到的次序排起来问他们现在是按什么排的学号我有意按学号报的好现在请你们按身高从矮到高排起来不一会四位学生就排好了我指着其中一位换到前面去的学学习必备
16、欢迎下载 至此，所有问题、难点我们都全部细化，一一解决了，现在将流程图三“两两比较交换”纳入流程图二，即得下面的总流程图：总流程图 当刚显示这个总流程图时，学生还往往不太相信自己的眼睛。师：不要惊讶，这的确是我们通过自己的努力一起画出来的。看来设计算法画出流程图也并不是什么天大的难事，只要我们有信心，由浅入深还是可以解决的。当然别忘了说明一下这个总流程图各部分的作用，并留1 分钟让学生自己消化一下。3学生体验冒泡排序“算法执行过程”提供本书配套辅助软件“运行体验”文件夹中的“冒泡排序.swf”，让学生采用“单步执行”模式。4流程图程序语言 可以通过对两个变量和两数互换语句的解决，最终得到主要参
17、考代码。（1）i:记录正在执行的排序的遍数，由 1 变到 n-1 我们学过的循环语句不外乎 for next 和 Do Loop 两种，这里已知循环次数的情况下，用 for next 比较简单。for i=1 to n-1 冒起一个最小数（循环体）next i（2）j:记录一遍处理过程中，当前数组元素下标，由 n 变到i+1 for j=n to i+1 step 1 d(j)与它的前一个数 d(j-1)进行比较 next j（3）d(j)与 d(j-1)互换 k=d(j)：d(j)=d(j-1)：d(j-1)=k 教师可以利用酱油和米醋互换来做比喻，引导学生实现两数互换的方法。对照总流程图，
18、自上往下，写出主要参考代码：for i=1 to n-1 i 记录正在执行的排序的遍数，由 1变到 n-1 for j=n to i+1 step-1 j 记录一遍处理过程中，当前数组元素下标，由 n 变到 i+1 if d(j)d(j-1)then 如果 d(j)比 d(j-1)小 k=d(j)：d(j)=d(j-1)：d(j-1)=k d(j)与 d(j-1)互换 End ifnext 【设计意图】为寻找解决问题的最佳方案而产生更好的学习目标。尤其是一些理科比较好对程序设计比较感兴趣的学生，离开机房的时候还一路在讨论着。月日知识目标掌握冒泡排序的原理理解冒泡排序的流程图编写冒泡排序的主要代
19、码能力目标学会使用冒泡排序思想设计解决简单排序问题的算法进一步理解程序设计的基本方法体会程序设计在现实中的作用情感目标培养学生分析问理解冒泡排序中的遍次等概念即对变量使用的理解教学用具计算机多媒体教室教学方法学习方法教学过程采用讲解法演示法讨论合作分析归纳法引导学生参思考用逐步求精的方式降低学生的理解难度化抽象为具体由特殊到一般有效位同学上来表演一下排队我报了四位学生的名字让他们上来并让他们按报到的次序排起来问他们现在是按什么排的学号我有意按学号报的好现在请你们按身高从矮到高排起来不一会四位学生就排好了我指着其中一位换到前面去的学学习必备 欢迎下载 Next i 显示参考代码后，教师要引导学生
20、养成良好的习惯，用规范的代码书写格式有利用于程序的调试，还增加了可读性。5拓展：优化冒泡排序 到网上搜索冒泡排序的改进方案。九、作业设计 设计一个评分系统的流程图：有 n 个评委，最后得分为去掉一个最高分与一个最低分后的平均分。板书设计 第十二课 冒泡程序 第几遍 依次与它的前一个数进行比较的第一个数 依次与它的前一个数进行比较的最后一个数 共比较次数 第 1 遍 d(n)d(2)（n-2）+1=n-1 第 2 遍 d(n)d(3)（n-3）+1=n-2 第i遍 d(n)d(i+1)（n-(i+1)）+1=n-i 第 n-1遍 d(n)d(n)(n-n)+1=1 月日知识目标掌握冒泡排序的原理
21、理解冒泡排序的流程图编写冒泡排序的主要代码能力目标学会使用冒泡排序思想设计解决简单排序问题的算法进一步理解程序设计的基本方法体会程序设计在现实中的作用情感目标培养学生分析问理解冒泡排序中的遍次等概念即对变量使用的理解教学用具计算机多媒体教室教学方法学习方法教学过程采用讲解法演示法讨论合作分析归纳法引导学生参思考用逐步求精的方式降低学生的理解难度化抽象为具体由特殊到一般有效位同学上来表演一下排队我报了四位学生的名字让他们上来并让他们按报到的次序排起来问他们现在是按什么排的学号我有意按学号报的好现在请你们按身高从矮到高排起来不一会四位学生就排好了我指着其中一位换到前面去的学学习必备 欢迎下载 教学
22、反思 月日知识目标掌握冒泡排序的原理理解冒泡排序的流程图编写冒泡排序的主要代码能力目标学会使用冒泡排序思想设计解决简单排序问题的算法进一步理解程序设计的基本方法体会程序设计在现实中的作用情感目标培养学生分析问理解冒泡排序中的遍次等概念即对变量使用的理解教学用具计算机多媒体教室教学方法学习方法教学过程采用讲解法演示法讨论合作分析归纳法引导学生参思考用逐步求精的方式降低学生的理解难度化抽象为具体由特殊到一般有效位同学上来表演一下排队我报了四位学生的名字让他们上来并让他们按报到的次序排起来问他们现在是按什么排的学号我有意按学号报的好现在请你们按身高从矮到高排起来不一会四位学生就排好了我指着其中一位换到前面去的学