《幻灯片-c语言程序设计视频教程-徐红波-第2章》由会员分享,可在线阅读,更多相关《幻灯片-c语言程序设计视频教程-徐红波-第2章(32页珍藏版)》请在金锄头文库上搜索。
1、C程序设计,讲师:徐红波 Email:x_h_,第2章 程序的灵魂-算法,一个程序包括以下两个方面的内容: (1)对数据的描述。在程序中要指定数据的类型和数据的组织形式,即数据结构。 (2)对操作的描述。即操作步骤,也就是算法。 数据是操作的对象,操作的目的是对数据进行加工处理,以得到期望的结果。作为程序设计人员,必须认真考虑和设计数据结构和操作步骤(即算法)。著名计算机科学家沃思提出一个公式:数据结构+算法=程序。 实际上,一个程序除了以上两个主要要素之外,还应当采用结构化程序设计方法进行程序设计,并且用某一种计算机语言表示。因此,算法、数据结构、程序设计方法和语言工具4个方面是一个程序设计
2、人员所应具备的知识。,2.1 算法的概念,广义地说,为解决一个问题而采取的方法和步骤,就称为算法(algorithm)。例如,描述太极拳动作的图解,就是太极拳的算法。一首歌曲的乐谱,也可以称为该歌曲的算法,因为它指定了演奏该歌曲的每一个步骤,按照它的规定就能演奏出预定的曲子。 对同一个问题,可以有不同的解题方法和步骤。 计算机算法可分为两大类别: 数值运算算法 非数值运算算法,2.2 简单算法举例,例2.1求12345 算法1: 步骤1:先求1*2,得到结果2。 步骤2:将步骤1得到的乘积2再乘以3,得到结果6。 步骤3:将6再乘以4,得24。 步骤4:将24再乘以5,得120。,算法2: S
3、1:使p=1 S2:使i=2 S3:使p*i,乘积仍放在变量p中,可表示为p*ip S4:使i的值加1,即i+1i S5:如果i不大于5,返回重新执行步骤S3以及其后的步骤S4和S5;否则,算法结束。最后得p的值就是5!的值。,例2.2有50个学生,要求将他们之中成绩在80分以上的学号和成绩输出,ni代表第i个学生学号。gi代表第i个学生成绩,算法如下: S1:1i S2:如果gi80,则输出ni和gi;否则不输出 S3:i+1i S4:如果i50,返回S2,继续执行;否则,算法结束。,例2.3判定2000-2500年中的每一年是否是闰年,闰年的条件是:(1)能被4整除,但不能被100整除的年
4、份是闰年,如1996年、2004年;(2)能被400整除的年份是闰年,如1600年、2000年。 设y为被检测的年份。可采用以下步骤: S1:2000y S2:若y不能被4整除,则输出 “y不是闰年”。然后转到S6 S3:若y能被4整除,不能被100整除,则输出 “y是闰年”。然后转到S6 S4:若y能被400整除,输出 “y是闰年”,然后转到S6 S5:输出 “y不是闰年” S6:y+1y S7:当y2500时,转S2继续执行,否则算法停止。,例2.4求1-1/2+1/3-1/4+1/99-1/100,算法如下: S1:sign=1 S2:sum=1 S3:deno=2 S4:sign=(-
5、1)*sign S5:term=sign*(1/deno) S6:sum=sum+term S7:deno=deno+1 S8:若deno100返回S4;否则算法结束。,例2.5对一个大于或等于3的正整数,判断它是不是一个素数,判断一个数n(n3)是否素数的方法是将n作为被除数,将2到n-1各个整数先后作为除数,如果都不能被整除,则n为素数。 算法如下: S1:输入n的值 S2:i=2(i作为除数) S3:n被i除,得余数r S4:如果r=0,表示n能被i整除,则输出 “n不是素数”,算法结束;否则执行S5 S5:i+1i S6:如果in-1,返回S3;否则输出 “n是素数”,然后结束。,2.
6、3 算法的特性,(1)有穷性。一个算法应包含有限的操作步骤,而不能是无限的。 (2)确定性。算法中的每一个步骤都应当是确定的,而不应当是含糊的、模棱两可的。 (3)有零个或多个输入。所谓输入是指在执行算法时需要从外界取得必要的信息。 (4)有一个或多个输出。算法的目的是为了求解,“解”就是输出。 (5)有效性。算法中的每一个步骤都应当能有效地执行,并得到确定的结果。,2.4 怎样表示一个算法,为了表示一个算法,可以用不同的方法。 常用的方法有: 自然语言 传统流程图 N-S流程图 伪代码 PAD图等。,2.4.2 用流程图表示算法,例2.6将例2.1求5!的算法用流程图表示,例2.7将例2.2
7、的算用流程图表示。将50名学生中成绩在80分以上者的学号和成绩输出,例2.8将例2.3判定闰年的算法用流程图表示,例2.9将例2.4的算法用流程图表示。即求1-1/2+1/3-1/4+1/99-1/100,例2.10将例2.5判断素数的算法用流程图表示,2.4.3 三种基本结构,(1)顺序结构,(2)选择结构,(3)循环结构 当型循环 直到型循环,2.4.4 用N-S流程图表示算法,N-S流程图用以下的流程图符号: (1)顺序结构:A和B两个框组成一个顺序结构。,(2)选择结构:当条件p成立时执行操作A ,条件p不成立则执行操作B。,(3)循环结构: 当型循环结构下,图符表示先判断后执行,当条
8、件p成立时反复执行操作A ,直到条件p不成立为止。 直到型循环结构下,图符表示先执行后判断,当条件p不成立时反复执行A操作,直到p条件成立为止。,例2.11将例2.1的求5!算法用N-S图表示,例2.12将例2.2的算法用N-S图表示。将50名学生中成绩高于80分的学号和成绩打印出来,例2.13将例2.3判定闰年的算法用N-S图表示,例2.14将例2.4的算法用N-S图表示。 求1-1/2+1/3+1/99-1/100,例2.15将例2.5判断素数的算法用N-S流程图表示,2.4.6 用计算机语言表示算法,例2.16将例2.11表示的算法(求5!)用C语言表示 #include main()
9、int i, t; t=1; i=2; while(i=5) t=t*i; i=i+1; printf(“%d”, t); ,例2.17求例2.14表示的算法(求级数的值) 用C语言表示,#include main() int sign=1; float deno=2.0, sum=1.0, term; while(deno=100) sign=-sign; term=sign/deno; sum=sum+term; deno=deno+1; printf(“%f”, sum); ,2.5 结构化程序设计方法,自顶向下 逐步细化 模块化设计 结构化编码,习题,2.4 用传统流程图表示求解以下问题的算法 (1)有两个瓶子A和B,分别盛放醋和酱油,要求将它们互换。 (2)依次将10个数输入,要求将其中最大的数输出 (3)有3个数a、b、c,要求按大小顺序把它们输出 (4)求1+2+3+100 (5)判断一个数n能否同时被3和5整除 (6)将100-200之间的素数输出 (7)求两个数m和n的最大公约数 (8)求方程式ax2+bx+c=0的根。分别考虑:有两个不等的实根;有两个相等的实根,