刘天顺——中学数学——排序问题与算法的多样性教学设计.doc

排序问题与算法的多样性
陕西省西乡县第二中学数学组 刘天顺
一．概述
[科 目] 中学数学，高二年级
[教材依据] 北师大版高中课程标准实验教课书，必修三，第二章1.2
[课 时] 一课时（40分钟）
[教材分析]
为了便于查询和检索,我们常常根据要求把被查询的对象用数字(或者符号)表示出来，并把数字按小大排序,是信息处理中一项基本的工作，通常称为排序，排序的算法很多，这里给大家介绍一些经常使用的排序方法，通过对解决具体问题过程与步骤的分析，体会算法的思想，了解算法的含义，让学生体会到同一问题可能存在多种算法，这些算法之间有优劣之分，体会算法学习的必要性。
[价值及重要性]
解释选择排序的优势，指出选择排序的策略，找出数字之间的逻辑联系。有迁移应用能力，能由此及彼，归纳排序中的数字规律，探索更有效率的排序算法。
[教学重点] 算法的基本思想。
[教学难点] 算法的基本思想。

二、教学目标分析
1．知识和技能目标
1）进一步理解什么是；算法，知道算法的多样性；
2）能够对设计的算法做简单的评价。
2．过程与方法目标
通过对解决具体问题过程与步骤的分析，体会算法的思想，了解算法的含义，让学生体会到同一问题可能存在多种算法，这些算法之间有优劣之分，体会算法学习的必要性。
3．情感、态度、价值观目标
1）通过算法的学习，进一步理解数学与现实世界的关系，数学与计算机技术的关系。
2）通过算法的学习，将许多复杂问题的算法写成程序，交给计算机完成，提高学生学习数学的兴趣。

三、学习者特征分析
通过上学期《算法与编程》部分的学习，学生初步了解算法及其表示、比较熟悉流程图设计。
本学期课程为《算法与程序设计》，对算法的理解更加深入，要求能实现简单算法。
在本课之前，学生应了解了流程图的应用，熟悉在一组数中求极值算法，使学生对于排序比较熟练。
对于本部分，学生可能会对选择排序算法的原理理解较为困难，需要教师的引导学习。学生应当在学习过程中认真听取教师对于算法的分析，在教师指导下能解释该算法的流程图，进而实现程序。

四、教学策略选择与设计
把握重点，先导入问题，复习排序定义，分析冒泡中数据交换次数多的问题，指出冒泡排序法效率不高，从而引出数据交换次数较少的选择排序算法
在教学过程中，可通过Flash演示材料，比较直观地把抽象的问题简单化，由“流程图雏形绘制”-“逐步完善流程图”-“程序实现”-“调试”的过程，让学生熟练此算法与程序实现。
在教学中可灵活运用小组合作、分组讨论、小组间竞赛等手段进行教学，通过发散性思维的培养，增强学生对知识的探索能力。

五、教学资源与工具设计
准备充分的演示材料、相关数据；计算机，多媒体，幻灯片。

六、教学过程
（一）复习回顾
1．算法的定义：解决某类问题的一系列步骤或程序；
2．算法思想的本质：程序化；
3．算法的特点：有输入，有输出，有穷性，确定性，有效性；
4．算法设计的原则：正确性，可读性，高效率与低存储量需求；
5．算法描述的语言：自然语言，流程图，程序设计语言。
（二）新课讲解
1． 课题引入：
(1) 你会使用这些字典吗？
？
(2) 问题：新来的同学小黄升高1.75cm，在班上是中等升高，因为做操的需要，体育老师要将他插到队中，你认为老师应该怎样做？
2．象这样一种在已经按一定顺序排好的序列（有序列）中插入，我们就叫它有序列直接插入排序算法，
有序列直接插入排序的算法定义：对于一个有序列： ≤ ≤---- ≤ .欲将新数据A插入到有序列中，形成新的有序列，其做法是：将数据A与原有序列中的数据从右到左（也可以从左到右）进行比较，直到发现某一数据 使得 ≤A，把A插入到 的右边；如果数据A小于原有序列中的所有数据，则将A插入到原序列的最左边。上面的排序算法通常称为有序列直接插入排序的算法
例1：把数据52插入到有序列{13,27,51,57,82}中构成一个新的有序列，请设计算法确定52在序列中的位置，并用自然语言表达算法。
解：算法：
（1）比较52与82, ∵ 52 <82∴52放82 左边；　　
（2）比较52与57, ∵ 52 <57∴52放57左边；
（3）比较52与51, ∵ 52 >51∴52放51与57中间；
（4）得到新有序列{13,27,51,52,57,82}。
学生讨论：要将8插入到{1,3,5,7,9,11,13}中，我们怎样考虑？
确定8在原系列中的位置，使8小于或等于原系列中右边的数据，大于或等于左边的数据
将这个位置空出来，将数据8插进去
1
3
5
7

9
11
13
例题2：已知有一组系列{13,27,38,39,43,47,48,51,57,66,74,82}，现要将数据52插入到数据中。
数据系列
1
2
3
4
5
6
7
8
9
10
11
12
原系列号
13
27
38
39
43
47
48
51
57
66
74
82
请设计算法，确定52在新数据中的位置，请将52插入系列中
解：算法：
（1）确定52的位置：从有到左比较系列数与52的大小，使52在两个数之间，位置为9
（2）插入数据，位置9以后的数据后移一位，在9位置插入52
数据号
1
2
3
4
5
6
7
8
9
10
11
12
13
原系列
13
27
38
39
43
47
48
51
57
66
74
82

