C语言程序设计基础与实训教程第12章节.pptVIP

第12章 算法和流程图 主要内容 算法的概念 简单算法举例 算法的特性 算法的表示 12.1 算法的概念 做任何事情都有一定的步骤。例如，你想从北京去天津开会，首先要去买火车票，然后按时乘地铁到北京站，登上火车，到天津后乘电车到会场，参加会议。你要买电视机，先要选好货物，然后开票，付款，拿发票，取货，乘车回家。要考大学，首先要填报名单，交报名费，拿到准考证，按时参加考试，得到录取通知书，到指定学校报到注册等。这些步骤都是按一定的顺序进行的，缺一不可，次序错了也不行。从事各种工作和活动，都必须事先想好进行的步骤，然后按步就班地进行，才能避免产生错乱。实际上，在日常生活中，由于已养成习惯，所以人们并没意识到每件事情都需要事先设计出“行动步骤”。例如吃饭、上学、打球、做作业等，事实上都是按照一定的规律进行的，只是人们不必每次都重复考虑它而已。 12.1 算法的概念 不要认为只有“计算”的问题才有算法。广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。例如，描述太极拳动作的图解，就是太极拳的算法。一首歌曲的乐谱也可以称为该歌曲的算法，因为它指定了演奏该歌曲的每一个步骤，按照它的规定就能演奏出预定的曲子。 12.1 算法的概念 对同一个问题，可以有不同的解题方法和步骤。例如，求1+2+3+…+100，有人可能先进行1+2，再加3，再加4，一直加到100，而有人采取这样的方法：100+（1+99）+（2+98）+…+（49+51）+50=100+49×100+50=5050，还可以有其他的方法。当然，方法有优劣之分。有的方法只需进行很少的步骤，而有些方法则需要较多的步骤。一般来讲，希望采用方法简单、运算步骤少的方法。因此，为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。 12.1 算法的概念 本书所关心的只限于计算机算法，即计算机能执行的算法。例如，让计算机算1×2×3×4×5，或将100个学生的成绩按高低分次序排列，这是可以做到的，而让计算机去执行“替我理发”或“煎一份牛排”，则是做不到的（至少目前如此）。 12.1 算法的概念 计算机算法可分为两大类别：数值运算算法和非数值运算算法。数值运算的目的是求数值解，例如求方程的根、求一个函数的定积分等，都属于数值运算范围。非数值运算包括的面十分广泛，最常见的是用于事务管理领域，例如图书检索、人事管理、行车调度管理等。目前，计算机在非数值运算方面的应用远远超过了在数值运算方面的应用。由于数值运算有现成的模型，可以运用数值分析方法，因此对数值运算的算法研究比较深入，算法比较成熟。对各种数值运算都有比较成熟的算法可供选用。人们常常把这些算法汇编成册（写成程序形式），或者将这些程序存放在磁盘或磁带上，供用户调用。例如，有的计算机系统提供数学程序库，使用起来十分方便。而非数值运算的种类繁多，要求各异，难以规范化，因此只对一些典型的非数值运算算法（例如排序算法）作比较深入的研究。其他的非数值运算问题，往往需要使用者参考已有的类似算法，重新设计解决特定问题的专门算法。 12.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，继续执行；否则算法结束。 本例中，变量i作为下标，用它来控制序号（第几个学生， 第几个成绩）。当i超过50时，表示已对50个学生的成绩处 理完毕，算法结束。 12.2 简单算法举例 【例】判定2000—2500年中的每一年是否为闰年，将结果输出。 闰年的条件是：① 能被4整除，但不能被100整除的年份都是闰年，如1996年，2004年是闰年；② 能被100整除，又能被400整除的年份是闰年，如1600年，2000年是闰年。不符合这两个条件的年份不是闰年。 算法可表示如下： 设y为被检测的年份，可采取以下步骤： S1：2000=y。 S2：若y不能被4整除，则输出y“不是闰年”，然后转到S6。 S3：若y能被4整除，不能被100整除，则输出y“是闰年”，然后转到S6。 S4：若y能被100整除，又能被400整除，则输出y“是闰年”，否则输出“不是闰年”，然后转到S6。 S5：输出y“不是闰年”。 12.2 简单算法举例 S6：y+1=y。 S7：当y≤2500时，转到S2继续执行，如y＞2500，算法停止。 在这个算法中采取了多次判断。先判断y能否被4整除，如不能，则y必 然不是闰年。如y能被4整除，并不能马上决定它是否闰年，还要看它能 否被100整除。如果