谭浩强版C语言课件第2章

C程序设计东北大学电子信息工程第2章程序的灵魂——算法一个程序应包括以下两方面内容:(1)对数据的描述。在程序中要指定数据的类型和数据的组织形式，即数据结构(datastructure)。(2)对操作的描述。即操作步骤，也就是算法(algorithm)。著名计算机科学家沃思(NikiklausWirth)提出一个公式:数据结构+算法=程序实际上：程序=算法+数据结构+程序设计方法+语言工具和环境2.1算法的概念2.2简单算法举例2.3算法的特性2.4怎样表示一个算法2.5结构化程序设计方法2.1算法概念为解决一个问题而采取的方法和步骤，就称为“算法”。算法分类：一、数值算法：求解数值解，可运用数值分析方法二、非数值算法：范围广泛，常见的是用于事物管理领域。2.2简单算法举例例2.1求1×2×3×4×5。最原始的方法：步骤1：先求1×2，得到结果2。步骤2：将步骤1得到的乘积2再乘以3，得到结果6。步骤3：将6再乘以4，得24。步骤4：将24再乘以5，得120。这就是最后的结果。用循环算法来求结果：S1：使p=1S2：使i=2S3：使p×i，乘积仍放在变量p中，可表示为p×i=pS4：使i的值加1，即i+1=iS5：如果i不大于5，返回重新执行步骤S3以及其后的步骤S4和S5；否则，算法结束。最后得到p的值就是5!的值。如果题目改为求1×3×5×7×9×11算法只需作很少的改动即可：S1：1=pS2：3=iS3：p×i=pS4：i+2=iS5：若i≤11，返回S3；否则，结束若把S5改为如下：S5：若i＜11，返回S3。这样会有什么问题?会得到什么结果?例2.2有50个学生，要求将他们之中成绩在80分以上者打印出来。用n表示学生学号，n1代表第一个学生学号，ni代表第i个学生学号。用g代表学生成绩，gi代表第i个学生成绩，算法可表示如下。S1：1=iS2：如果gi≥80，则打印ni和gi，否则不打印S3：i+1=iS4：如果i≤50，返回S2，继续执行；否则，算法结束。本例中，变量i作为下标，用它来控制序号(第几个学生，第几个成绩)。当i超过50时，表示已对50个学生的成绩处理完毕，算法结束。例2.3判定2000—2500年中的每一年是否闰年，将结果输出。闰年的条件是：①能被4整除，但不能被100整除的年份都是闰年，如1996年，2004年是闰年；②能被100整除，又能被400整除的年份是闰年。如1600年、2000年是闰年。不符合这两个条件的年份不是闰年。算法可表示如下：设y为被检测的年份。可采取以下步骤：S1：2000=yS2：y不能被4整除，则输出y“不是闰年”。然后转到S6S3：若y能被4整除，不能被100整除，则输出y“是闰年”。然后转到S6S4：若y能被100整除，又能被400整除，输出y“是闰年”；否则输出“不是闰年”。然后转到S6S5：输出y“不是闰年”S6：y+1=yS7：当y≤2500时，转S2继续执行，如y＞2500，算法停止。在考虑算法时，应当仔细分析所需判断的条件，如何一步一步缩小被判断的范围。有的问题，判断的先后次序是无所谓的，而有的问题，判断条件的先后次序是不能任意颠倒的。例2.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.5对一个大于或等于3的正整数，判断它是不是一个素数。所谓素数，是指除了1和该数本身之外，不能被其他任何整数整除的数。例如，13是素数，因为它不能被2，3，4，…，12整除。判断一个数n(n≥3)是否素数的方法是很简单的：将n作为被除数，将2到(n-1)各个整数轮流作为除数，如果都不能被整除，则n为素数。算法可以表示如下：S1：输入n的值S2：2=i（i作为除数）S3：n被i除，得余数rS4：如果r=0，表示n能被i整除，则打印n“不是素数”，算法结束；否则执行S5S5：i+1=iS6：如果i≤n-1，返回S3；否则打印n“是素数”，然后结束。实际上n不必被2到(n-1)的整数除，只需被2到n的开方间整数除即可，甚至只需被2到n/2之间的整数除即可。例如，判断13是否素数，只需将13被2、3除即可，如都除不尽，n必为素数。S6步骤可改为：S6：如果i≤n，返回S2；否则算法结束。通过以上几个例子，可以初步了解怎样设计一个算法。2.3算法的特性1.有穷性2.确定性3.有零个或多个输入4.有一个或多个输出5.有效性设计算法，编写算法适用的对象:2.4怎样表示一个算法为了表示一个算法，可以用不同的方法。常用的有自然语言、传统流程图、结构化流程图、伪代码、PAD图等。2.4.1用自然语言表示算法2.4.2用流程图表示算法（重点）流程图是用一些图框表示各种操作，美国国家标准化协会ANSI(AmericanNationalStandardInstitute)规定了一些常用的流程图符号如下：例2.6将例2.1求5!的算法用流程图表示，流程图如下：例2.7将例2.2的算法用流程图表示。将50名学生中成绩在80分以上者的学号和成绩打印出来，见图2.8。在此算法中没有包括输入50个学生数据的部分，如果包括这个输入数据的部分，流程图如图例2.8将例2.3判定闰年的算法用流程图表示如下图2.7图2.8图2.62.4.3三种基本程序结构(1)顺序结构(2)选择结构(3)循环结构①当型(While型)循环结构②直到型(Until型)循环顺序结构选择结构循环结构已经证明，由以上三种基本结构顺序组成的算法结构，可以解决任何复杂的问题以上三种基本结构，有以下共同特点：(1)只有一个入口。(2)只有一个出口。请注意，一个菱形判断框有两个出口，而一个选择结构只有一个出口。不要将菱形框的出口和选择结构的出口混淆。(3)结构内的每一部分都有机会被执行到。对每一个框来说，都应有一条从入口到出口的路径通过它。图中没有一条从入口到出口的路径通过A框。(4)结构内不存在“死循环”(无终止的循环)。图2.21就是一个死循环。2.5结构化程序设计方法1.自顶向下2.逐步细化3.模块化设计4.结构化编码