《二章算法简介及程序的基本结构.ppt》由会员分享，可在线阅读，更多相关《二章算法简介及程序的基本结构.ppt（22页珍藏版）》请在三一办公上搜索。
1、第二章 算法简介及程序的基本结构,本章要点：了解算法的基本概念掌握程序的基本结构,算法(algorithm)是对特定问题求解步骤的一种描述。程序=数据结构+算法+程序设计方法+编程语言,2.1 算法的概念,例1.有50个学生，要求将他们之中成绩在80分以上者打印出来。用n表示学号，n1代表第一个学生学号，ni代表第i个学生学号。用g代表学生成绩，gi 代表第i个学生成绩，算法可表示如下：S1：1i S2：如果gi 80，则打印 ni 和gi，否则不打印S3：i+1 i S4:如果 i 50,返回S2，继续执行；否则，算法结束。,2.2 简单算法举例(用自然语言描述法）,例2 将学生百分成绩按分
2、数段分级的程序。该算法的核心部分是对输入的每一个数进行比较判断，以确定属于的级别。若学生成绩分布是均匀的，算法描述如下：S1：1i S2:,输入10000个数据，则需进行31500次比较。,S3:i+1 iS4:如果i 10000,返回S2；否则，算法结束。,转S3,转S3,转S3,转S3,转S3,学生成绩分布不是均匀的情况，算法改进如下：,输入10000个数据，仅需进行22000次比较。,例3：对一个大于或等于3的正整数，判断它是不是一个素数。方法：将 n(其中n 3)作为被除数，将2 到（n-1)各个整数轮流作为除数，如果都不能被整除，则n为素数。算法表示如下：S1：输入n的值S2：2 i
3、(i 作为除数）S3:n 被 i 除，得余数 rS4:如果 r 等于 0，表示 n 能 被 i 整除，则打印 n“不是素数”，算法结束；否则执行S5S5：i+1 i S6:如果 i n-1,返回S3；否则，打印 n“是素数”，算法结束。,例4：求 1-1/2+1/3 1/4+1/99 1/100。S1:1 signS2:1 sumS3:2 denoS4:(-1)*sign signS5:sign*(1/deno)termS6:sum+term sumS7:deno+1 denoS8:若deno 100 返回S4；否则算法结束。,2.3 算法的特性,1.算法(algorithm)是对特定问题求解
4、步骤的一种描述。程序=数据结构+算法,2.算法的五个特性：有穷性：一个算法必须在执行有穷步之后结束。确定性：算法的每一步必须是确切定义的。对于相同输入必须得到相同结果。有效性：算法的每一步都是能够实现的，即可操作的。输 入：算法有零个或多个输入。有输出：算法执行完毕，必须有一个或若干个输出结果。,2.4 怎样描述算法2.4.1 自然语言描述法 2.4.2 流程图表示常用符号有:,2.4.3 程序的三种基本结构和改进的流程图（N-S结构流程图）,一、顺序结构,先执行A操作，再执行B操作，两者是顺序执行关系。,N-S结构流程图,二、选择结构,当P条件为真时，执行A模块，否则执行B模块。,三、循环结
5、构,当P条件成立时，反复执行A,直到P为假。,1.当型循环结构,2.直到型循环结构,先执行A操作，再判断P是否为假，若P为假，再执行A，直到P为真为止。,2.4.5 用伪代码表示算法：用介于自然语言和计算机语言之间的文字和符号来描述算法 BEGIN 1=i while(i 50)input ni和gi i+1=I 1=i while(i 50)if(gi=80)print ni和gi i+1=i END,2.4.6 用计算机语言表示算法,例4：求 1-1/2+1/3 1/4+1/99 1/100。S1:1 signS2:1 sumS3:2 denoS4:(-1)*sign signS5:sig
6、n*(1/deno)termS6:sum+term sumS7:deno+1 denoS8:若deno 100 返回S4；否则算法结束。,main()int sign=1;float deno=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.结构化编码,读输入,输入处理；return 输入；,编辑输入,编辑输入处理；return 编辑好的输入；,结果格式化,结果格式化处理；return 格式化结果；,显示结果,显示结果处理；,
