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

《清华大学C语言教程第2章.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第二章算法第一节算法的概念第二节算法的特性第三节算法的表示本章小结习题二计算机科学家D.M.Knuth撰写的《THEAREOFCOMPUTERPROGRAMMING》一书中写到：“一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一个特定类型的问题的运算序列”。意思是说任何问题的解决都是由一定的方法和步骤组成的，把解决问题的这些方法和步骤称为算法。第一节算法的概念算法不只存在于计算问题中，人们在做任何事情前，都会拟草一定的步骤，这些步骤也称为算法。例如从北京到西安观光，首先要买火车票，然后乘车到北京站，登上火车，到西安后乘车去旅游点观光，这些步骤是按一定的

2、顺序进行的，缺一不可，次序也不能颠倒。　　对待相同问题可以有不同的解决方法，即算法。例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。当然方法有优有劣，有的方法只需要很少的步骤就能实现命题要求，有的则需要很多步骤。因而在解决问题时，不仅需要保证算

3、法的正确性，而且要考虑算法的复杂难易程度，以选择合适的算法。例2.2输入一个正数，判断它是否是素数。　　算法　　素数是指除了1和该数本身外，不能被其他任何数整除的数。判断一个数n是否为素数的方法很简单，只须将n作为被除数，除以2～n-1之间的各数，如果都不能整除，则n为素数；否则n不是素数。判断某数是否为素数可以表示如下：S1：输入n的值。　　S2：n除以i（i∈[2,n-1]），得余数r。　　S3：如果r=0，则表示n不是素数，执行S5；否则执行S4。　　S4：执行i++，然后判断i的值是否超出范围，如果i大于n-1，则表示n是素数，执行S5；否则执行S

4、2。　　S5：打印判断结果。注意：n不必与2～n-1之间各数相除，只要能与2～之间的整数相除即可。例如判断29是否为素数，只要用29除以2～5（5）之间各数进行判断即可。现实中问题的正确合理解决是建立在算法的基础上的。一个合法、健壮的算法，应具备以下特点：　　（1）有穷性。一个算法中的执行步骤必须是有限的，不能是无限的死循环。第二节算法的特性注意：有穷性是指某算法在规定的合法范围内能够实现预定功能。例如，计算机按照某种算法执行某个程序需要100年，虽然这个算法是有限的，但是它超出了合理的限度，因而该算法也不符合有穷性。（2）确定性。算法中每句话的含义必须是确切的

5、、唯一的，不能产生歧义。例如，有段算法描述“一个整数除以5，求该数。”这段描述是不正确的，它既没有说明该整数除以5得多少，也没说明余数是多少，因而无法执行。　　（3）有效性。算法中每一步都应该能有效地运行并返回预定结果。例如，有段算法描述“求0除5的结果”，这是不正确的，因为0不能作为除数。（4）有零个或多个输入。输入是指在执行算法时需要从外界取得必要的信息。例如，在例2.1中3种算法都没有从外界接收信息；在例2.2中，需要输入某个数，然后再判断它是否是素数。（5）有一个或多个输出。输出是指与输入有某种特定关系的量，在一个合法的算法中至少有一个输出。例如，例2.1

6、中输出的是求和运算的结果，例2.2中输出的是输入数据是否为素数的信息。　　对于初学者来说，不需要自己设计算法处理命题，只需要使用别人设计好的算法设计程序即可。例如，在排序问题中可以使用现成的算法进行排序，常见的排序法有冒泡法、选择法、二分法等。确定好某个算法后，可以用不同的方法将其表示出来，常见的算法表示有自然语言表示法、流程图表示法、N-S图表示法、伪代码表示法、计算机语言表示法等。第三节算法的表示一、自然语言表示法自然语言表示法是指用日常语言将算法的各步骤描述出来。在第一节中介绍的算法都是用自然语言表示的。这种算法表示法结构自由、通俗易懂，但表示的含义不太严格

7、，需要根据上下文才能确定其含义，容易产生歧义。此外用此方法表示复杂循环的算法时，文字冗长，很不方便。二、流程图表示法流程图是指用特定的图形符号、流程线及文字说明将算法描述出来。这种算法表示法形象直观、简单易懂、便于修改，深受广大程序设计者喜爱。美国国家标准协会（AmericanNationalStandardInstitute）规定了常见的流程图符号及其含义，如表2.1所示。表2.1常见的流程图符号及其含义例2.3将例2.1算法（1）用流程图表示，如图2.3.1所示。　　注意流程图中菱形框两侧的“Y”和“N”表示“是”（yes）和“否”（no），即条件判断式的