模块5-2.ppt

1、计算机应用基础,模块一计算机概论 模块二计算机基本理论 模块三微机操作环境 模块四计算机网络基础 模块五计算机程序设计基础 模块六数据库基础 模块七计算机安全,2020/7/28,程序设计基础知识,5.1 程序与程序设计语言 5.2算法与算法设计 5.3程序结构 5.4结构化程序设计方法,2020/7/28,不只是计算问题有算法，实际上任何一个问题的进行过程都有它自己的算法。解决任何问题都要确定有哪些操作步骤，以及如何控制各步骤的进行。,生活中的算法问题,例1: 一天中的时间安排问题,例2: 处理某一件事情的具体步骤,例3: 红、蓝两个墨水瓶中的墨水互换,算法就是解决实际问题的方法和步骤。,一

2、、算法,5.2 算法与算法设计,1. 算法的概念,什么是算法?,2020/7/28,5.2 算法与算法设计,决定了算法的执行顺序 控制结构有：顺序结构、选择结构、循环结构。 算法的控制结构也是组成程序的基本结构。,算术运算、逻辑运算、比较运算和数据传送,1.基本功能操作,2. 控制结构,算法的 基本要素,2. 算法的基本要素,由上例可见任何简单或复杂的算法都包含两个基本要素。,2020/7/28,3. 算法的基本特征,输出是指与输入有某种特定关系的量，是算法进行信息加工后得到的结果,有穷性,一个算法必须在执行有限个操作步骤后终止,确定性,算法中每一个步骤都有确切的定义,不可出现任何二义性,可行

3、性,算法中每一步操作都能有效执行 （如：一个数被0 除的操作就是无效的）,有零个 或多个输入,输入是指算法开始之前所需要的原始数据,有一个 或多个输出,5.2 算法与算法设计,2020/7/28,4. 算法的分类,计算机算法可分为两大类： 数值运算算法： 求解数值； 非数值运算算法： 事务管理。,例1: 数值计算问题：结构静力分析计算需要解线性代数方程组。,例2: 非数值计算问题：计算机对弈 算法对弈的规则和策略 模型棋盘及棋盘的格局,5.2 算法与算法设计,2020/7/28,二、算法设计的原则,1.正确性：对于一切合法的输入数据都能得出满足要求的结果。,2.可读性：算法应该易理解，便于交流