排后系列
13
27
38
39
43
47
48
51
52
57
66
74
82
思考：此题是否还有其它方法呢？
3．引入有序列的折半插入排序算法：
先将数据与有序列中“中间位置”的数据进行比较，若有序列有2n+1个数据则“中间位置”的数据指的是第个n+1数；若有序列有2n个数据则“中间位置”的数据指的是第n个数;如果新数据小于“中间位置”的数据，则新数据插入的位置应该在靠左边的一半；如果新数据等于“中间位置”的数据，则新数据应插入到“中间位置”的数据的右边；如果新数据大于“中间位置”的数据，则新数据插入的位置应靠右边一半
即一次比较就排除了数据列中一半的位置，反复进行比较直到确定新数据的位置．
例1：分析：

13
27
51
57
82
首先，选择有序列的“中间位置”数据 =51,将52与 进行比较，显然52> ,所以52应排在的右边:

13
27
51
52
57
82
　 然后，取余下数据列{, }的“中间位置”的数据=57与52比较，显然52< ,因此52应插到的左边：
讨论：例2写出算法
（三）课堂练习：
1．分别用两种方法将数据210插入到有序列{6,56,98,114,156,320,421}中，用自然语言写出排序算法的步骤．
解：
方法１直接插入法：
⑴比较210与421,∵210<421∴210放421左边；
⑵比较210与320,∵210<320∴210放320左边；
⑶比较210与156,∵210>156∴210放156和320之间；
⑷得到新的有序列{6,56,98,114,156,210,320,421}；
方法2折半插入法：⑴取有序列中间数114<210
取114右边有序列中间数320>210⑶取320左边有序列中间数156<210⑷将210插入到156和320之间⑸得出新的有序列。
2．用直接插入排序法将61插入{13,37,40,55,65,76,97}中，共比较了（　）
A.3次 B.4次 C.5次 D.6次
3．用折半插入排序法将10插入有序列{7,9,11,12,15}中第2次是10与（　）的比较
A.10与7 B.10与9 C.10与12 D.10与15
思考题：
如何将无序列{15,3,10,12,8}从小到大排列，用自然语言写出算法．
（四）课堂小结：
(1)有序列折半插入排序的思想和算法
(2)有序列直接插入排序的思想和算法
(3)注意理解同一个问题算法的多样性及各自的优缺点
（五）课后作业：
教材 p86习题2-1A组8,9。
补充练习：用斜二测画法画出正方形的内切圆。
六，[板书设计]
（一）复习回顾，问题引入
（二）介绍排序概念和有序列概念。
（三）（1）直接插入排序
（2）折半插入排序
（四）例题分析
（五）课堂练习与交流
（六）学生讨论比较直接插入排序和折半插入排序总结各自特点，体会排序问题与算法的多样性。
（七）思考与交流无序列排序问题。
（八）由学生讨论并总结课堂收获。
演示型课件资源应用计划表
（注：凡是需要用到信息化资源的知识点才需要填写此表）
知识点
资源名称
素材类型
水平
来源
使用时间
应用方式和作用
1复习回顾，问题引入

算法的相关内容
图像＋文本
识记
现有，
下载
3分钟
复习回顾，问题导入，激发学习兴趣
2介绍排序概念和有序列概念
通过图片信息了解更多关于排序的信息
文本
感知与体验，识记
现有
5分钟
通过联系所学知识，介绍新的概念。开门见山，给出概念，引入课题。
3引入直接插入排序思想和算法
例1
图表＋文本
分析，理解，应用
现有，
开发
8分钟
教师指导，例题分析讨论及讲解，引入直接插入排序思想和算法。
4引入折半插入排序思想和算法
例2
图表＋文本
分析，理解，应用
现有，
开发
10分钟
教师指导，例题分析讲解，引入折半插入排序思想和算法。
5课堂练习；
思考与交流无序列排序问题。
课堂练习题；
思考题
文本
分析，理解，应用，综合
现有，
开发
10分钟
学生小组讨论及体会排序问题与算法的多样性，全班交流总结，教师指导并汇总。
6课堂小结
归纳，
小结
文本
综合，评价
现有，
开发
4分钟
教师归纳，学生提问。
资源内容描述说明（请详细说明此知识点信息化资源的主要内容，此表需要与教学设计紧密挂钩，同时在收集、下载、处理和开发素材的过程中不断修改与完善）：
（样式：资源名称，主要内容）
1． 复习回顾算法的定义，思想的本质，特点，原则及语言。再思考老师提出的问题。
2． 通过复习和提问导入排序和有序列的概念，介绍一些经常使用的排序方法。通过问题引入让学生理解掌握排序和有序列概念。
3． 通过例1的分析和讲解引入直接插入排序思想和算法。并让学生讨论相应问题。
4．通过例题2的分析和讲解引入折半插入排序的思想和算法。然后让学生思考其他方法。
5．经过前面的一系列活动，学生了解了排序及算法的基本思想和概念，还能认识折半插入排序的思想和概念。现在通过练习题让学生讨论、分析比较并总结出直接插入排序和折半插入排序各自特点，体会排序问题与算法的多样性。最后留一个思考题让学生思考与交流无序列排序问题。
6. 由学生讨论并总结课堂收获，然后老师进行最后归纳。

说明：
1) 水平：知识和技能的掌握水平，分为识记，理解，应用，分析，综合，评价
2) 名称：为此知识点的信息化资源起一个名字
3) 类型：指图形/图像、视频、音频、文本、动画（包括flash），或者上述几类的组合，比如：“图+文+声”，注，可以自定义其它类型（一般以超级链接的形式来集成中演示型课件中），如认知工具类
4) 来源：开发、现有、现有需修改、下载
5) 使用时间：资源在课堂教学中使用的时间
6) 应用方式：该资源在教学中如何使用？它起什么作用？

6