当前位置:电子教案 >> 第六章

 

《中学数学研究》——第六章算法

 

   

2013级数学与应用数学

学科

中学数学研究

教师

梅俊雷

教学目标

掌握算法的基本知识。

重难点

算法的基本知识

 

   

新知课

教学方法

讲授法

教学内容与程序

 

一、算法概述

算法,一个既陌生又熟悉的名词。说陌生,因为算法概念从未进入我国中学数学教学大纲。新的高中数学课程标准破天荒地把算法作为重要内容列入必修课,自然出乎人们的意料。说到熟悉,那是因为从小学就开始接触算法。例如做四则运算要先乘除后加减,从里往外脱括弧,竖式笔算等等都是算法,只要按照一定的程序一步一步做,一定不会错。至于乘法口诀、珠算口诀更是算法的具体体现。因此,算法其实是耳熟能详的数学对象。一般地,算法是指在解决问题时按照某种机械程序步骤一定可以得到结果的处理过程。这种程序必须是确定的、有效的、有限的。

中国古代数学以算法为主要特征。吴文俊指出:“我国传统数学在从问题出发以解决问题为主旨的发展过程中,建立了以构造性与机械化为其特色的算法体系,这与西方数学以欧几里得《几何原本》为代表的所谓公理化演绎体系正好遥遥相对。肇始于我国的这种机械化体系,在经过明代以来几百年的相对消沉后,由于计算机的出现,已越来越为数学家所认识与重视,势将重新登上历史舞台。”吴文俊创立的几何定理的机器证明方法(世称“吴方法”),用现代的算法理论,焕发了中国古代数学的算法传统,享有很高的国际声誉。他因此于2001年获得了第一届国家最高科学技术奖。

20世纪上半叶,科学研究方式归结为两种方式:理论+实验。后来由于计算机技术能力的开发,计算成为第三种重要手段。未来的趋势是,“理论+实验+计算”将成为标准的科学研究方法。那么,计算机如何按照人的意愿进行计算呢?这就要靠算法。因此,毫不夸张地说,算法既是数学科学的重要基础,也是计算机科学的核心。

 

“算法”一词英译为“Algorithm”,数学史家发现了algorism(算术)一词的真实起源,它来自于阿拉伯著名数学家穆罕默德·伊本·穆斯·阿里·花拉子米在公元825年论述算术的著作《印度计算法》,书中系统介绍了阿拉伯数字和十进制记数法以及相应的算法。在我国,1980年的《辞海》还没有收入算法,只有算法论的条目(那是数理逻辑学科的一个分支,相当专业)。1988年出版的《中国大百科全书(数学卷)》,才有了莫绍揆先生撰稿的算法辞条。

一本早期的数学德文词典《数学大全辞典》,给出了Algorithms(算法)一词的如下定义:“在这个名称之下,组合了四种类型的算术计算的概念,即加法、乘法、减法、除法。”笼统地讲,算法是解决一个问题而采取地方法和步骤。

 

“算法”是一个与数的计算密切相关的概念。古代就有许多有名的算法,如古埃及乘法、求解某些二次方程的巴比伦方法、求两个自然数最大公约数的欧几里得算法等等。就整个数学发展的历史进程而言,不同时期、不同地域的数学一直存在两种不同的倾向:一种是逻辑演绎倾向;另一种是机械化算法倾向。前者以古希腊欧几里得《几何原本》为代表,后者则以中国古代数学名著《九章算术》为代表。《九章算术》采用应用问题的形式,共收录了246个问题,每个问题都包括“问”、“答”、“术”,经数学家刘徽作注后增加了“注”,共4部分。“问”是先提出问题,“答”则给出答案,再给出“术”,作为一类问题的共同解法,以后就可以利用“术”来解决其它同类问题。“术”是《九章算术》的核心内容,实际上就是一类问题的一种算法,这是中国古代数学的一大特征。“

 

 