4、,3.健壮性：当输入非法数据时，算法应恰当地作出反应或进行相应处理。,4.高效率与低存储量需求：算法执行时间较少，算法执行所需存储空间较小。,5.2 算法与算法设计,2020/7/28,三、算法的表示,自然语言 流程图 结构化流程图（N-S图） 伪代码 PAD图(Problem Analysis Diagram） 计算机语言,5.2 算法与算法设计,2020/7/28,1. 流程图,用规定的一系列图形、流程线和文字说明算法中的基本操作和控制流程。,5.2 算法与算法设计,流程图包括： 表示相应操作的框； 带箭头的流程线； 框内外必要的文字说明。,2020/7/28,（1）图形符号,5.2 算法

5、与算法设计,起止框,判断框,处理框,输入/输出框,注释框,流向线,连接点,2020/7/28,图 c,例：连接点的使用,图 A,图 B,等价,图A+图B等价于图C,5.2 算法与算法设计,2020/7/28,（2）用流程图表示算法,例1：求给定半径R的圆面积和圆周长。,5.2 算法与算法设计,算法： 圆面积 S=* R2 圆周长 L=2*R,2020/7/28,5.2 算法与算法设计,开始,输入a,b,c,x,xa？,输出 f,结束,Y,N,选择结构,（2）用流程图表示算法,2020/7/28,例3：上节求12345，即5。用流程图表示法,方法一：,方法二：,开始,循环结构,循环体,2020/

6、7/28,例4：求 S=1+2+3+.+100,0s; s+1s s+2 s . s+100 s,0s s+i s (循环) (i=1,2,.,100),5.2 算法与算法设计,循环体,2020/7/28,例5: 给定K值，求T=1+2+3+K。,5.2 算法与算法设计,K=5，T=0 I=1：T=0+1=1，I=1+1=2 I=2：T=1+2=3，I=2+1=3 I=3：T=3+3=6，I=3+1=4 I=4：T=6+4=10，I=4+1=5 I=5：T=10+5=15，I=5+1=6,0 T T+I T(I=1,2,3,K),2020/7/28,2. NS流程图,5.2 算法与算法设计,由

7、于流程线的任意转向性，传统流程图无法保证自顶向下的程序设计，使模块之间的调用关系难以表达。故两位美国学者 I.Nassi 和B.Shneiderman于1973年提出了无流程线的N-S流程图。 其根据是：既然任何算法都是由前面介绍的三种结构组成，所以各基本结构之间的流程线就是多余的，因此，N - S图也是算法的一种结构化描述方法。,2020/7/28,（1）图形符号,5.2 算法与算法设计,2020/7/28,5.2 算法与算法设计,2020/7/28,5.2 算法与算法设计,2020/7/28,5.2 算法与算法设计,2020/7/28,（2）用N-S流程图表示算法,例：求给定半径R的圆面积

8、和圆周长。,5.2 算法与算法设计,2020/7/28,例：求给定数R的绝对值。,5.2 算法与算法设计,2020/7/28,例: 给定K值，求T=1+2+3+K。,循环,循环体,5.2 算法与算法设计,2020/7/28,3.伪代码,伪代码也是描述算法常用的工具之一； 类似英语的表示形式； 部分英语和部分结构化代码的组合。,5.2 算法与算法设计,2020/7/28,伪代码描述算法的一般组成：,算法头：算法的名字。 目的、条件和返回值： 目的： 有关算法要做什么的简短说明 前置条件：列出算法所有前驱条件 后置条件：指出算法产生的影响 返回值： 算法返回的结果或无返回值 语句序号：表示语句之间

9、的附属关系。,5.2 算法与算法设计,2020/7/28,例：用伪代码描述在一数列中找最小值的算法。,Algorithm （算法）：Finding Smallest Purpose（目的）：在一数列中找最小值 Pre（前置条件）：List of numbers（数列） Post（后置条件）：None Return（返回值）：The smallest,3,2,4,1,6,a:,S,3,2,1,算法：设数列中第一个数为最小值S，然后用后续数依次与S比较，若比S小，则用该数替换原S的值，全部比较完成后S即最小值。,5.2 算法与算法设计,2020/7/28,1.Set smallest to the

10、 first number 2.Loop(not end of list) 2.1 if(next number smallest) 2.2.1 set smallest to next number 2.2 end if 3. end loop 4. return smallest End Finding Smallest,循环,循环体,5.2 算法与算法设计,2020/7/28,1. 数列ai ( i=1,5 ) 2. a1 S, 2 i 3. while(i5) 3.1 if(aiS ) then ai S endif 3.2 i+1i end while 4. return S,伪代码

11、不一定按上述严格的格式，且可以使用汉字，只要把算法表达清楚即可。,循环,循环体,5.2 算法与算法设计,2020/7/28,4.PAD图 PAD（Problem Analysis Diagram），是近年来在软件开发中被广泛使用的一种算法的图形表示法。 与前述的流程图、N-S图相比，PAD图除了自上而下以外，还有自左向右的展开，所以，如果说流程图、N-S图是一维的算法描述的话，则PA D图就是二维的，它能展现算法的层次结构，更直观易懂。,5.2 算法与算法设计,2020/7/28,选择结构(1) 单分支选择，条件为真执行A (2) 两分支选择，条件为真执行A，为假执行B。(3) 多分支选择，当

12、I = I1时执行A，= I2时执行B，I = I3时执行C，I = I4时执行。,PAD图的几种基本形态：,顺序结构,2020/7/28,循环结构while型循环，do - while型循环。,PAD图的几种基本形态：,5.2 算法与算法设计,2020/7/28,例：输入三个数，然后输出其中最大的数。 PAD图表示为：,例：猴子吃桃问题：有一堆桃子不知数目，猴子第一天吃掉一半，觉得不过瘾，又多吃了一只，第二天照此办理，吃掉剩下桃子的一半另加一个，天天如此，到第十天早上，猴子发现只剩一只桃子了，问这堆桃子原来有多少个？,5.2 算法与算法设计,2020/7/28,s=a1; i=2; whil

13、e(i=5) if(ais ) s = ai; i= i+1; return s;,4. 计算机语言,循环,循环体,5.2 算法与算法设计,2020/7/28,四、几种常用的算法,1. 枚举法,也称为穷举法，即一一的列举。该方法经常用于不定方程的求解问题。如“百钱买百鸡问题”。,例1：,鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一，百钱买百鸡 ，问鸡翁、鸡母、鸡雏各几何？,解：用x、y、z分别代表公鸡、母鸡和小鸡的数量， 列出方程为：,x+y+z=100 5x+3y+z/3=100,根据题意可知x、y、z的范围：分别约是正整数20、30；100，简单的解题方法是：假设一组x、y、z的值，一一

14、带入方程组求解，找出全部可能的组合，以得到所有满足方程组的解。,5.2 算法与算法设计,2020/7/28,枚举法例：,2020/7/28,枚举法解题的步骤如下：,(1) 分析题目,确定答案的大致范围。 (2) 确定列举方法，常用的有顺序列举、排列列举和组合列举。 (3) 实验所有可能范围内的情况。 (4) 实验后得到满足题目条件的一组或多组答案，或无答案。,枚举法的特点：,算法简单，容易理解，因为要用可能范围内的数值一一去试，所以运算量较大。枚举算法以循环结构实现。,5.2 算法与算法设计,2020/7/28,2. 迭代法,迭代法是数值近似求解的方法。科学计算上很多问题可用这种方法解决。,例

15、1：,计算 s=1+2+3+4+100,迭代法有精确迭代法和近似迭代法。精确迭代法指算术本身提供了问题的精确解，如对N个数求和、求均值、方差、对方程求近似解等。,迭代方法如下:,5.2 算法与算法设计,2020/7/28,例2：,牛顿迭代法：,1. 估计实根可能的范围,任选一个接近于真实根x的近似根x1。,2. 由 x1求出f(x1)。,3. 求f(x1)。,4. 由图可知：f(x1)=f(x1)/(x1-x2) 所以 x2=x1-f(x1)/f(x1) 同理 xn=xn-1-f(xn-1)/f(xn-1),5. 由x2求出f(x2)再求f(x2)及x3， 重复以上步骤，依次求出x4、 x5、

16、xn 直到前后两次求出的近似根| xn+1- xn| 此时就认为xn+1是足够接近真实根的近似根。,假设函数f(x)在某区间内为单调函数,(即在此范围内函数值单调增 加或单调减少)且有一个实根,用牛顿迭代法求f(x)的根的方法为：,迭代法例：,2020/7/28,xn=0.5*(xn-1+a/xn-1),2020/7/28,5.2 算法与算法设计,3. 递推和递归法,这也是程序中常用的两种算法，最常见的如用于计算级数。这种方法一般给出数列的前项与后项的递推公式，然后计算数列的通项。,例1：,已知某数列为1,1,2,3,5,8,13,.,求第n项的值。,(1) 首先确定 f(1)=1；f(2)=

17、1; (2) 计算 f(3)=f(1)+f(2); f(4)=f(3)+f(2); (3) 依此递推下去可知 f(n)=f(n-1)+f(n-2) 。,这就是该数列的通项公式。,递推法: 由已知的前两项可得下一项，依次递推下去，得到第n项得值。,你知道这个数列吗？,2020/7/28,递推法例：,已知某数列为1,1,2,3,5,8,13,.,求第n项的值。,循环,循环体,如果输出前n项的值呢？,2020/7/28,5.2 算法与算法设计,例2：,求n！；设n=10。,(1) 首先 f(0)=0!=1； (2) f(1)=1!=1*0!=1; (3) f(2)=2!=2*1!=2; (4) f(

18、3)=3!=3*2!=6 (3) 依此递推下去可知 f(n)=n!=n*(n-1)!=n*f(n-1) 。,递推法的关键是找到进行递推的通项公式,然后求解。,2020/7/28,5.2 算法与算法设计,递归法也是利用递推公式，它的特点是: 由繁到简，用简单的问题和已进行的操作运算解决复杂问题。,递归法：,上例2：,用递归求n！,f(1)=1； f(n)=f(n-1)n; 将后一个式子从n到n-1、再到n-2逐步递推化简得到：f(n)= f(n-1)n= f(n-2) (n-1)n; = f(1)*2*3*n (n1),每一次化简,自变量减一,但多乘一个因子,在化简的每一步, f(n-1),f(n-2),仍为未知量,直到化简到f(1),因f(1)是已知的可由最后一个式子得到结果。.,2020/7/28,递归法例：,用递归法求n！ 。,调用f(n)函数,求n!,求n!的递归函数f(n),2020/7/28,5.2 算法与算法设计,递推是从已知的初始条件出发，逐次递推出最后所求的值。一个递推算法总可以转换为一个递归算法。 一般递推法用循环结构实现。 而递