88教案网

算法与程序设计——选择排序

经验告诉我们,成功是留给有准备的人。教师要准备好教案,这是教师需要精心准备的。教案可以让学生更容易听懂所讲的内容,让教师能够快速的解决各种教学问题。所以你在写教案时要注意些什么呢?急您所急,小编为朋友们了收集和编辑了“算法与程序设计——选择排序”,相信您能找到对自己有用的内容。

算法与程序设计——选择排序

一、学情分析

通过上学期《算法与编程》部分的学习,学生初步了解算法及其表示、比较熟悉流程图设计;

本学期课程为《算法与程序设计》,对算法的理解更加深入,要求能通过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

开始

JN?

d(J)d(Min)?

Min←J

Y

Y

N

………………

J=J+1

最后把每次选举出来的结果依次输出即可实现升序排列。

[学生完成第1遍处理过程的流程图片断]

[依据流程图写出代码]

DimMinAsInteger

DimJAsInteger

Min=1

ForJ=2ToN

Ifd(J)d(Min)ThenMin=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

开始

JN?

d(J)d(Min)?

Min←J

Y

N

N

………………

Min1?

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)。

[学生完善流程图及代码]

IfMin1then

Temp=d(1):d(1)=d(Min):d(Min)=Temp

EndIf

[教师]我们先前说过,对于规模为N的数组,需要遍历处理次数为N-1次,以上的流程就是这N-1次中需要重复做的事,对于重复处理的事,可以用什么结构?

——循环,以上的比较、交换即为循环体

[教师]大家试着把这个循环结构流程图画出来

[学生完善流程图及代码]

开始

JN?

d(J)d(Min)?

Min←J

Y

N

输出排序结果

N

MinI?

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)d(Min)ThenMin=J

NextJ

IfMinIThen

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)d(Min)ThenMin=J

NextJ

IfMinIThen

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))

【问题研讨】

对于规模非常大时,计算选择排序与冒泡排序交换次数,研究时间、空间复杂度

利用网络、图书,发现更优秀的排序算法,并对各种算法进行效率分析

相关推荐

高中数学必修三《算法与程序框图》教案


一名爱岗敬业的教师要充分考虑学生的理解性,高中教师要准备好教案,这是高中教师需要精心准备的。教案可以让学生更好的吸收课堂上所讲的知识点,帮助高中教师更好的完成实现教学目标。您知道高中教案应该要怎么下笔吗?为满足您的需求,小编特地编辑了“高中数学必修三《算法与程序框图》教案”,仅供参考,欢迎大家阅读。

高中数学必修三《算法与程序框图》教案设计

学习目标:

1.明确算法的含义,熟悉算法的三种基本结构:顺序、条件和循环,以及基本的算法语句.

2.能熟练运用辗转相除法与更相减损术、秦九韶算法、进位制等典型的算法知识解决同类问

题.

重点:

算法的基本知识与算法对应的程序框图的设计.

难点:

与算法对应的程序框图的设计及算法程序的编写.

要点梳理

知识点一:算法与程序框图

1.算法的定义:广义的算法是指完成某项工作的方法和步

骤,现代意义的算法是指可以用计算机来解决的某一类问

题的程序和步骤,这些程序或步骤必须是明确和有效的,

而且能够在有限步之内完成.

2.四种基本的程序框

3.三种基本逻辑结构

(1)顺序结构

(2)条件结构

(3)循环结构

要点诠释:

1.对于算法的理

解不能仅局限于解决

数学问题的方法,解

决任何问题的方法和

步骤都应该是算法.算法具有概括性、抽象性、

正确性等特点,要通过具体问题的过程和步骤

的分析去体会算法的思想,了解算法的含义.

2.在学习程序框图时要掌握各程序框的

作用,准确应用三种基本逻辑结构,即顺序结

构、条件分支结构、循环结构来画程序框图,

准确表达算法.

画程序框图是用基本语句来编

程的前提.知识点二:基本算法语句

1、输入语句

2、输出语句

3、赋值语句

4、条件语句

IF-THEN-ELSE格式

IF-THEN格式

5、循环语句

(1)WHILE语句

(2)UNTIL语句

要点诠释:

基本算法语句是程序设

计语言的组成部分,注意各语

句的作用,准确理解赋值语

句,灵活表达条件语句.计算机

能够直接或间接理解的程序语

言都包含输入语句、输出语句、

赋值语句、条件语句和循环语句

等基本算法语句.输入语句、输

出语句和赋值语句贯穿于大多

