C语言编程：程序的灵魂--算法.pptVIP

第二章 程序的灵魂—算法 主要内容 2.1 算法的概念 2.2 简单算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法 2.1 算法的概念 一个程序应包括以下两方面内容： (1) 对数据的描述。即数据结构。 (2) 对操作的描述。即算法。 算法(algorithm)是对特定问题求解步骤的一种描述。 程序是存放在计算机中的操作指令的集合。 用程序设计语言安排好的处理问题的步骤称为计算机程序 用程序设计语言编制一个能完成某项任务的计算机程序的 过程叫做程序设计。 程序设计的关键：必须掌握一种程序设计语言。掌握程序设计的逻辑思维。 一个程序可以这样表示： 程序 = 算法 + 数据结构 + 程序设计方法 + 语言工具和环境 2.2 简单的算法举例(自然语言描述) 例2.有50个学生 ，要求将他们之中成绩在80分以上者打印出来。用n表示学号，n1代表第一个学生学号，ni代表第i个学生学号。用g代表学生成绩， gi 代表第i个学生成绩，算法可表示如下： S1：1?i S2：如果gi?80 ，则打印ni和gi，否则不打印 S3：i+1?i S4: 如果i?50,返回S2，继续执行；否则，算法结束。 2.2 简单的算法举例(自然语言描述) 例3.判定2000-2500年中的每一年是否为闰年，将结果输出。 润年的条件：1)????能被4整除，但不能被100整除的年份； 2) 能被100整除，又能被400整除的年份； 算法可表示如下：设y为被检测年份 S1：S1: 2000→y S2:若y不能被4整除，则输出y“不是闰年”，然后转到S5 S3:若y能被4整除，不能被100整除，则输出y“是闰年”，然后转到S5 S4:若y能被100整除，又能被400整除，输出y“是闰年” 否则输出y“不是闰年”，然后转到S5 S5:y+1→y S6:当y≤2500时, 返回S2继续执行，否则，结束。 2.2 简单的算法举例(续) 例4：求 1-1/2 + 1/3 –1/4 +…+ 1/99 –1/100。 S1: 1?sign S2: 1?sum S3: 2?deno S4: (-1)*sign ?sign S5: sign*(1/deno) ?term S6: sum+term?sum S7: deno+1?deno S8: 若deno?100返回S4；否则算法结束。 2.2 简单的算法举例(续) 例5：对一个大于或等于3的正整数，判断它是不是一个素数。 方法：将 n (其中n ?3) 作为被除数， 将2 到（n-1) 各个 整数轮流作为除数，如果都不能被整除，则n为素数。 算法表示如下： S1：输入n的值 S2：2?i(i作为除数） S3: n被i除，得余数r S4: 如果r=0,表示n能被i整除，则打印n“不是素数”，算法结束；否则执行S5 S5：i+1?i S6: 如果i?n-1,返回S3；否则，打印n“是素数”，算法结束。 2.3 算法的特性 算法的五个特性： 有穷性：一个算法必须在执行有穷步之后结束。 确定性：算法的每一步必须是确切定义的，不能含糊。 同一程序对于相同输入必须得到相同结果。 输 入：算法有零个或多个输入。 输 出：算法执行完毕，必须有一个或多个输出结果。 有效性：算法的每一步都是能够实现的，即可操作的。 2.4 怎样表示一个算法 2.4.1 用自然语言表示算法 2.4.2 用流程图表示算法 2.4.3 三种基本结构和改进的流程图 2.4.4 用N-S流程图表示算法 2.4.5 用伪代码表示算法 2.4.6 用计算机语言表示算法 2.4.1 用自然语言表示算法 在2.2节中介绍的算法是用自然语言表示的。 用自然语言表示的每一步骤必须是计算机能实现的，否则便是错误的算法。 用自然语言表示通俗易懂，简单易写，但内容较长，理解有异，容易出现“歧义性”，故较少使用。 2.4.2 用流程图表示算法 2.2节中例2.1的程序流程图示例: 2.2节中例2.3的程序流程图示例: 2.4.3 三种基本结构和改进的流程图2.4.4 用N-S流程图表示算法 三种基本结构及其N-S流程图表示： 一、顺序结构 2.4.3/2.4.4 (续) 二、选择结构（选取结构/分支结构） 2.4.3/2.4.4 (续) 三、 循环结构 2.4.3/2.4.4 (续) 2.直到型(Until型)循环结构 2.4.5 用伪代码表示算法 伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。2.2节中例1用伪代码表示算法如下(含数据输入部分)： BEGIN 1 =i