高中数学第一章统计1.2排序问题与算法的多样性教案北师大版.DOC

1.2 排序问题与算法的多样性整体设计教学分析 在数据处理中，排序是一种最基本的活动.排序又是一个进行算法研究、分析和教学的理想题材.它可用于说明为达到同一目的，可以有许多的算法，其中有些是在某种衡量标准下是最优的，在另一种衡量标准下则不然. 安排排序问题作为专门一节，有以下几个方面的考虑：1.排序问题是一种重要的算法问题，排序算法是使用最频繁的算法.2.教科书前面涉及的算法要么是简单的，要么是学生学习过的.主要做的是描述工作，教科书欲通过排序算法展现算法设计的整个过程，从分析解决问题的算理到描述算法，画出流程图,让学生对算法设计有一个整体的认识.3.在算法设计的整体过程中，再次让学生复习算法的一些基本知识：算法的程序化思想、变量的设置、循环变量的设定、循环体的确定、终止条件的分析、算法流程图的绘制等等. 值得注意的是，我们对算法的叙述并不是严格的、一步到位的，而是采用学生熟悉的语言、熟悉的叙述方式，目的是让学生把握算法的基本思想程序化思想.在归纳概括中培养学生的逻辑思维能力.教师在教学中不要拘泥于教科书，可以穿插练习，让学生有机会模仿例题.先描述解决一个具体问题的步骤，然后通过归纳概括，总结出具有一般意义的算法.三维目标1.通过分析具体问题，抽象出算法设计的过程，培养抽象概括能力、语言表达能力和逻辑思维能力.2.通过经历算法设计的全过程，体会构造性解决问题的方法. 重点难点教学重点：经历算法设计的全过程，体会构造性解决问题的方法.教学难点：通过分析具体问题，抽象出算法设计的过程.课时安排1课时教学过程导入新课思路1. 在日常生活中，人们经常要查询信息.例如，在词典中查找某个词的读音和含义，在电话号码薄中查询某个电话号码.今天我们学习排序问题与算法的多样性，教师点出课题.思路2.某班有52名同学，一次数学单元测试后，数学老师要按从高到低的顺序将全班同学测试成绩排列起来，你能帮助这位老师设计一个算法吗？教师点出课题.推进新课新知探究提出问题1.什么叫排序？2.什么叫有序列？3.写出有序直接插入排序的算法.4.写出折半插入排序的算法.5.怎样对无序的数据列排序？讨论结果：1.为了便于查询和检索，我们常常根据某种要求把被查询的对象用数字（或者符号）表示出来，并把数字按大小排列，是信息处理中一项基本的工作，通常称为排序.2.按顺序排列的数据列称为有序列.3.对于一个有序列：a1a2a3an，欲将新数据A插入到有序列中，形成新的有序列.其算法是：将数据A与原有序列中的数据从右到左依次进行比较，直到发现某一数据ai使得aiA，把A插入到ai的右边；如果数据A小于原有序列中的所有数据，则将A插入到原序列的最左边.4.先将新数据与有序列中的“中间位置”的数据进行比较.若有序列有2n+1个数据则“中间位置”的数据指的是第n+1个数，若有序列有2n个数据,则“中间位置”的数据指的是第n个数.如果新数据小于“中间位置”的数据，则新数据插入的位置应该在靠左边的一半；如果新数据等于“中间位置”的数据，则将新数据插入到“中间位置”的数据的右边；如果新数据大于“中间位置”的数据，则新数据插入的位置应该在靠右边这一半.也就是说，一次比较就排除了数据列中一半的位置.反复进行这种比较直到确定新数据的位置，像这样的插入排序方法我们称之为折半插入排序方法.5. 对一组无序的数据列进行排序时，通常将这组无序的数据列的第一个数据看成一个有序列，将第二个数据插入到这个有序列得到一个有序列；然后，将第三个数据插入到上述有序列中，又得到一个有序列，按照这种方法，直到将最后一个数据插入到有序列中，得到一个有序列，这样实质上就是完成了对无序的数据列排序，最后得到的有序列就是对无序的数据列排序的结果.应用示例例1 对于有序列13,27,51,57,82,现在要将数据52插入到数据列中.请设计算法确定数据52在序列中的位置,并用自然语言表述算法：a1a2a3a4a51327515782解：求解这个问题的基本思路是：将52从右向左逐个与有序列中的数据进行比较,确定52在序列中的位置,将其插入构成一个新的序列.点评：本题解答过程还可用图1描述.图1例2 对无序的数据列49,38,65,97,76,13,27,49排序.解：首先,只有一个数的序列49是有序列,我们将38插入到有序列49中,得到有两个数据的有序列：38,49.然后,将第三个数据65插入到上述有序列中,得到有序列：38,49,65.按照这种方法,直到将最后一个数据49插入到有序列中,得到13,27,38,49,49,65,76,97.这样,就完成了整个数据列的排序工作.点评：有序列插入排序算法是解决这个问题的关键.例3 用折半插入排序法将60插入有序列20,25,56,67,90,构成一个新的有序列.a1a2a3a4a52025566790解：首先选择有序列的“中间位置”的数据a3=56,将60与a3进行比较，显然60a3,所以60应该排在a3的右边.再取余下数据列a4,a5的“中间位置”的数据a4=67,与60比较,60a4，所以215应该排在a4的右边.再取余下数据列a5,a6,a7的“中间位置”的数据a6=216,与215比较，215a5,因此215应插在a5和a6中间.2.将27插入到无序数据列12,91,32,40,29中,分别用两种方法来完成,并用自然语言写出排序算法的步骤.解：方法一：首先,将27放入无序数据列中为27,12,91,32,40,29.然后,对此无序数据列进行排序.只有一个数的序列27是有序列,我们将12插入到有序列27中,得到有两个数据的有序列12,27.将第三个数91插入到上述有序列中,得到有序列12,27,91,按照这种方法,直到将最后一个数据29插入到有序列中,得到12,27,29,32,40,91.方法二：首先,将无序数列12,91,32,40,29排序后变为有序列12,29,32,40,91.然后,用折半插入排序法,将27插入有序列12,29,32,40,91中,得到12,27,29,32,40,91.拓展提升“字典序”是日常生活中常见的一种排序方法,我们以英语单词排序为例来介绍“字典序”.英语字母有一个自然序：a,b,c,x,y,z.这是建立“字典序”的基础.通常按照下面的原则把所有的英语单词排一个顺序,我们称为字典序.(1)比较单词act和bank.它们的第一个字母不同,a在b之前,故在字典中act排在bank的前面.(2)比较单词China和Chinese.从第一个字母开始,找出第一个不相同的字母a和e,a在e之前,故在字典中,China排在Chinese的前面.(3)比较单词act和action.它们前三个字母相同,act没有第四个字母,规定act排在action之前.了解了“字典序”后,请大家试按字典序比较大小,用直接插入排序法,将序列Tim,Kay,Eva,Roy,Dot排序,用自然语言写出排序算法的步骤.解：步骤：把Tim看成有序列,把Kay插入得Kay,Tim;把Eva插入Kay,Tim得Eva,Kay,Tim;把Roy插入Eva,Ka