清华大学C语言教程第2章

C语言程序设计基础教程第二章算法第一节算法的概念第二节算法的特性第三节算法的表示本章小结习题二C语言程序设计基础教程计算机科学家D.M.Knuth撰写的《THEAREOFCOMPUTERPROGRAMMING》一书中写到：“一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一个特定类型的问题的运算序列”。意思是说任何问题的解决都是由一定的方法和步骤组成的，把解决问题的这些方法和步骤称为算法。第一节算法的概念C语言程序设计基础教程算法不只存在于计算问题中，人们在做任何事情前，都会拟草一定的步骤，这些步骤也称为算法。例如从北京到西安观光，首先要买火车票，然后乘车到北京站，登上火车，到西安后乘车去旅游点观光，这些步骤是按一定的顺序进行的，缺一不可，次序也不能颠倒。对待相同问题可以有不同的解决方法，即算法。C语言程序设计基础教程例2.1求1+2+3+…+100的值。算法解决这一问题可以有以下几种方法：（1）先进行1+2操作，再加3，再加4，一直加到100，得到5050。（2）1+2+3+…+100=100+(1+99)+(2+98)+…+(49+51)+50=100+49×100+50=5050。（3）1+2+3+…+100=(1+100)×100÷2=5050。C语言程序设计基础教程当然方法有优有劣，有的方法只需要很少的步骤就能实现命题要求，有的则需要很多步骤。因而在解决问题时，不仅需要保证算法的正确性，而且要考虑算法的复杂难易程度，以选择合适的算法。C语言程序设计基础教程例2.2输入一个正数，判断它是否是素数。算法素数是指除了1和该数本身外，不能被其他任何数整除的数。判断一个数n是否为素数的方法很简单，只须将n作为被除数，除以2～n-1之间的各数，如果都不能整除，则n为素数；否则n不是素数。判断某数是否为素数可以表示如下：C语言程序设计基础教程S1：输入n的值。S2：n除以i（i∈[2,n-1]），得余数r。S3：如果r=0，则表示n不是素数，执行S5；否则执行S4。S4：执行i++，然后判断i的值是否超出范围，如果i大于n-1，则表示n是素数，执行S5；否则执行S2。S5：打印判断结果。C语言程序设计基础教程注意：n不必与2～n-1之间各数相除，只要能与2～之间的整数相除即可。例如判断29是否为素数，只要用29除以2～5（5）之间各数进行判断即可。C语言程序设计基础教程现实中问题的正确合理解决是建立在算法的基础上的。一个合法、健壮的算法，应具备以下特点：（1）有穷性。一个算法中的执行步骤必须是有限的，不能是无限的死循环。第二节算法的特性C语言程序设计基础教程注意：有穷性是指某算法在规定的合法范围内能够实现预定功能。例如，计算机按照某种算法执行某个程序需要100年，虽然这个算法是有限的，但是它超出了合理的限度，因而该算法也不符合有穷性。C语言程序设计基础教程（2）确定性。算法中每句话的含义必须是确切的、唯一的，不能产生歧义。例如，有段算法描述“一个整数除以5，求该数。”这段描述是不正确的，它既没有说明该整数除以5得多少，也没说明余数是多少，因而无法执行。（3）有效性。算法中每一步都应该能有效地运行并返回预定结果。例如，有段算法描述“求0除5的结果”，这是不正确的，因为0不能作为除数。C语言程序设计基础教程（4）有零个或多个输入。输入是指在执行算法时需要从外界取得必要的信息。例如，在例2.1中3种算法都没有从外界接收信息；在例2.2中，需要输入某个数，然后再判断它是否是素数。C语言程序设计基础教程（5）有一个或多个输出。输出是指与输入有某种特定关系的量，在一个合法的算法中至少有一个输出。例如，例2.1中输出的是求和运算的结果，例2.2中输出的是输入数据是否为素数的信息。对于初学者来说，不需要自己设计算法处理命题，只需要使用别人设计好的算法设计程序即可。例如，在排序问题中可以使用现成的算法进行排序，常见的排序法有冒泡法、选择法、二分法等。C语言程序设计基础教程确定好某个算法后，可以用不同的方法将其表示出来，常见的算法表示有自然语言表示法、流程图表示法、N-S图表示法、伪代码表示法、计算机语言表示法等。第三节算法的表示C语言程序设计基础教程一、自然语言表示法自然语言表示法是指用日常语言将算法的各步骤描述出来。在第一节中介绍的算法都是用自然语言表示的。这种算法表示法结构自由、通俗易懂，但表示的含义不太严格，需要根据上下文才能确定其含义，容易产生歧义。此外用此方法表示复杂循环的算法时，文字冗长，很不方便。C语言程序设计基础教程二、流程图表示法流程图是指用特定的图形符号、流程线及文字说明将算法描述出来。这种算法表示法形象直观、简单易懂、便于修改，深受广大程序设计者喜爱。美国国家标准协会（AmericanNationalStandardInstitute）规定了常见的流程图符号及其含义，如表2.1所示。C语言程序设计基础教程表2.1常见的流程图符号及其含义C语言程序设计基础教程例2.3将例2.1算法（1）用流程图表示，如图2.3.1所示。注意流程图中菱形框两侧的“Y”和“N”表示“是”（yes）和“否”（no），即条件判断式的结果是否正确。程序设计的目标是利用算法对问题的原始数据进行处理，从而获得期望的效果。但是要提高程序的质量，提高编程效率，使程序具有良好的可读性、可靠性和可维护性，就必须在程序设计时遵循结构化的设计思想。1966年，Bohra和Jacopini提出了结构化程序设计的3种基本结构。C语言程序设计基础教程开始s=0,输入100s=s+ii100输出s结束NY,i=i+1i=1图2.3.1例2.1算法（1）的流程图C语言程序设计基础教程1．顺序结构顺序结构表示程序中的各操作是按照它们出现的先后顺序执行的，其流程图如图2.3.2所示。其中A和B表示两个处理步骤，它们可以是一个非转移操作或多个非转移操作，也可以是空操作。整个执行过程是从入口a开始，先执行完A后，再执行B，直到出口点b结束。C语言程序设计基础教程ABab图2.3.2顺序结构C语言程序设计基础教程2．选择结构选择结构表示程序的处理出现了分支，它需要根据某一特定的条件选择其中的一条分支来执行。常见的选择结构有单选型、双选型和多选型3种，其具体流程图如图2.3.3所示。C语言程序设计基础教程图2.3.3选择结构C语言程序设计基础教程3．循环结构循环结构表示程序反复执行某个或某些操作，直到某条件为真时，才终止循环。常见的循环结构有当型循环和直到型循环两种，其具体流程图如图2.3.4所示。A条件abYNa当型循环A条件abYNb直到型循环图2.3.4循环结构C语言程序设计基础教程三、N-S图表示法由于结构化程序设计的一些基本结构在传统流程图中没有相应的表示符号，因而需要一种新的流程图表示算法。1973年，美国学者I.Nassi和B.Shneiderman在传统的流程图设计思想上，提出了一种新的流程图形式，即N-S图。C语言程序设计基础教程N-S图的基本单元是矩形框，它只有一个入口和一个出口，在该矩形框内用不同形状的线条分割，可以表示顺序结构、选择结构和循环结构。这种算法表示法从形式上排除了随意使用控制转移对程序流程的影响，限制了不良程序结构的产生。结构化程序设计的3种基本结构对应的N-S图如图2.3.5所示。C语言程序设计基础教程图2.3.53种基本结构的N-S图C语言程序设计基础教程例2.4将例2.1算法（1）用N-S图表示，如图2.3.6所示。输入i=100开始s=0当i100时s=s+is=s+1输出s结束图2.3.6例2.1算法（1）的N-S图C语言程序设计基础教程注意：N-S图是描述算法的重要图形工具之一，适合于结构化程序的表示；而对于非结构化的程序，一般很少用N-S图表示。C语言程序设计基础教程四、伪代码表示法虽然传统流程图和N-S图表示算法直观易懂，但画起来比较麻烦，且流程图的修改也比较麻烦，因此为了设计算法时方便，常用一种介于自然语言和计算机语言之间的文字和符号来描述算法。例2.5输入数n，打印出该数的绝对值。使用伪代码表示该算法。C语言程序设计基础教程算法开始输入数n如果n0打印出x否则打印出-x结束C语言程序设计基础教程注意：虽然伪代码书写格式自由，易于表达设计者的思想，而且易于修改，但是用伪代码表示算法不如流程图直观，容易出现逻辑错误。五、计算机语言表示法计算机语言表示算法（即编写计算机程序）与伪代码不同，必须严格遵循该语言的语法规则。C语言程序设计基础教程例2.6将例2.1算法（1）用计算机语言表示。程序#includestdio.hmain(){inti,n,s;s=0;printf(“n=”);scanf(“%d”,&n);for(i=1;i=100;i++)C语言程序设计基础教程s=s+i;printf(“1+2+3+…+100=%d\n”,s);}输入n=100↙输出注意：用计算机语言表示算法不能实现算法的预定功能，只有将该算法在计算机上运行后才能实现。C语言程序设计基础教程程序设计的目的不只是学习一种语言，而是学习程序设计的方法。掌握了算法就掌握了程序设计的灵魂。本章主要介绍了算法的概念，然后介绍了算法的特点，最后结合实例重点介绍了几种常见算法的表示方法。本章小结C语言程序设计基础教程一、填空题1．一个合法的算法，应该具有的特点是__________、___________、__________、__________和_________。2．结构化程序设计的3种基本结构分别为_________、_________和_________。习题二C语言程序设计基础教程二、选择题1．（）年，Bohra和Jacopini提出了结构化程序设计的3种基本结构。A．1964B．1965C．1966D．19672．（）年，美国学者I.Nassi和B.Shneiderman在传统的流程图设计思想上，提出了一种新的流程图形式，即N-S图。A．1971B．1972C．1973D．1974C语言程序设计基础教程三、上机操作题用流程图表示以下命题的算法：任意输入两个数，然后求这两个数的最小公倍数。