C语言――第02章 算法

1、第二章 程序的灵魂算法,2.1 算法的概念 算法即程序操作的步骤。 广义的说：算法就是为解决一个问题而采取的方法和步骤。 数据结构就是程序中指定的数据类型和数据的组织形式。 Wirth教授认为：程序数据结构算法 实际上程序还应该包括语言环境和程序设计方法。,2.2简单举例 例：对于一个大于3的正整数n，判断它是不是一个素数。(n被2,3,4n-1除，若都不能整除，则n是素数) 算法： S1: 输入n的值 S2：m2 S3：n被m除，得余数r S4: 如果r=0,表示n能被m整除，则打印“n不是素数”，算法结束;否则执行s5 S5：m=m+1 S6: 如果mn-1，返回s3；否则打印“n不是素数

2、”然后结束。,2.3算法的特性 有穷性：即有限步解决问题； 确定性:算法的每一个步骤不能含糊； 有零个或多个输入； 有一个或多个输出； 有效性；,2.4算法的表示,一些常用的流程图符号,三种基本结构,顺序结构 选择（选取、分支）结构 循环（重复）结构,注：A,B可以是一个简单语句，也可以是一个基本结构,选择（选取、分支）结构,循环（重复）结构 当（while）型循环结构 直到型（Until）循环,多分支选择结构,三种结构的特点： （1）只有一个入口和出口 （2）结构内的每一部分都有机会被 执行到。 （3）结构内不存在死循环,例：判断闰年的算法,表示算法的其他方法,用N-S流程图表示算法 (1)

3、顺序结构,(2)二分支选择结构,(3)循环结构,当型循环结构,直到型循环结构,用伪代码表示算法,例：打印20002500年中的每一年是否闰年。 BEGIN 2000 y while y=2500 if y 被4整除 if y 不被100整除 print y; “闰年” else if y 被400整除 print y; “闰年” else print y; “非闰年” else print y; “非闰年” y=y+1 END,2.5结构化程序设计方法 基本思路: 把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。 具体方法： (1)自顶向下； (2)逐

4、步细化； (3)模块化设计； (4)结构化编码。,特点：考虑周全、结构清晰、层次分明、修改容易。 过程：将问题求解由抽象逐步具体化，从顶层设计然后一步步细化。 功能：将复杂的问题分解成若干个简单的问题。,逐步细化的实现方法,把给定的模块功能转换成它的详细过程性描述，通常都采用逐步细化的策略。 例：在一组数中找出其中的最大数,1.输入一组数; 2.找出其中的最大数 3.输出最大数,2.1.任取一数,假设它就是最大数 2.2.将该数与其余各数逐一比较 2.3.若发现有任何数大于该假设的最大数,即取而代之.,1.输入一个数组 2.1 先设第一个元素为最大数 2.2 从第二个到最后一个比较. 2.3 如果新元素最大数 则将新元素最大数 3.输出,逐步细化的实现方法,逐步细化的步骤： （1）由粗到细地对程序进行逐步的细化。 （2）在细化程序的过程中，同时对数据的描述进行细化。 （3）每一步细化均使用相同的结构化语言，最后一步一般直接用伪代码来描述，以便编码时直接翻译为程序。 优点： （1）每一步只优先处理当前最需要细化的部分，其余部分则推迟到适当的时