数算法的结构中,而算法中的条

件结构由条件语句来表述,循环

结构由循环语句来实现.学习中

要熟练掌握这些基本算法语句.知

识点三:算法案例

案例1、辗转相除法与更相减损术

1.利用辗转相除法求最大公

约数的步骤如下:

(1)用较大的数m

除以较小的

数n得到一个商(2)若

商和一个余数;≠0,则用除数n除以余数得到一个=0,则n为m,n的最大公约数;若;

为m,n的最大公约数;若

;„„

=0,此时所得到的和一个余数=0,则(3)若商≠0,则用除数除以余数得到一个和一个余数依次计算直至即为所求的最大公约数.2.更相减损术

(1)任意给出两个正数;判断它们是否都是偶数.若是,用2约简;若不是,执行第二步.

(2)以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小数.继续这个操作,直到所得的数相等为止,则这个数(等数)就是所求的最大公约数.

案例2、秦九韶算法

用秦九韶算法求一般多项式f(x)=anxn+an-1xn-1+„.+a1x+a0当x=x0时的值.

把n次多项式的求值问题转化成求n个一次多项式的值的问题,即求

v1=anx+an-1

v2=v1x+an-2

v3=v2x+an-3

„„..

vn=vn-1x+a0

的值的过程.案例3、进位制

进位制是一种记数方式,用有限的数字在不同的位置表示不同的数值.可使用数字符号的个数称为基数,基数为n,即可称n进位制,简称n进制.现在最常用的是十进制,通常使用10个阿拉伯数字0-9进行计数.

要点诠释:

我国古代数学发展的主导思想,就是构造“算法”解决实际问题.通过对这些案例的阅读、理解,同学们可以体会它们蕴含的算法及其思想.

方法指导

1、在理解算法的基础上,掌握算法的基本思想,发展有条理的思考与表达能力,提高逻辑思维能力.会用算法的思想和方法解决实际问题.从熟知的问题出发,体会算法的程序化思想,通过实践,主动思维,经历不断的从具体到抽象,从特殊到一般的抽象概括活动来理解和掌握.

2、涉及具体问题的算法时,要根据题目进行选择,以简单、程序短、易于在计算机上执行为原则.

3、注意条件语句的两种基本形式及各自的应用范围以及对应的程序框图.条件语句与算法中的条件结构相对应,语句形式较为复杂,要会借助框图写出程序.

4、利用循环语句写算法时,要分清步长、变量初值、终值,必须分清循环次数是否确定,若确定,两种语句均可使用,当循环次数不确定时用while语句.

5、复习算法案例时,要体会其中蕴含的算法思想,并能利用它解决具体问题.对课本涉及到的几种算法,同学们要在理解的基础上掌握其程序,并深刻体会古代数学中的算法思想.

高二数学期末知识点:算法与程序框图


高二数学期末知识点:算法与程序框图

1.算法的概念
(1)算法的定义:广义的算法是指完成某项工作的方法和步骤,那么我们可以说洗衣机的使用说明书是操作洗衣机的算法,菜谱是做菜的算法等等。
在数学中,现代意义的算法是指可以用计算机来解决的某一类问题的程序和步骤,这些程序或步骤必须是明确和有效的,而且能够在有限步之内完成。
(2)算法的特征:①确定性:算法的每一步都应当做到准确无误、不重不漏。不重是指不是可有可无的、甚至无用的步骤,不漏是指缺少哪一步都无法完成任务。②逻辑性:算法从开始的第一步直到最后一步之间做到环环相扣。分工明确,前一步是后一步的前提,后一步是前一步的继续。③有穷性:算法要有明确的开始和结束,当到达终止步骤时所要解决的问题必须有明确的结果,也就是说必须在有限步内完成任务,不能无限制的持续进行。
(3)算法的描述:自然语言、程序框图、程序语言。
2.高中二年级数学必修三算法与程序框图程序框图
(1)程序框图的概念:程序框图又称流程图,是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形;
(2)构成程序框的图形符号及其作用
(3)程序框图的构成
一个程序框图包括以下几部分:实现不同算法功能的相对应的程序框;带箭头的流程线;程序框内必要的说明文字。
3.高中二年级数学必修三算法与程序框图几种重要的结构
(1)顺序结构
顺序结构是最简单的算法结构,语句与语句之间,框与框之间是按从上到下的顺序进行的。它是由若干个依次执行的步骤组成的,它是任何一个算法都离不开的一种基本算法结构。
见示意图和实例:
顺序结构在程序框图中的体现就是用流程线将程序框自上而下地连接起来,按顺序执行算法步骤。如在示意图中,A框和B框是依次执行的,只有在执行完A框指定的操作后,才能接着执行B框所指定的操作。
(2)条件结构
如下面图示中虚线框内是一个条件结构,此结构中含有一个判断框,算法执行到此判断给定的条件P是否成立,选择不同的执行框(A框、B框)。无论P条件是否成立,只能执行A框或B框之一,不可能既执行A框又执行B框,也不可能A框、B框都不执行。A框或B框中可以有一个是空的,即不执行任何操作。
见示意图
(3)循环结构
在一些算法中要求重复执行同一操作的结构称为循环结构。即从算法某处开始,按照一定条件重复执行某一处理过程。重复执行的处理步骤称为循环体。
循环结构有两种形式:当型循环结构和直到型循环结构。
①当型循环结构,如左下图所示,它的功能是当给定的条件P成立时,执行A框,A框执行完毕后,返回来再判断条件P是否成立,如果仍然成立,返回来再执行A框,如此反复执行A框,直到某一次返回来判断条件P不成立时为止,此时不再执行A框,离开循环结构。继续执行下面的框图。
②直到型循环结构,如右下图所示,它的功能是先执行重复执行的A框,然后判断给定的条件P是否成立,如果P仍然不成立,则返回来继续执行A框,再判断条件P是否成立。以次重复操作,直到某一次给定的判断条件P时成立为止,此时不再返回来执行A框,离开循环结构。继续执行下面的框图。

