优品课件之算法与程序设计选择排序.docx
- 文档编号:16925709
- 上传时间:2023-07-19
- 格式:DOCX
- 页数:10
- 大小:17.55KB
优品课件之算法与程序设计选择排序.docx
《优品课件之算法与程序设计选择排序.docx》由会员分享,可在线阅读,更多相关《优品课件之算法与程序设计选择排序.docx(10页珍藏版)》请在冰点文库上搜索。
优品课件之算法与程序设计选择排序
算法与程序设计――选择排序
算法与程序设计――选择排序
一、学情分析
通过上学期《算法与编程》部分的学习,学生初步了解算法及其表示、比较熟悉流程图设计;
本学期课程为《算法与程序设计》,对算法的理解更加深入,要求能通过VisualBasic实现简单算法;
在本课之前,学生应了解了流程图的应用,熟悉在一组数中求极值算法,对于排序及冒泡排序,学生比较熟练。
对于本部分,学生可能会对选择排序算法的原理理解较为困难,需要教师的引导学习。
学生应当在学习过程中认真听取教师对于算法的分析,在教师指导下能解释该算法的流程图,进而实现程序。
二、教学目标
知识性目标:
了解排序的概念、能在现实生活中列举出关于排序的实例
能对照冒泡排序,解释选择排序的优势,指出选择排序的策略,找出数字之间的逻辑联系
有迁移应用能力,能由此及彼,归纳排序中的数字规律,探索更有效率的排序算法
技能性目标:
具有模仿水平,在教师指导下可以表达出选择排序的思想,能对流程图作出解释
能独立完成流程图的绘制,对选择排序的各个环节比较熟练,并能在VisualBasic环境中规范地编写程序
情感、态度、价值观目标:
学生在学习过程中,通过亲身经历体验选择排序的实现过程,获得对此算法的感性认识
利用信息技术手段,开展交流合作,把自己对此算法的心得与他人交流,培养良好的信息素养,提升热爱科学的理念
三、重点难点
重点:
对选择排序原理的理解,绘制流程图,数据交换,调试程序
难点:
分析流程图
四、教学策略与手段
把握重点,先导入问题,复习排序定义,分析冒泡中数据交换次数多的问题,指出冒泡排序法效率不高,从而引出数据交换次数较少的选择排序算法
在教学过程中,可通过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个元素中最小数选举出来……
I←1:
Min←1:
J←2
开始
J d(J) Min←J Y Y N ……………… J=J+1 最后把每次选举出来的结果依次输出即可实现升序排列。 [学生完成第1遍处理过程的流程图片断] [依据流程图写出代码] DimMinAsInteger DimJAsInteger Min=1 ForJ=2ToN Ifd(J) NextJ [小组讨论] 在遍历了一遍后如果发现第1-N个数中的最小数d(Min),根据选择排序的思想,需要把它与第1个数字进行交换。 如何进行? [请同学发言]打个比方,在厨房里有一瓶酱油、一瓶醋和一个空瓶,如何利用这个空瓶实现酱油与醋? ――可先把酱油倒到空瓶中,再把醋倒到原来装酱油的瓶中,然后从原来的空瓶中把酱油倒到原来装醋现在已经空的瓶中,即可实现换位。 [教师]大家动动脑筋,用这种思想,试试把d (1)与d(Min)换位,并写出相应的代码。 DimTempAsInteger Temp=d(I): d(I)=d(Min): d(Min)=Temp’关键在于引入“空瓶”变量Temp [思考]是不是每遍历一遍后必须做这样的一次交换? ――不是必须的,只有当确实发现有比d (1)小的数后才交换 [教师]那怎么知道有没有发现比d (1)更小的数呢? I←1: Min←1: J←2 开始 J d(J) Min←J Y N N ……………… Min<>1? Temp=d (1) d (1)=d(Min) d(Min)=Temp Y J=J+1 ――其实在遍历之前我们已经假设第1个元素最小,即Min=1,所以在遍历一遍后我们只需要验证一下Min=1是否还成立。 成立则表明没有比第1个元素小的数,不成立则表明有比第1个元素小的数,且它的下标为Min,此时要交换d (1)与d(Min)。 [学生完善流程图及代码] IfMin<>1then Temp=d (1): d (1)=d(Min): d(Min)=Temp EndIf [教师]我们先前说过,对于规模为N的数组,需要遍历处理次数为N-1次,以上的流程就是这N-1次中需要重复做的事,对于重复处理的事,可以用什么结构? ――循环,以上的比较、交换即为循环体 [教师]大家试着把这个循环结构流程图画出来 [学生完善流程图及代码] 开始 J d(J) Min←J Y N 输出排序结果 N Min<>I? Temp=d(I) d(I)=d(Min) d(Min)=Temp Y I<=N-1 I←1 Y N 结束 I=I+1 J=J+1 Min=I: J=I+1 ForI=1ToN-1 Min=I ForJ=I+1ToN Ifd(J) NextJ IfMin<>IThen Temp=d(I): d(I)=d(Min): d(Min)=Temp EndIf NextI ForM=1ToN Print(Str(d(M))) NextM [调试程序] [扩展提高] 我们知道,冒泡排序的效率比较低,主要因为数据交换的次数多,那我们如何知道选择排序中数据交换的次数? [学生带着问题思考并实践] ――可利用一个自定义Integer型变量,初值0,记录数据交换次数,在程序交换数据部分令其自加1,程序结束时输出结果。 [完整的程序为] DimI,J,Min,M,CishuAsInteger Cishu=0 ForI=1ToN-1 Min=I ForJ=I+1ToN Ifd(J) NextJ IfMin<>IThen Temp=d(I): d(I)=d(Min): d(Min)=Temp: Cishu=Cishu+1 EndIf NextI ForM=1ToN Print(Str(d(M))) NextM Print(Str(Cishu)) 【问题研讨】 对于规模非常大时,计算选择排序与冒泡排序交换次数,研究时间、空间复杂度 利用网络、图书,发现更优秀的排序算法,并对各种算法进行效率分析 优品课件,意犹未尽,知识共享,共创未来! ! !
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 课件 算法 程序设计 选择 排序