《冒泡排序算法》教学设计章婷红

                冒泡排序算法》教学设计章婷红 [ 录入者:编辑03 | 时间:2009-01-16 | 来源:本站 | 浏览:[ 　　本节内容选自浙江教育出版社《算法与程序设计》第二章第三节和第五章第三节。以第二章第三节内容《冒泡排序算法》为主，第五章的内容主要用于学生进行程序编写及上机实践。　　通过前面的学习，学生已经了解了算法设计的基本知识，学会了利用自然语言和流程图描述解决问题的算法，对排序中遇到的循环结构流程图、循环语句以及数组变量的使用方法都已有基础。但由于实践较少，他们对以前知识的遗忘率比较高，画流程图还不够熟练，程序设计思想比较弱。　　程序设计的基本方法是自顶向下、逐步求精和模块化。依据这一方法，教师采用讲解法、演示法、讨论合作法、分析归纳法，引导学生参与思考，逐步降低学生的理解难度，化抽象为具体，有效地将各个难点分解和突破。　　　 　一、教学目标　　　 　知识目标：掌握冒泡排序的原理，理解冒泡排序的流程图，学会编写冒泡排序程序的主要代码。　　 能力目标：学会使用冒泡排序思想设计解决简单排序问题的算法；进一步理解程序设计的基本方法，体会程序设计在现实中的作用；培养分析问题、发现规律的能力。　　 情感目标：提高学习热情，培养良好的程序书写习惯。　　　 　二、教学重点与难点　　　　重点：理解冒泡排序原理及其流程图。　 　难点：理解冒泡排序中的遍、次等概念（即对变量使用的理解）。　　　　 三、课前准备　　　　资源准备：冒泡排序的课件。　　教学环境的设计与布置：多媒体网络教室、投影机、多媒体教学平台、Flash软件。　　　 　四、教学过程　　　 　1.导入：创新情景　　师：生活中，我们经常会碰到要排队的情况，比如排座位、排队做操、排队大合唱等。今天，我想请4位同学上来表演一下排队。　　我按学号顺序点4位学生的名字，让他们上来，并让他们按报到的次序排列。　　师：他们现在是按什么排的？　　生：学号。　　师：好，现在请你们按身高从低到高排列。　　不一会儿，4位学生就排好了。其他学生的注意力也集中了过来。　　师（指着其中一位换到前面去的学生问大家）：他是怎么知道自己矮的。　　生：一看就知道了。　　师：那请这位学生谈谈你当时的想法。　　这时一般学生会提到与别人比一下，矮的话就换到前面去了（如果说不出来，教师可做适当引导）。　　师：对，肯定要比一下才知道，而且需要交换。有些学生说一看就知道，其实也是看了以后经过大脑思维飞快地比较而得出的结论。排队其实是一种排序——通过调整位置，把杂乱无章的数据变为有序的数据，如Excel中的排序功能。通过本节课的学习，我们自己也可以设计出类似的小软件。　 　2.冒泡排序的基本思想　　师：排序的方法很多，这节课我们来学习其中一种比较典型的排序方法——冒泡排序。　　教师先让学生根据字面意思想象一下“冒泡”是一个怎么样的情景——气泡一个一个地由下而上依次冒上来。接下来，教师一边讲解一边以文字形式给出冒泡排序的基本思想（教材P31，略）。特别要强调怎样算一遍处理，而且每遍总是从最下面起，自下而上，比较相邻的两个数。　　教师再让刚才那4位学生仍先按学号排回来，演示利用冒泡排序法进行从低到高排序的过程。在学生表演时，教师充当解说员，在关键处（如每遍的开始和结束）进行提示，并引导学生认识到第几遍处理完后找到的应该是第几矮的同学（或第几小的数）。　　设计意图：学生的表演比单纯拿出几个数来比较更能吸引学生的注意力，在这种轻松活跃的气氛中，学生很快明确了冒泡排序的基本方法。　　师：4位学生共进行了几遍查找？为什么？　　教师再用一个Flash动画演示规模为4的数组按非减次序进行逐个冒泡排序的过程，再次强化学生对冒泡排序过程的理解，也为下面每一遍中两两交换情况的分析做了铺垫。　 　3.画流程图（按非减次序排序）　　这一环节是本节课的重点。教师采用自顶向下、逐步求精的方式，由特殊到一般归纳总结，各个难点一一突破。　　教师以具体的4个数为例，由最简单的流程图1左侧的图开始，让学生将冒泡排序过程用形象的语言表示出来：不断冒起一个泡（最小数），转化成右侧流程图。　　　　流程图１　　　　思考：以4个数为例，这里的“不断”有没有限定，到底是几遍呢？为什么？进而带领学生画出流程图2左侧的流程图。　　　　流程图２（４个数）　　　　得出流程图2左侧的图之后，教师让学生思考：这种结构实际上属于什么结构？（循环结构）但是左图是不规范的，需要用一个变量来控制循环次数，从而引出用变量i来记录正在执行的排序的遍数，它的值应该是从1到3，每次做完后加1。学生回顾循环结构的流程图模式，两两讨论，合作将流程图2左侧的图转换成右侧规范的流程图。　　　　流程图３（n个数）　　　　思考：如果参与排序的是n个数呢？　　比较遍数与个数关系：遍数＝个数－1　　为了分解后面的一个难点，教师让学生用简单的语言描述每次“冒起一个最小数”是怎么冒出来的：不断两两比较交换，这也是冒泡排序的原理。于是图2右侧流程图又可转化成流程图3的形式。　　设计意图：遍数与个数关系运算是本课的一个难点，但学生还是可以比较容易地得出这个结论的。所以将上面流程图中的“i＜=3”改成“i＜=n-1”即可得到流程图了。　　现在只剩下“不断两两比较交换”还需要进一步细化。教师以4个数为例，回顾刚才的Flash动画。　　在程序中有些数据规律不很明显，教师用表格列出来，以提高学生分析数据的有效性和准确性，规律也更易找出来。　　　　教师引导学生发现规律：每次都是从最后一个数开始比较，最后一个参与比较的数的下标与比较的遍数有关，即遍数＋1。教师让学生思考：n个数的情况如何比较呢？学生讨论共n个数、各遍比较的情况，特别是第i遍，完成下表的填写：　　　　这里又需要用一个变量来标识正在参加比较的数组元素的下标，引进变量j：记录一遍处理过程中，当前数组元素的下标。　　　　小结论：共n个数，第i遍处理时，j的值从n到i1之间递减，每次d(j)与它的前一个数d(j-1)进行比较。　　设计意图：本节课最大的难点就是变量j的取值范围，尤其对“它的终值为什么是i1”学生更是难以理解，因为它是在动态变化的。由特殊的4位数开始找出规律，然后归纳推广到一般的n个数就相对简单。我花了较长的时间让学生自己探讨，目的是经过充分思考得出的结论才会记忆深刻。　　　　流程图４（n个数）　　　　为了加深学生理解，我一边讲解，一边手绘了如下的图形，以更直观地来说明这个问题：当要进行第i遍处理时，即要找第i个最小数时，此时前面i-1个最小数已经找到（阴影部分），这部分不需要再参与以后的两两比较，所以第i遍处理时，第一次两两比较应该是d(n)与它的前一个数d(n-1)。以此类推，最后要比的是d(i1)与它的前一个数d(i)。至此，该轮最小数就冒到第i个位置了。所以最后一个的“它”的位置应该是i1。　　“如果下面一个数比上面一个数小，就交换”。这是一种分支结构。教师用生活中的实例说明（如果天气好的话就去打球；如果60分以上就显示合格，否则就显示不合格），并简单回顾分支结构的流程示意图。　　设计意图：程序实例生活化学生更容易接受。　　师生得出不断两两比较交换的流程图，如流程图4。　　　　至此，所有问题、难点我们都全部细化，一一解决了，现在将流程图4“两两比较交换”纳入流程图3，即得下面的总流程图。　　　　总流程图　　　　当出示这个总流程图时，学生发出惊叹，他们不太相信自己的眼睛。　　师：不要惊讶，这的确是我们通过自己的努力一起画出来的。看来设计算法、画出流程图也并不是什么难事。只要我们有信心，由浅入深还是可以解决的。　　|||　　本节内容选自浙江教育出版社《算法与程序设计》第二章第三节和第五章第三节。以第二章第三节内容《冒泡排序算法》为主，第五章的内容主要用于学生进行程序编写及上机实践。　　通过前面的学习，学生已经了解了算法设计的基本知识，学会了利用自然语言和流程图描述解决问题的算法，对排序中遇到的循环结构流程图、循环语句以及数组变量的使用方法都已有基础。但由于实践较少，他们对以前知识的遗忘率比较高，画流程图还不够熟练，程序设计思想比较弱。　　程序设计的基本方法是自顶向下、逐步求精和模块化。依据这一方法，教师采用讲解法、演示法、讨论合作法、分析归纳法，引导学生参与思考，逐步降低学生的理解难度，化抽象为具体，有效地将各个难点分解和突破。　　　　一、教学目标　　　　知识目标：掌握冒泡排序的原理，理解冒泡排序的流程图，学会编写冒泡排序程序的主要代码。　　能力目标：学会使用冒泡排序思想设计解决简单排序问题的算法；进一步理解程序设计的基本方法，体会程序设计在现实中的作用；培养分析问题、发现规律的能力。　　情感目标：提高学习热情，培养良好的程序书写习惯。　　　　二、教学重点与难点　　　　重点：理解冒泡排序原理及其流程图。　　难点：理解冒泡排序中的遍、次等概念（即对变量使用的理解）。　　　　三、课前准备　　　　资源准备：冒泡排序的课件。　　教学环境的设计与布置：多媒体网络教室、投影机、多媒体教学平台、Flash软件。　　　　四、教学过程　　　　1.导入：创新情景　　师：生活中，我们经常会碰到要排队的情况，比如排座位、排队做操、排队大合唱等。今天，我想请4位同学上来表演一下排队。　　我按学号顺序点4位学生的名字，让他们上来，并让他们按报到的次序排列。　　师：他们现在是按什么排的？　　生：学号。　　师：好，现在请你们按身高从低到高排列。　　不一会儿，4位学生就排好了。其他学生的注意力也集中了过来。　　师（指着其中一位换到前面去的学生问大家）：他是怎么知道自己矮的。　　生：一看就知道了。　　师：那请这位学生谈谈你当时的想法。　　这时一般学生会提到与别人比一下，矮的话就换到前面去了（如果说不出来，教师可做适当引导）。　　师：对，肯定要比一下才知道，而且需要交换。有些学生说一看就知道，其实也是看了以后经过大脑思维飞快地比较而得出的结论。排队其实是一种排序——通过调整位置，把杂乱无章的数据变为有序的数据，如Excel中的排序功能。通过本节课的学习，我们自己也可以设计出类似的小软件。　　2.冒泡排序的基本思想　　师：排序的方法很多，这节课我们来学习其中一种比较典型的排序方法——冒泡排序。　　教师先让学生根据字面意思想象一下“冒泡”是一个怎么样的情景——气泡一个一个地由下而上依次冒上来。接下来，教师一边讲解一边以文字形式给出冒泡排序的基本思想（教材P31，略）。特别要强调怎样算一遍处理，而且每遍总是从最下面起，自下而上，比较相邻的两个数。　　教师再让刚才那4位学生仍先按学号排回来，演示利用冒泡排序法进行从低到高排序的过程。在学生表演时，教师充当解说员，在关键处（如每遍的开始和结束）进行提示，并引导学生认识到第几遍处理完后找到的应该是第几矮的同学（或第几小的数）。　　设计意图：学生的表演比单纯拿出几个数来比较更能吸引学生的注意力，在这种轻松活跃的气氛中，学生很快明确了冒泡排序的基本方法。　　师：4位学生共进行了几遍查找？为什么？　　教师再用一个Flash动画演示规模为4的数组按非减次序进行逐个冒泡排序的过程，再次强化学生对冒泡排序过程的理解，也为下面每一遍中两两交换情况的分析做了铺垫。　　3.画流程图（按非减次序排序）　　这一环节是本节课的重点。教师采用自顶向下、逐步求精的方式，由特殊到一般归纳总结，各个难点一一突破。　　教师以具体的4个数为例，由最简单的流程图1左侧的图开始，让学生将冒泡排序过程用形象的语言表示出来：不断冒起一个泡（最小数），转化成右侧流程图。　　　　流程图１　　　　思考：以4个数为例，这里的“不断”有没有限定，到底是几遍呢？为什么？进而带领学生画出流程图2左侧的流程图。　　　　流程图２（４个数）　　　　得出流程图2左侧的图之后，教师让学生思考：这种结构实际上属于什么结构？（循环结构）但是左图是不规范的，需要用一个变量来控制循环次数，从而引出用变量i来记录正在执行的排序的遍数，它的值应该是从1到3，每次做完后加1。学生回顾循环结构的流程图模式，两两讨论，合作将流程图2左侧的图转换成右侧规范的流程图。　　　　流程图３（n个数）　　　　思考：如果参与排序的是n个数呢？　　比较遍数与个数关系：遍数＝个数－1　　为了分解后面的一个难点，教师让学生用简单的语言描述每次“冒起一个最小数”是怎么冒出来的：不断两两比较交换，这也是冒泡排序的原理。于是图2右侧流程图又可转化成流程图3的形式。　　设计意图：遍数与个数关系运算是本课的一个难点，但学生还是可以比较容易地得出这个结论的。所以将上面流程图中的“i＜=3”改成“i＜=n-1”即可得到流程图了。　　现在只剩下“不断两两比较交换”还需要进一步细化。教师以4个数为例，回顾刚才的Flash动画。　　在程序中有些数据规律不很明显，教师用表格列出来，以提高学生分析数据的有效性和准确性，规律也更易找出来。　　　　教师引导学生发现规律：每次都是从最后一个数开始比较，最后一个参与比较的数的下标与比较的遍数有关，即遍数＋1。教师让学生思考：n个数的情况如何比较呢？学生讨论共n个数、各遍比较的情况，特别是第i遍，完成下表的填写：　　　　这里又需要用一个变量来标识正在参加比较的数组元素的下标，引进变量j：记录一遍处理过程中，当前数组元素的下标。　　　　小结论：共n个数，第i遍处理时，j的值从n到i1之间递减，每次d(j)与它的前一个数d(j-1)进行比较。　　设计意图：本节课最大的难点就是变量j的取值范围，尤其对“它的终值为什么是i1”学生更是难以理解，因为它是在动态变化的。由特殊的4位数开始找出规律，然后归纳推广到一般的n个数就相对简单。我花了较长的时间让学生自己探讨，目的是经过充分思考得出的结论才会记忆深刻。　　　　流程图４（n个数）　　　　为了加深学生理解，我一边讲解，一边手绘了如下的图形，以更直观地来说明这个问题：当要进行第i遍处理时，即要找第i个最小数时，此时前面i-1个最小数已经找到（阴影部分），这部分不需要再参与以后的两两比较，所以第i遍处理时，第一次两两比较应该是d(n)与它的前一个数d(n-1)。以此类推，最后要比的是d(i1)与它的前一个数d(i)。至此，该轮最小数就冒到第i个位置了。所以最后一个的“它”的位置应该是i1。　　“如果下面一个数比上面一个数小，就交换”。这是一种分支结构。教师用生活中的实例说明（如果天气好的话就去打球；如果60分以上就显示合格，否则就显示不合格），并简单回顾分支结构的流程示意图。　　设计意图：程序实例生活化学生更容易接受。　　师生得出不断两两比较交换的流程图，如流程图4。　　　　至此，所有问题、难点我们都全部细化，一一解决了，现在将流程图4“两两比较交换”纳入流程图3，即得下面的总流程图。　　　　总流程图　　　　当出示这个总流程图时，学生发出惊叹，他们不太相信自己的眼睛。　　师：不要惊讶，这的确是我们通过自己的努力一起画出来的。看来设计算法、画出流程图也并不是什么难事。只要我们有信心，由浅入深还是可以解决的。　　|||　　教师说明这个总流程图各部分的作用，并留几分钟让学生自己消化新学知识。　　4.学生体验冒泡排序“算法执行过程”　　让学生采用“单步执行”模式观看本书配套辅助软件“运行体验”文件夹中的“冒泡排序.swf”，体验冒泡排序的算法执行过程。　　5.流程图→程序语言　　可以通过对两个变量和两数互换语句的解决，最终得到主要参考代码。　　（1）i:记录正在执行的排序的遍数，由1到n-1　　fori=1ton-1　　冒起一个最小数（循环体）　　nexti　　（2）j:记录一遍处理过程中，当前数组元素下标，由n变到i1　　forj=ntoi1step-1　　d(j)与它的前一个数d(j-1)进行比较　　nextj　　（3）d(j)与d(j-1)互换　　k=d(j):d(j)=d(j-1):d(j-1)=k　　教师可以利用酱油和米醋互换来做比喻，引导学生实现两数互换的方法。　　对照总流程图，自上往下，写出主要参考代码：　　fori=1ton-1'i记录正在执行的排序的遍数，由1变到n-1　　forj=ntoi1step-1'j记录一遍处理过程中，当前数组元素下标，由n变到i1　　ifd(j)　　k=d(j):d(j)=d(j-1):d(j-1)=k'd(j)与d(j-1)互换　　endif　　nextj　　nexti　　设计意图:因为已学过VB基本知识，学生对赋值、选择和循环这三种语句都有基础，所以流程图画出来以后，转换成程序语言并不太难。教师趁热打铁，顺理成章地完成了主要代码的编写，为下节课学生上机实践打下基础。　　显示参考代码后，教师要引导学生养成良好的习惯，使用规范的代码书写格式，不仅有利于程序的调试，还增加了可读性。　　6.拓展：优化冒泡排序　　教师让学生到网上搜索冒泡排序的改进方案。　　设计意图:为寻找解决问题的最佳方案而产生更好的学习目标。尤其是一些理科比较好，又对程序设计比较感兴趣的学生，离开机房的时候还一路在讨论着。　　7.作业设计　　设计一个评分系统的流程图：有n个评委，最后得分为去掉一个最高分与一个最低分后的平均分。　　　　五、问题研讨　　　　1.如何用人的思维模拟计算机的工作过程　　我让学生上来排队演示，本想让他们用不同方法，以便引出各种排序方式。但后来发现这太难了。因为人是有眼睛和原有认知能力的，有些事想当然就可以完成判断。但计算机与人不同，它看不见、摸不着这些数据，不可能像人一样来完成任务。解决问题的关键，就是要把人解决问题的每一步思维过程描述出来。这也是所有学程序的人尤其是初学者感觉最难的地方。并且，程序设计思想并不是一下子就能培养的，我们高中阶段只能是慢慢引导学生学着去分析问题，将问题解决方法步骤化。所以课后我一直在思考，是否可以在上这部分内容之前给学生布置一个任务：闭上眼睛，将十根乱排的长短相差不大的小木棍从短到长排起来，要求每次最多只能比较两根。事后我也请一些人做过实验，发现每个人都有自己不同的想法，但都可以从程序设计的各种排序法中找出原型。　　2.细节也不容忽视　　为了说明冒泡排序的基本方法，我在各班上课时都按学号点了4位学生上讲台排队，没料到其中有一个班上来的4位学生中有个男生个子比女生都要矮，轮到他进行两两比较而被换到前面时，下面有学生发出了一些笑声，他难过得头都低下去了。男生对自己的身高其实是很在意的，这可能会伤及他的自尊心。是否先将男女生分开，再按学号点呢。看来，再小的细节也不容忽视。　　　　（作者单位：浙江象山中学）　　《冒泡排序算法》教学设计 章婷红