高中数学必修三1.1.2程序框图与算法的基本逻辑结构(2)导学案


1.1.2程序框图与算法的基本逻辑结构(2)
【学习目标】
1.理解算法的三个基本逻辑结构.
2.掌握画程序框图的基本规则,会画一个算法的程序框图.
【新知自学】
知识回顾:
1.程序框图的定义?
2.程序框图中的顺序结构的示意图?

新知梳理:
1.条件结构的程序框图
算法的流程根据有不同的流向,处理这种过程的结构就是条件结构.它有入口和出口,但最后只有一个终结口.
试画出条件结构的示意图:

2.循环结构的程序框图
在一些算法中,经常会出现从某处开始,按照
反复执行某些步骤的情况,这就是循环结构.反复执行的步骤称为.
试画出循环结构的示意图:

循环结构有两种主要结构形式,
和.你能说出它们的特征吗?

对点练习:
1.算法的三种基本结构是().
A.顺序结构、条件结构、循环结构
B.顺序结构、流程结构、循环结构
C.顺序结构、分支结构、流程结构
D.流程结构、循环结构、分支结构
2.算法有三种结构,下列说法正确的是().
A.一个算法只能含有一种逻辑结构
B.一个算法最多可以包含两种逻辑结构
C.一个算法必须含有上述三种逻辑结构
D.一个算法可以含有三种逻辑结构的任意组合
3.在算法的逻辑结构中,要求进行逻辑判断,并根据结果进行不同处理的是哪种结构().
A.顺序结构
B.条件结构和循环结构
C.顺序结构和条件结构
D.没有任何结构
【合作探究】
典例精析
例题1、已知函数设计一个算法,输入自变量的值,输出对应的函数值.请写出算法步骤,并画出程序框图.

变式训练1、已知函数,试写出求该函数值的算法,并画出程序框图.

例题2、设计一个计算1+2+…+100的值的算法,并画出程序框图.

变式训练2、用程序框图表示:求

的值的一个算法.

例题3、求满足的最小正整数的程序框图.
给出以下一个程序框图,判断是否正确,若都不正确,请你给出一个正确的程序框图.

【课堂小结】

【当堂达标】
1.如图,阅读程序框图,则输出的=()
A.26B.35C.40D.57
2.如图所示的程序框图能判断任意输入的整数的奇偶性,则判断框内的条件是()
A.B.C.D.
3.如图所示的程序框图,输出的结果是,则输入的值为

【课时作业】
1.如图所示的是一个算法的程序框图,已知,输出的结果为7,则的值是()

A.9B.10C.11D.12
2.下列算法中,含有条件结构的是()
(A)1(B)2(C)3(D)4
A.求两个数的积
B.求点到直线的距离
C.解一元二次不等式
D.已知梯形两底和高求面积
3.如图所示的程序框图,其功能是()
A.输入的值,按从小到大的顺序输出它们的值
B.输入的值,按从大到小的顺序输出它们的值C.求的最大值
D.求的最小值

