计算机数学基础-王信峰版第2节-算法.pptVIP

第二节 主要内容 1 算法的概念 2 简单算法举例 3 算法的特性 4 算法的表示 5 结构化程序设计方法 6 数值计算算法的收敛与稳定性 华罗庚----“烧水泡茶” “烧水泡茶”有五道工序：1、烧开水 （15分钟）2、洗茶壶 （2分钟）3、茶杯 （1分钟）4、拿茶叶 （1分钟）5、泡茶 （1分钟） 烧开水、洗茶壶、茶杯，拿茶叶是泡茶的前提。 问题：请同学们写出烧水泡茶的具体过程，进行比较和分析，比较的标准是哪个最省时间 。 方法比较 方法1： ?? 第一步：烧水； ?? 第二步：水烧开后，洗刷茶具，拿茶叶； ?? 第三步：沏茶。  方法2： ?? 第一步：烧水； ?? 第二步：烧水过程中，洗刷茶具，拿茶叶； ?? 第三步：水烧开后沏茶。 ①工序安排不同 甲：烧开水 同时 ，洗茶壶，洗茶杯，拿茶叶 乙：烧开水 之前 ，洗茶壶，洗茶杯，拿茶叶 丙：烧开水 之后 ，洗茶壶，洗茶杯，拿茶叶 ②花的时间不同， 甲： 16 分钟 乙： 20 分钟 丙： 20 分钟 1 算法的概念 1 算法的概念 2 简单算法举例 3 算法的特性 4 算法的表示 4.1 用自然语言表示算法 4.2 用流程图表示算法 小结： 流程图是表示算法的较好的工具。一个流程图包括以下几部分 ： (1)表示相应操作的框； (2)带箭头的流程线； (3)框内外必要的文字说明。 4.3 三种基本结构和N-S流程图 小结： 由三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。由基本结构所构成的算法属于“结构化”的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳转。 4.4 用N-S流程图表示算法 N-S图表示算法的优点 比文字描述直观、形象、 易于理解；比传统流程图紧凑易画。尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的，N--S流程图中的上下顺序就是执行时的顺序。用N--S图表示的算法都是结构化的算法，因为它不可能出现流程无规律的跳转，而只能自上而下地顺序执行。 小结： 一个结构化的算法是由一些基本结构顺序组成的。在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内(如循环中流程的跳转)；一 个非结构化的算法可以用一个等价的结构化算法代替，其功能不变 。如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法。 4.6 用计算机语言表示算法 5 结构化程序设计方法 1.2.2 算法的数值稳定性 算法的收敛性：该算法计算结果逐步接近所要的计算结果，称算法是收敛的，否则称不收敛的。收敛也有快慢之分，选择越快越好。 #include stdio.h void main( ) {int i,t; t=1; i=2; while(i=5) {t=t*i; i=i+1; } printf(″%d\n″,t); } 例 2.20 将例2.16表示的算法（求5!）用C语言表示。 一个结构化程序 就是用高级语言表示的结构化算法。用三种基本结构组成的程序必然是结构化的程序，这种程序便于编写、便于阅读、便于修改和维护。 结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。 结构化程序设计方法的基本思路是：把一个复杂问题的求解过程 分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。 采取以下方法来保证得到结构化的程序： 自顶向下； 逐步细化； 模块化设计； 结构化编码。 两种不同的方法： 自顶向下，逐步细化； 自下而上，逐步积累。 用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫 做“自顶向下，逐步细化”。 自顶向下，逐步细化方法的优点： 考虑周全，结构清晰，层次分明，作者容易写，读者容易看。如果发现某一部分中有一段内容不妥，需要修改，只需找出该部分修改有关段落即可，与其它部分无关。我们提倡用这种方法设计程序。这就是用工程的方法设计程序。 用一个算法进行计算，如果初始数据误差在计算中传播 使计算结果的误差增长很快，这个算法就是数值不稳定的. 计算 并估计误差. 由分部积分可得计算 的递推公式 若计算出 ， 代入（3.2），可逐次求出 的值. （3.2） 例5 而要算出 就要先计算 . 并取 ， 则得 ， 计算过程中小数点后第5位的数字按四舍五入原则舍入. 若用泰勒多项式展开部分和 用4位小数计算， 截断误差 当初值