C程序设计 第2章算法.doc

《C程序设计 第2章算法.doc》由会员分享，可在线阅读，更多相关《C程序设计 第2章算法.doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章 算法教学目标理解什么是算法；掌握算法的特性和算法的表示方法；掌握结构化程序设计的三种基本结构及设计方法。教学重点与难点算法的概念、算法的表示、结构化程序设计的思想、三种基本结构。学时分配2学时一个程序应包括的两个方面的内容：（1）对数据的描述：在程序中要指定数据的类型和数据的组织形式，即数据结构。（2）对操作的描述：即操作步骤，也就是算法。数据和操作的关系：数据是操作的对象，操作的目的是对数据进行加工，以得到期望的结果。著名计算机科学家沃斯提出了一个公式：数据结构+算法=程序在设计程序时，还要考虑程序设计方法和计算机语言，因此有：程序=数据结构+算法+程序设计方法+语言工具和环境以上4

2、个方面是一个程序设计人员应具备的知识，设计一个程序时要综合运用这几方面的知识。上述四个方面中，算法是灵魂，数据结构是加工对象，语言是工具，编程需要采取合适的方法。算法解决做什么和怎么做的问题。程序中的按一定顺序列出的操作语句，就是算法的体现。通过本门课，大家学会使用c语言的语法编写不太复杂的c程序。本门课程重点讲述算法的设计。2.1算法的概念做任何事情都有一定的步骤。这些步骤是按一定的顺序进行的，缺一不可，并且遵循一定的次序。广义地说，为解决一个问题所采用的方法和步骤统称为算法。解决一个问题可以有不同的方法和步骤，一般希望采用简单和步骤少的方法，所以在考虑算法时，不仅要保证算法正确，还要考虑算

3、法的质量。计算机算法可分为两个类别：数值算法和非数值算法。数值算法的目的是求数值解。非数值算法包括的面非常广泛，常见的是用于事物管理领域。2.2简单算法举例例2.1 求12345最原始的方法：步骤1：求12, 得结果2。步骤2：将第1步得到的结果再乘以3, 得结果6。步骤3：将第2步得到的结果再乘以4, 得结果24。步骤4：将第3步得到的结果再乘以5, 得120。即最后结果。算法正确，但过于繁琐，如果问题改成求123.1000，需要999步才行。改进的方法：先设两个变量p和i，p代表被乘数，i代表乘数；将每一步乘积直接放入被乘数变量p中；用循环算法求结果。步骤1：令p=1步骤2：令i=2步骤3

4、：使pi，并将乘积放入p中，表示为pi =p步骤4：使 i 的值加1，表示为 i+1= i步骤5：如果i不大于5，返回到步骤3继续向下执行；否则算法结束，p中的值即最后结果。算法简练，通用。如果改成求123.1000，只需将步骤5中对i的判断改成1000既可。如果改成135791113，算法如下：步骤1：令p=1步骤2：令i=3步骤3：使pi，并将乘积放入p中，表示为pi =p步骤4：使 i 的值加2，表示为 i+2= i步骤5：如果i不大于13，返回到步骤3继续向下执行；否则算法结束，p中的值即最后结果。例2.2 有50个学生，要求将他们之中成绩在80分以上者打印出来。用n表示学号，g表示成

5、绩，i表示序号，ni表示第i个学生的学号，gi表示该学生的成绩。算法：步骤1：令i=1步骤2：如果gi80，打印ni和gi。步骤3：i+1 =i步骤4：如果i不大于50，返回到步骤2继续向下执行；否则算法结束。例2.3 判定2000-2500年中的每一年是否是闰年，将结果输出。闰年的条件：能被4整除，但不能被100整除的年份；能被400整除的年份。用y表示年份，算法如下：步骤1：令y=2000步骤2：如果y不能被4整除，输出y不是闰年，然后转到步骤6。步骤3：若y能被4整除，但不能被100整除，输出y是闰年，然后转到步骤6。步骤4：若y能被4和100整除，又能被400整除，输出y是闰年，然后转

6、到步骤6。步骤5：输出y不是闰年。步骤6：y+1=y。步骤7：若y不大于2500，转到步骤2继续执行；否则算法结束。例2.5：对于一个大于或等于3的正整数，判断它是不是素数。素数：除了1和它本身，不能被其它的任何整数整除的数。判断一个数n是否为素数：将n作为被除数，将2到（n-1）轮流作为除数进行计算，如果都不能被整除，则n为素数。算法：步骤1：输入n的值。步骤2：i=2。步骤3：计算n/i的余数r。步骤4：如果r=0，输出n不是素数，算法结束。步骤5：i+1=i。步骤6：如果i不大于n-1，返回步骤3继续执行；否则输出n是素数，算法结束。实际上循环到n/2、甚至既可。2.3算法的特性1.有穷

7、性2.确定性3.有零个或多个输入4.有一个或多个输出5.有效性2.4算法的表示2.4.1用自然语言表示自然语言指人们日常使用的语言，如汉语、英语等。2.3节中介绍的算法是用自然语言写的。用自然语言表示算法通俗易懂，但不严谨，容易产生歧义。除非问题很简单，一般不用自然语言描述算法。2.4.2用流程图表示 图2.1 例2.1、例2.2的算法流程图流程图是用一些图框表示各种操作。用流程图表示算法直观形象，易于理解。美国国家标准化协会ANSI规定了一些常用的流程图符号。一个流程图包括以下几个部分：表示相应操作的框、带箭头的流程线、框内必要的文字说明。当算法复杂时，画流程图费时、不方便。2.4.3三种基

8、本结构和改进的流程图1.传统流程图的弊端流程线的大量使用造成阅读困难。2.三种基本结构BA1966年，Bohra和Jacopini提出。（1）顺序结构（2）选择结构 （3）循环结构 当型（While型） 直到型（Until型）3.三种基本结构的共同点（1）只有一个入口；（2）一个出口；（3）结构内每一部分都有机会被执行。（4）结构内不存在“死循环”。已经证明，用上述三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。由基本结构构成的算法属于“结构化”的算法只要符合上述的四个特点的结构，都称为基本结构。4.实例图2.18是当型循环的应用例子，图2.19是直到型循环的应用例子。2.4.4用N-

9、S流程图表示算法1973年，Nassi和Shneiderman提出，也称盒图。完全取消了流程线。全部算法写在一个矩形框内。实例：2.4.5用伪代码表示算法流程图和N-S图画起来都比较费事，在算法设计过程不宜使用。伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。书写方便，格式紧凑，易懂，便于向计算机语言过渡。实例：2.4.6用计算机语言表示只有用计算机语言描述的算法才能被计算机的编译环境识别，并被处理、执行。用计算机语言表示算法必须严格遵守所用语言的语法规则。2.5结构化程序设计方法基本思路：把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。具体操作：自顶向下、逐步细化、模块化设计、结构化编码。2.6程序设计步骤1.分析问题 2.确定解决方案3.建立数学模型4.设计算法5.用计算机语言描述算法（即写出源程序）6.上机调试源程序：经过编辑、编译、连接、运行，得到可执行的程序。7.运行程序，得到需要的结果。作业2.3，2.4（2、3、4、7），2.7