3.执行如图所示的程序框图,输出的T=

4.设计求的一个算法,并画出相应的程序框图.

高中数学必修三1.1.2程序框图与算法的基本逻辑结构(1)导学案


1.1.2程序框图与算法的基本逻辑结构(1)
【学习目标】
1.掌握程序框图的概念.
2.掌握画程序框图的基本规则,能正确画出含顺序结构的程序框图.
【新知自学】
知识回顾:
1.算法的概念

2.算法的特点

新知梳理:
1.程序框图
(1)定义
程序框图又称,是一种用、
及来表示算法的图形.
(2)表示
在程序框图中,算法的一个步骤通常用一个或几个的组合来表示:带有方向箭头将程序框连接起来,表示算法步骤.
(3)常见的程序框、流程线及其各自表示的功能
图形符号名称功能
感悟:学习这部分知识,要掌握各个图形的形状、作用及使用规则,画程序框图的规则如下:
(1)使用标准的图形符号.
(2)框图一般按从上到下、从左到右的方向画.
(3)除判断框外,大多数流程图符号只有一个进入点和一个退出点.判断框具有超过一个退出点的唯一符号.
(4)判断框分两大类,一类判断框“是”与“否”两分支的判断,而且有且仅有两个结果;另一类
是多分支判断,有几种不同的结果.
(5)在图形符号内描述的语言要非常简练清楚.
2.算法的顺序结构
任何一个算法各步骤之间都有明确的顺序性,在算法的程序框图中,由若干个依次执行的步骤组成的逻辑结构,称为顺序结构,用程序框图可以表示为:

在顺序结构中可能会用到哪几种程序框和流程线?

对点练习:1.下面对算法描述正确的一项是().
A.算法只能用自然语言来描述
B.算法只能用图形方式来表示
C.同一问题可以有不同的算法
D.同一问题的算法不同,结果必然不同
2.已知直角三角形两直角边长为,,求斜边长的一个算法分下列三步:
①计算;
②输入直角三角形两直角边长,的值;
③输出斜边长的值,其中正确的顺序是().
A.①②③B.②③①
C.①③②D.②①③
3.程序框图中表示判断框的是().
A.矩形框B.菱形框
C.圆形框D.椭圆形框
【合作探究】
典例精析
例题1.写出“判断整数n(n2)是否为质数”的算法步骤,并用图形表示写出的算法.

变式练习1:若一个三角形的三条边长分别为,令,则三角形的面积.你能利用这个公式设计一个计算三角形面积的算法步骤吗?.

你所写出的算法步骤如何用程序框图表示?

例题2.已知下图是“求一个正奇数的平方加5的值”的程序框图,若输出的数是30,求输入的数n的值.

变式练习2:已知点和直线,求点到直线的距离.设计算法,并画出程序框图.

【课堂小结】

【当堂达标】
1.下面的结论正确的是().
A.一个程序的算法步骤是可逆的
B.一个算法可以无止境地运算下去的
C.完成一件事情的算法有且只有一种
D.设计算法要本着简单方便的原则
2.算法的有穷性是指().
A.算法必须包含输出
B.算法中每个操作步骤都是可执行的
C.算法的步骤必须有限
D.以上说法均不正确
3.下面的程序框图的算法功能为交换两个变量的值,则在①处应填.

【课时作业】
1.看下面的四段话,其中不是解决问题的算法是().
A.从济南到北京旅游,先坐火车,再坐飞机抵达
B.解一元一次方程的步骤是去分母、去括号、移项、合并同类项、系数化为1
C.方程有两个实根
D.求1+2+3+4+5的值,先计算1+2=3,再计算3+3=6,6+4=10,10+5=15,最终结果为15
2.下列关于程序框图的说法,正确的个数是()
①程序框图只有一个入口,也只有一个出口;
②程序框图中的每一部分都应有一条从入口到出口的路径通过它;
③程序框图中的输入框必须紧跟在开始框后.
A.0B.1C.2D.3
3.如图所示的程序框图,其输出的结果是()

A.4B.5C.6D.13
4.写出求1+2+3+4+5+6+…+100的一个算法.可运用公式1+2+3+…+=直接计算.
第一步,取;
第二步,计算;
第三步,输出计算的结果.
5.已知圆的半径,设计一个求圆的周长和面积的近似值,并用程序框图表示.

6.已知一个等边三角形的周长为,求这个三角形的面积.设计一个算法解决这个问题,并用程序框图表示.

文章来源:http://m.jab88.com/j/45012.html

更多

最新更新

更多