人教A版高中数学必修三课件:1.1.1《算法的概念》PPT_图文

高中数学课件
灿若寒星整理制作

1.1.1《算法的概念》

教学目标
? 1.了解算法的含义,体会算法的思想; ? 2.能够用自然语言叙述算法; ? 3.掌握正确的算法应满足的要求; ? 4.会写出解线性方程(组)的算法。 ? 教学重点:1.通过实例体会算法思想,初步
理解算法的含义;2.解二元一次方程组、判 断一个数为质数和用“二分法”求方程近似 解的算法设计。
? 教学难点:用自然语言描述算法。

一.算法的基本概念
1什么是算法
算法(algorithm)一词源于算术(algorism),算 术方法的原义是一个由已知推求未知的运算过 程。后来,人们把它推广到一般,指算法是在 有限步骤内求解某一问题所使用的一组定义明 确的规则,甚至把把进行某一工作的方法和步 骤也称为算法。

例如,人们在计算过程中,先乘除,后加减,从 内到外去括号等规则,都是按部就班必须遵守的 算法。人类最早关于算法的记录存在于在两河流 域发现的公元前两三千年的泥板书上,其中的一 个典型例子就是计算利息何时能够够等于本金。 算法早期发展中值得一提的另一个成果应归功于 古希腊的欧几里得,他提出的计算最大公约数的 辗转相除法(又称欧几里得算法)至今仍在使用。

欧几里得是古代最有名望的学者之一,古希腊 数学家,几何学的鼻祖。公元前300年左右,他 所著《几何原本》13卷,是世界上最早公理化 的数学著作。在《几何原本》中他充分总结了 前人的生产经验和研究成果,从公理和公设出 发,运用演绎法,经过逻辑推理和数学运算, 创立了著名的欧几里得(简称欧氏几何)。
在《几何原本》中,欧几里得还阐述了关于求 两个整数的最大公约数的过程,这就是著名的 欧几里得算法——辗转相除法,其具体过程如 下:

设给定的两个正整数为m和n,求它们的最大 公约数的步骤为:
(1)以m除以n,令所得的余数为r(r必小于n);
(2)若r=0,则输出结果n,算法结束;否则,继续步骤(3)
(3)令m=n,n=r,并返回步骤(1)继续进行。

中国古代数学研究中也有许多有关算法的成果。 用我国传统的开方术求高次方程的近似根,是算 法上的一大成就。此外,在社会上得到广泛使用 的珠算口诀就可以看做是典型的算法,它把复杂 的计算(例如除法)描述为一系列按口诀执行的简 单的算珠拨动操作。 中国古代数学以算法为主要特征,其中最具代表 性的就是《九章算术》。

《九章算术》是战国、秦、汉时期数学发展的总结, 就其数学成就来说,堪称是世界数学名著。其内容按 类分章,以数学问题的形式出现,包括分数四则运算、 开平方与开立方(包括二次方程数值解法)、盈不足 术、各种面积和体积公式、线性方程组解法、正负数 运算的加减法则、勾股形解法(特别是勾股定理和求 勾股数的方法)等。其中方程组解法和正负数加减法 则在世界数学发展上是遥遥领先的。就其特点来说, 它形成了一个以筹算为中心,与古希腊数学完全不同 的独立体系。

在11~14世纪约300年期间著名的数学家的著 作中,如贾宪的《黄帝九章算法细草》,刘 益的《议古根源》,秦九昭的《数书九章》, 李治的《测圆海镜》和《益古演段》,杨辉 的《详解九章算法》、《日用算法》和《杨 辉算法》中,算法的特点得到了进一步的强 化和发展(其中包括发展了一套求高次方程 近似根的方法。

2。算法的一般特征
算法实际上是一种抽象的解题方法,它具有动态性。因 此,算法的行为非常重要。作为一个算法,应具有以下 四个特征。
1)能行性(effectiveness) 算法的能行性包括两个方面:一是算法中的每一个步 骤必须是能实现的。例如,在算法中,不允许出现分 母为零的情况;在实数范围内不能求一个负数的平方 根等。二是算法执行的结果要能达到预期的目的。通 常,针对实际问题设计的算法,人们总是希望能够得 到满意的结果。

(2)确定性(definiteness) 算法的确定性,是指算法中的每一个步骤都必须是有明 确定义的,不允许有模棱两可的解释,也不允许有多义 性。这一特征也反映了算法与数学公式的明显差异。在 解决实际问题时,可能会出现这样的情况:针对某种特 特殊问题,数学公式是正确的,但按此数学公式设计的 计算过程可能会使计算机系统无所适从,这是因为,根 据数学公式设计的计算过程只考虑了正常使用的情况, 而当出现异常情况时,该计算过程就不能适应了。

