第二章算法简介与程序基本结构

第二章算法简介与程序基本结构算法(algorithm)是对特定问题求解步骤的一种描述。=数据结构+算法++编程语言2.1算法的概念例1.

有50个学生，要求将他们之中成绩在80分以上者打印出来。用n表示学号，n1代表第一个学生学号，ni代表第i个学生学号。用g代表学生成绩，gi代表第i个学生成绩，算法可表示如下：S1：1iS2：如果gi80，则打印ni

和gi，否则不打印S3：i+1iS4:如果i50,返回S2，继续执行；否则，算法结束。2.2简单算法举例(用自然语言描述法）例2将学生百分成绩按分数段分级的程序。该算法的核心部分是对输入的每一个数进行比较判断，以确定属于的级别。若学生成绩分布是均匀的，算法描述如下：S1：1iS2:a<60

a<70

a<80

a<90

不及格中等良好优秀及格YNYNYNYN输入10000个数据，则需进行31500次比较。S3:i+1iS4:如果i10000,返回S2；否则，算法结束。转S3转S3转S3转S3转S3分数0—5960—6970—7980—8990—99比例0.050.150.40.30.10

不及格Ya<90

a<80

a<70

a<60

优秀中等及格良好YNNNYYY

学生成绩分布不是均匀的情况，算法改进如下：输入10000个数据，仅需进行22000次比较。例3：对一个大于或等于3的正整数，判断它是不是一个素数。方法：将n(其中n3)作为被除数，将2到（n-1)各个整数轮流作为除数，如果都不能被整除，则n为素数。算法表示如下：S1：输入n的值S2：2i(i作为除数）

S3:n被i除，得余数rS4:如果r等于0，表示n能被i整除，则打印n“不是素数”，算法结束；否则执行S5S5：i+1iS6:如果in-1,返回S3；否则，打印n“是素数”，算法结束。例4：求1-1/2+1/3–1/4+…+1/99–1/100。S1:

1signS2:1sumS3:2denoS4:(-1)*signsignS5:sign*(1/deno)termS6:sum+termsumS7:deno+1denoS8:若deno100返回S4；否则算法结束。2.3算法的特性1.算法(algorithm)是对特定问题求解步骤的一种描述。程序=数据结构+算法2.算法的五个特性：有穷性：一个算法必须在执行有穷步之后结束。确定性：算法的每一步必须是确切定义的。对于相同输入必须得到相同结果。有效性：算法的每一步都是能够实现的，即可操作的。输入：算法有零个或多个输入。有输出：算法执行完毕，必须有一个或若干个输出结果。2.4怎样描述算法2.4.1自然语言描述法2.4.2流程图表示常用符号有:起止框输入/输出框判断框处理框流程线开始1=>ii>50输出gi和nii+1=>ii>50结束YNN输入ni和gii+1=>igi>=80N1=>iY2.4.3程序的三种基本结构和改进的流程图（N-S结构流程图）一、顺序结构

BA(a)AB(b)先执行A操作，再执行B操作，两者是顺序执行关系。N-S结构流程图二、选择结构当P条件为真时，执行A模块，否则执行B模块。APB真假(a)P真假AB(b)三、循环结构当P条件成立时，反复执行A,直到P为假。1.当型循环结构PA假真(a)当P为真A(b)当P为真2.直到型循环结构先执行A操作，再判断P是否为假，若P为假，再执行A，直到P为真为止。AP假真(a)A直到P为真(b)1=>i输入ni和gii+1=>i直到i>501=>i

gi>=80真假输出ni和gii+1=>i直到i>50开始1=>ii>50输出gi和nii+1=>ii>50结束YNN输入ni和gii+1=>igi>=80N1=>iY2.4.5用伪代码表示算法：用介于自然语言和计算机语言之间的文字和符号来描述算法

BEGIN1=>iwhile(i50){inputni和gi

i+1=>I}

1=>iwhile(i50){if(gi>=80)printni和gi

i+1=>i}END

2.4.6用计算机语言表示算法

例4：求1-1/2+1/3–1/4+…+1/99–1/100。S1:

1signS2:1sumS3:2denoS4:(-1)*signsignS5:sign*(1/deno)termS6:sum+termsumS7:deno+1denoS8:若deno100返回S4；否则算法结束。main(){intsign=1;floatdeno=2.0,sum=1.0,term;while(deno<=100){sign=-sign;term=sign/deno;sum=sum+term;deno=deno+1;}printf(“%f”,sum);}2.4结构化程序设计方法1.自顶向下2.逐步细化3.模块化设计4.结构化编