数值算法举例:求

步骤1:使

步骤2:使,得到的积仍放在中;

步骤3:使的值加1

步骤4:如果,返回重新执行第2步;如果,则不再返回步骤2,而停止循环,此时中的值就是

非数值算法举例:201电话卡的使用步骤

步骤1:拿起话筒,在201机上拨通“201”;

步骤2:听到提示语言,按“1”或“2”,选择语言种类;

步骤3:拨卡号、密码;

步骤4:拨所需号码;

步骤5:有人接则通话,无人接可在等一会儿,仍无人接说明要找的人不在;

步骤6:放下话筒;

步骤7:结束。

 

在数学发展史上,算法数学与演绎数学相辅相成,彼此消长,不断推进着数学的发展。算法数学也促进了数学分支的诞生和发展,16世纪以后,符号代数、十进小数、对数计算、解析几何、微积分的诞生都与算法数学紧密相关,尤其是微积分的出现,并不是靠严格的演绎理论,而是以实际应用为动力,计算为手段才得以迅速发展,成为人类数学史上新的高峰。可以说,数学诞生于实际问题的计算,算法是计算数学的核心,它是十分古老的分支。随着电子计算机问世,现代计算数学得到迅猛发展,成为数学科学中与生产实际和科学实践联系最直接的部分。

“算法”在数学学科及计算机科学的发展中,发挥越来越重要的作用,并日益融入社会生活的诸多方面。随着电子计算机的出现及普及,算法化、程序化的思想与方法也已经渗透到商业、交通、国防、科技甚至教育等许多领域。如果在现代数学研究与应用以及数学的未来发展中挖掘这种十分重要而深刻的思想,在数学教育中逐步渗透这种思想与方法,会为学生适应社会发展的需要打下坚固的基础,算法思想也成为现代公民应具备的一种数学素养,算法已开始成为普通高中课程的组成部分。

 

 

算法具有以下五个重要特征:

⑴有穷性。一个算法必须保证执行有限步之后结束,且每一步都可在有限时间内完成。

⑵确定性。算法的每一步都应该是明确无误的,不能含义模糊,也不能产生二义性。

⑶可行性。一个算法是可行的,指的是算法中有待实现的运算都是基本运算,每种运算至少在原理上能由人用纸和笔在有限的时间内完成。

⑷输入。一个算法有若干个输入,以刻画运算对象的初始情况。

⑸输出。一个算法有若干个输出,以反映对输入数据加工后的结果。

 

 

算法的表示

⑴用自然语言描述算法;

假如有这样一句话:"先生对李先生说他的孩子考上了大学"。请问是张先生的孩子考上大学,还是李先生的孩子考上大学呢?仔细一想,发现这是一个会引起歧义的句子。这个例子告诉我们,使用自然语言表示某些意义时存在着缺陷,因此,除了简单问题以外,一般不用自然语言描述。

对于更一般形式的二元一次方程组  ,仿照上述具体数字系数的二元一次方程组的解法,采用自然语言来描述这个算法。

:输入值;

:先求乘数

:求,由

:求,由代入(1)式得

:输出

:结束。

⑵用伪代码描述算法

伪代码是用介于自然语言和计算机语言之间的文字和符号。

上述求一般二元一次方程组的算法也可用如下的伪代码表示:

BEGIN(算法开始)                    /*开始*/

input        /*输入值*/

                            /*赋值*/

       /*赋值*/

                 /*赋值*/

printf  方程组的解为             /*输出x,y*/

END                                  /*算法结束*/

用伪代码描述算法表达形式灵活,易读易写,不必考虑语法规则,容易表达设计人员的思想。用伪代码表示算法可以不必画出流程图(流程图的知识将在下面给出介绍),比较省时、省力、省篇幅,在修改算法时比修改流程图更为方便。而且伪代码与计算机语言比较接近,便于转化为计算机程序。

⑶用流程图描述算法

