第2章 程序的灵魂-算法.ppt

1、第二章 程序的灵魂-算法,1. 什么是算法,确定 数据结构,做菜,数据结构+算法=程序,数据的逻辑 结构和存储结构,对数据运 算的描述,算法 (Algorithm) - 是指为解决一个问题而采取的方法和步骤，或者说是解题步骤的精确描述。,例1：求1+2+3+100=?,1+2+3+4+5+ +100=5050,(100 +1)+(99+2) +(51+50) =101*50=5050,执行算法所需的时间。 执行算法所需的存储空间。 算法应易于理解，易于编码，易于调试，具有通用性等等。,99次加,1次加，1次乘,例2：求1*2*3*4*5=?,方法1： S1：求1*2=2； S2：步骤1的结果2

2、*3=6； S3：求6*4=24； S4：求24*5=120，输出结 果。,方法2： S1：使p=1； S2：使i=2； S3：使p*ip； S4：使i的值加1，即i+1i; S5：如果i=5,返回S3，否则输出结 果，结束。,例3：求1*3*5*7*9=?,方法2： S1：使p=1； S2：使i=3； S3：使p*ip； S4：使i的值加2，即i+2i; S5：如果i=9,返回S3，否则输出结 果，结束。,例4：判断2000-2500年中是闰年的年份。 闰年的条件 能被4整除，便不能被100整除：2004 (能被100整除)，且能被400整除：2000 算法步骤： S1: 2000y; S2

3、: 若y能被4整除，不能被100整除，则输出y; S3: 若y能被400整除，则输出y; S4: y+1y; S5: 若y=2500，转S2，否则算法停止;,例5：判断一个大于等于3的正整数是不是素数。 素数的条件 除了1和自身，不能被其它整数整除：13 算法步骤： S1: 输入n的值; S2: i=2 (i为除数) ; S3: n被i除，得余数r; S4: 如果r=0，表示n能被i整除，则打印n“不是素数”，算法结束；否则转S5； S5: i+1i; S6: 如果i=n-1,返回S3；否则打印n“是素数”，结束;,2. 算法的特性,(3) 输入：应具有 0 个或多个输入。,(4) 输出：至少

4、产生 1 个输出。,(1) 有穷性：每一条指令的执行次数必须是有限的。,(2) 确定性：每条指令的含义都必须明确，无二义性。,(5) 有效性：每条指令都能有效、正确地执行。,算法的有穷性,求1*2*3*4*5=? S1：使p=1； S2：使i=2； S3：使p*ip； S4：使i的值加1，即i+1i; S5：如果i0，返回S3，否则结束。,算法的确定性,判断n是不是素数 算法步骤： S1: 输入n的值; S2: i=2 (i为除数) ; S3: n被一个整数除，得余数r; S4: 如果r=0，表示n能被i整除，则打印n“不是素数”，算法结束；否则转S5； S5: i+1i; S6: 如果i=n

5、-1,返回S3；否则打印n“是素数”，结束;,3. 算法的描述,3.1 自然语言 3.2 流程图 3.3 N-S流程图 3.4 伪代码表示 3.5 计算机语言表示,3. 算法的描述,3.1 自然语言 求1*2*3*4*5=? S1：使p=1； S2：使i=2； S3：使p*ip； S4：使i的值加1，即i+1i; S5：如果i=5，返回S3，否则结束。,3.2 流程图,例：求1*2*3*4*5=? S1：使p=1； S2：使i=2； S3：使p*ip； S4：使i的值加1，即i+1i; S5：如果i=5，返回S3，否则结束。,三种基本结构,例：求a+b=？,顺序结构,B,A,a,b,成立,不成

6、立,选择结构,例：判断a0,循环结构,a,b,成立,不成立,当型(while)结构,a,b,成立,不成立,直到型(until)结构,当型(while)结构,直到型(until)结构,例：求1+2+3+4+5=?,3.3 N-S流程图: 1973 年由美国学者 I.Nassi, B.Shneiderman,顺序结构,选择结构,当型(while)结构,直到型(until)结构,例：求a+b=？,例：判断a0,选择结构,当型(while)结构,直到型(until)结构,例：求1+2+3+4+5=?,例1：请用N-S 图描述解决下列问题的算法,若输入 a b两个整数 然后将它们 的值互换。,输入 a,

7、 b,t = a,a = b,b = t,输出 a, b,100,200,100,200,100,例2：请用N-S 图描述解决下列问题的算法,m=c,m=b,输入 a, b, c,m=a,a b,Y,N,m c,Y,N,输出 m,若输入 a b,c 三个整 数，请输出 它们当中最 大的一个 。,例3：请用N-S 图描述解决下列问题的算法,输入 x,y=1,x 0,Y,N,输出 y,x=0,Y,N,y=-1,y=0,例4：请用N-S 图描述解决下列问题的算法,输出y为非闰年,2000y,Y,y/400的余数=0,Y,N,y+1y,判断2000-2500 年中每一年是否 是闰年，将结果 输出。,y/4的余数=0,y/100的余数!=0,N,输出y为闰年,输出y为闰年,输出y为非闰年,直到y2500,输出y为非闰年,2000y,Y,y/400的余数=0,Y,N,y+1y,y/4的余数=0,y/100的余数!=0,N,输出y为闰年,输出y为闰年,输出y为非闰年,例4：当循环结构,3.4 伪代码表示,例：求5!,BEGIN 1t 2i while i=5 t*it i+1i print t END,3.5 计算机语言表示,程序 例：求5！