例如,某计算工具规定:大于100的数认为是比 1大很多,而小于10的数不能认为是比1大很多; 且在正常情况下出现的数或是大于100,或是小于 10.但指令“输入一个X,若x比1大很多,则输 出数字1,否则输出数字0”是不确定的。这是因 为,在正常的输入情况下,这一指令的执行可以 得到正确的结果,但在异常情况下(输入的x在 10与100之间),这一指令执行的结果就不确定 了.

例如,某计算工具具有七位有效数字(如

FORTRAN中的单精度运算),在计算下列三个
? ? 量A=,B1=0112,C=的和时?,10如12 果采用不同的运

算顺序,就会得到不同的结果,即

A+B+C=+1+=01012

? ? ? 1012

? ? A+C十B=++1=11012 ? 1012

而在数学上,A+B+C与A+C+B是完全等价的。

这可知,算法和计算公式是有差别的。

3)有穷性(finiteness)
算法的有穷性是指算法必须能在有限的时间内 执行完,即算法必须能在执行有限个步骤之后 终止。数学中的无穷级数,在实际计算时只能 取有限项,即计算无穷级数的过程只能是有穷 的。因此,一个数的无穷级数的表示只是一种 计算公式,而根据精度要求确定的计算过程才 是有穷的算法。

算法的有穷性还应包括合理的执行时间的含义。 如果一个算法的执行时间是有穷的,但却需要 执行千万年.显然这就失去了算法的实用价值。 例如,克莱姆(Cramer)规则是求解线性代数方 程组的一种数学方法,但不能以此为算法,这 是因为,虽然总可以根据克莱姆规则设计出一 个计算过程用于计算所有可能出现的行列式, 但这样的计算过程所需的时间实际上是不能容 忍的。

还例如,从理论上讲,总可以写出一个正确的弈棋程序, 而且这也并不是一件很困难的工作。由于在一个棋盘上安 排棋子的方式总是有限的,而且,根据一定的规则.在有 限次移动棋子之后比赛一定结束。因此.弈棋程序可以考 虑计算机每一次可能的移动,它的对手每一次可能的应答, 以及计算机对这些移动的可能应答等等,直到每个可能的 移动停止下来为止。此外,由于计算机可以知道每次移动 的结果,因此总可以选择一种最好的移动方式。但即使如 此,这种弈棋程序还是不可能执行,因为所有这些可能移 动的次数太多,所要花费的时间不能容忍。由上述两个例 子可以看出,虽然许多计算过程是有限的.但仍有可能无 实用价值。

(4)算法必须拥有足够的情报
一个算法是否有效,还取决于为算法的执行所提供的 情报是否足够。例如,对于指令“如果小明是学生, 则输出字母Y,否则输出N”。当算法执行过程中提供 了小明一定不是学生的某种信息时,执行的结果将输 出字母N;当提供的只是部分学生的名单,且小明恰在 此名单之中,则执行的结果将输出字母Y。但如果在提 供的部分学生的名单中找不到小明的名字.则在执行 该指令时无法确定小明是否是学生。

通常,算法中的各种运算总是要施加到各个运 算对象上,而这些运算对象又可能具有某种初 始状态.这是算法执行的起点或是依据。因此, 一个算法执行的结果总是与输入的初始数据有 关,不同的输入将会有不同的结果输出。如果 输入不够或输入错误,则算法本身也就无法执 行或执行有错。一般来说,只有当算法拥有足 够的情报时,该算法才是有效的;而如果提供 的情报不够,则算法并不是有效的。

综上所述,所谓算法,是一组严谨地定义运算 顺序的规则,并且每一个规则都是有效的且是 明确的,此顺序将在有限的次数下终止


相关文档

人教A版高中数学必修三 1.1.1 算法的概念 课件 (共30张PPT)
【高中课件】高中数学人教A版必修三1.1.1算法的概念课件ppt.ppt
人教A版高中数学必修三课件1.1.1算法的概念.ppt
最新人教A版高中数学必修三1.1.1《算法的概念》ppt配套课件
高中数学人教A版必修三 1.1.1 算法的概念 课件 (共17张PPT)
人教A版高中数学必修三课件《1.1.1算法的概念》新.ppt
人教A版高中数学必修三课件:1.1.1《算法的概念》PPT.pptx
人教A版高中数学必修三课件1.1.1算法的概念(共33张PPT)
人教A版高中数学必修三课件1.1.1算法的概念(共28张PPT)
人教A版高中数学必修三课件高一:1.1.1算法的概念.pptx.ppt
电脑版