15分钟)。

 

 

三、算法举例

  欧几里得算法(辗转相除法)

利用欧几里得算法,可以求给定两个正整数的最大公约数,其基本过程如下:

E1.【求余数】以,并令为所得余数(

E2.【余数为0?】若,则本算法结束,是答案

E3.【互换】置,并返回步骤E1

 

实例:求出的最大公约数

课堂练习:求出的最大公约数

 

 

更相减损算法(辗转相减法)

《九章算术》第一章“方田”中题五、题六之后,给出“约分术”曰:“可半者半之,不可半者,副置分母之数,以少减多,更相减损,求其等也,以等数约之。”此术提供了一种求两数最大公约数的算法,与欧几里得算法有异曲同工之妙。“约分术”的意思是说:“若分子、分母全是偶数,则可用2约简。若分子、分母不全是偶数,则把分子、分母(我国古代是使用算筹为工具进行计算)分别放于不同的地方,然后由较大的数减去较小的数,并辗转相减直到两边剩余的数相等,这个数称为等数,它就是分子、分母的最大公约数,最后用等数来约分。”而按“约分术”的计算程序可用下图表示,从而求出49和91的最大公约数为7(等数)。

  91                         49

(91-49=)42                 (49-42=)7

(42-7=)35

(35-7=)28

(28-7=)21

(21-7=)14

(14-7=)7

课堂练习:求出的最大公约数

143                            121

                     143-121=)22                121-22=)99

                                                    99-22=)77

                                                    77-22=)55

                                                    55-22=)33

                                                    33-22=)11

                     22-11=)11

所以,

 

 

  “大衍总数术”——中国剩余定理

对于两两互质的正整数(称为“定数”),(称为“剩数”)。其中,也是正整数。对一次同余数组

;……;

为了求出其最小正整数解,则可用如下大衍总数术的算法程序,求解如下:

:求衍母

:求衍数

:求乘率 使

:求用数

:求各总

:求总数

:求最小正整数解,其中p是满足的最大正整数。

 

课堂练习:用这个算法可以立即解出我国南北朝时代(5-6世纪)名著《孙子算经》中“物不知数”问题:“今有物,不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?”

这个问题用现代数学符号可表示为求下列同余方程的整数解:

即上述算法中

求解过程如下:

:求衍母

:求衍数

:求乘率

:求用数

:求各总

:求总数

:求最小整数解(即

故求出解是23。

 

 

  排序算法

排序是数据处理领域一种最常用的运算。所谓排序,就是把一组数的序列按照值的递增或递减的次序(前者又称为升序或正序,后者又称为降序、逆序或反序)重新排列的过程。

⒈插入排序

插入排序是一种最简单的排序方法。它的基本操作是“插入”,故称为插入排序。其基本思想是:每次将一个待排序的数据元,插入到前面已经排好序的序列中的适当位置,使序列依然有序,直到待排序数据元全部插入为止。

例如课本实例。

⒉选择排序

选择排序也是一种简单的排序方法。它的基本操作是“选择”,故称为选择排序。其基本思想是:每一趟从待排序的数据元中选出最小(或最大)的一个元,顺序放在已排好序的序列的最后(或最前),直到全部待排序的数据元排完为止。

例如课本实例。

⒊冒泡排序

冒泡排序是一种交换排序,即它是借助“互换”来进行的。其思想方法是:通过比较相邻两数据元之间的大小,发现两个数据元的次序相反时即进行交换,直到没有反序的数据元为止。

例如课本实例。

⒋快速排序

快速排序又称为划分排序,是对冒泡排序的一种改进。在冒泡排序中,数据元的比较和交换是在相邻位置间进行的,其每次交换只能上移或下移一个相邻位置;而在快速排序中,数据元的比较和交换是从两端向中间进行的,较大的数据元一次就能够交换到后面单元,较小的一次也能交换到前面单元。

 

教学后记