《2019-C语言程序设计课件》由会员分享,可在线阅读,更多相关《2019-C语言程序设计课件(30页珍藏版)》请在金锄头文库上搜索。
1、2020/10/23,1,第二章 算法及算法设计简介,2.1 算法的概念 2.2 算法的设计与表达 2.3 简单的算法实例 2.4 结构化程序设计方法简介,2020/10/23,2,算法的概念,任何一个程序应包含的如下两方面的内容: (1)对数据的描述。在程序中要指定数据的类型和数据的组织形式,即数据结构(data structure). (2)对操作的描述。即操作步骤,也就是算法(algorithm)。,著名计算机科学家沃思(Nikiklaus Wirth)提出公式 数据结构算法程序,算法:是对解决某个问题的方法步骤的描述。,程序:从计算机角度来说,程序是用某种计算机能理解并执 行的计算机语
2、言描述解决问题的方法和步骤。,2020/10/23,3,实际上,一个程序除了以上两个主要要素之外,还应当采用 结构化程序设计方法进行程序设计,并且用某一种计算机语 言表示。因此,可以这样表示: 程序算法数据结构程序设计方法语言工具和环境 在这4个方面中,算法是灵魂,数据结构是加工对象,语言 是工具,编程需要采用合适的算法。算法是解决“做什么” 和“怎么做”的问题。,2020/10/23,4,1、什么叫算法? 解决一个问题而采取的方法和步骤,就称为算法。,2、算法的特性,(1) 有穷性 一个算法应包含有限的操作步骤而不是无限的。,(2) 确定性 算法中的每一个步骤都应当是确定的,而不应当是 含糊
3、的,模棱两可的。,2020/10/23,5,(3)有零个或多个输入 所谓输入是指在执行算法时需要从外界取得必要 的信息。,(4)有一个或多个输出 算法的目的是为了求解,“解”就是输出。 没有输出的算法是没有意义的。,(5)有效性 算法中的每一个步骤都应当能有效地执行,并得到 确定结果。,2020/10/23,6,算法的表示,1、用自然语言表示算法 采用汉语、英语或其它语言来描述解决问题的方法和步骤。 由于自然语言容易出现“歧义性”,且描述问题的文字冗长, 因此一般很少使用自然语言来描述算法。,2020/10/23,7,例1: 有50个学生 ,要求将他们之中成绩在80分以上者打印出来。用n表示学
4、号,n1代表第一个学生学号,ni代表第i个学生学号。用g代表学生成绩, gi 代表第i个学生成绩,算法可表示如下: S1:1i S2:读入学号ni和成绩ni S3: 如果gi 80 ,则打印 ni 和gi ,否则不打印 S4: i+1 i S5: 如果 i 50, 返回S2, 继续执行; 否则,算法结束。,2020/10/23,8,2、用流程图表示算法,(1)常用的流程图符号,2020/10/23,9,上例用流程图表示:,(1) 流程图表示算法的优点: 表示算法直观形象,比较清楚地显示出各个框之间 的逻辑关系。 简单,易于掌握。,流程图,2020/10/23,10,3、用NS图表示算法,197
5、3年美国学者I.Nassi和B.Shneiderman提出了 一种新的流程图形式。在这种流程图中,完全去掉 了带箭头的流程线。全部算法写在一个矩形框内, 在该框内还可以包含其他的从属于它的框。,这种流程图又称NS结构化流程图。,NS流程图用以下的流程图符号:,(1)顺序结构:,A,B,2020/10/23,11,(2)选择结构:,P,成立,不成立,A,B,(3)循环结构:,当p1成立,A,当型循环结构,直到p1成立,A,直到型循环结构,用以上3种NS流程图中的基本框,可以组成复杂的NS流程图,以表示算法,2020/10/23,12,上例用NS图表示:,用NS表示算法如图,2020/10/23,
6、13,4、用伪码表示算法,伪代码是用介于自然语言和计算机语言之间的文字和符号来 描述算法。它不用图形符号,因此书写方便,格式紧凑,也 比较好懂,便于向计算机语言算法(即程序)过渡。,例 有50个学生,要求将他们之中成绩在80分以上者打印出来。 用n表示学生学号,n1表示第一个学生学号,ni表示第i个学生 学号。用g表示学生成绩,gi表示第i个学生成绩。,2020/10/23,14,BEGIN(算法开始) 1=i While ii 1=i While ii END(算法结束),用伪代码表示算法如下:,2020/10/23,15,5、用计算机语言表示算法,设计算法的目的是为了实现算法。因此,不仅要
7、考 虑如何设计一个算法,也要考虑如何实现一个算法。,我们的任务是用计算机解题,也就是要用计算机实 现算法。计算机是无法识别流程图和伪代码的。只 有用计算机语言编写的程序才能被计算机执行(当 然还要经过编译成目标程序才能被计算机识别和执 行)。因此,在用流程图或伪代码描述出一个算法 后,还要将它转换成计算机语言程序。,2020/10/23,16,例: 有50个学生,要求将他们之中成绩在80分以上者打印出来。 用n表示学生学号,n1表示第一个学生学号,ni表示第i个学生 学号。用g表示学生成绩,gi表示第i个学生成绩。,C语言程序如下: main( ) int g50,n50,i; for(i=0
8、;i=80) printf(“%6d,%3dn”,ni,gi); ,2020/10/23,17,例2:对一个大于或等于3的正整数,判断它是不是一个素数。,方法:将 n (其中n 3) 作为被除数, 将2 到(n-1) 各个整数轮流作为除数,如果都不能被整除,则n为素数。,简单的算法实例,2020/10/23,18,算法表示如下: S1:输入n的值 S2:2 i ( i 作为除数) S3: n 被 i 除,得余数 r S4: 如果 r 等于 0 , 表示 n 能 被 i 整除,则打印 n “不是素数”,算法结束;否则执行S5 S5:i+1 i S6: 如果 i n-1, 返回S3;否则,打印 n
9、 “是素数”,算法结束。,2020/10/23,19,S1: 1 sign S2: 1 sum S3: 2 deno S4: (-1)*sign sign S5: sign*(1/deno) term S6: sum+term sum S7: deno+1 deno S8: 若deno 100 返回S4;否则算法结束。,例3:求 1-1/2 + 1/3 1/4 + 1/99 1/100。,2020/10/23,20,结构化程序设计方法简介,1、三种基本结构回顾,(1)顺序结构,2020/10/23,21,(2)选择结构,或称选取结构,2020/10/23,22,l(3) 循环结构,它又称为重复
10、结构,即反复执行某一部分 的操作。又两类循环结构:,(a) 当型(while型)循环结构,2020/10/23,23,(b)直到型(Until型)循环结构,2020/10/23,24,2、三种基本结构的共同特点:,(1)只有一个入口。,(2)只有一个出口。请注意,一个菱形判断框有两个出口, 而一个 选择结构只有一个出口。不要将菱形框的出口混淆。,(3)结构内的每一部分都有机会被执行到。也就是说,对每一个框来说,都有从入口到出口的路径通过它。,(4)结构内不存在“死循环”(无终止的循环)。,2020/10/23,25,3、结构化程序,所谓结构化程序,就是仅仅使用顺序、选择、循环等三种基本结构所构
11、造的程序。,4、结构化程序设计方法,结构化程序设计方法的基本思想是,把一个复杂 问题的求解过程分阶段进行。每个阶段的问题都 控制在人们容易理解和处理的范围内。,2020/10/23,26,具体的说,采用以下方法保证得到结构化的程序: (1) 自顶而下。 (2) 逐步求精。 (3) 模块化设计。 (4) 结构化编码。,2020/10/23,27,1i,i+1 =i,gi80,i50,结束,开始,打印ni,gi,Y,N,N,Y,读入ni和gi,2020/10/23,28,解答:()用自然语言表示()用传统的流程图表示()NS流程图()用伪代码表示等。,1、算法的表示形式主要有哪些?,课堂练习,2020/10/23,29,2、设计算法:A、B两人各有一桶油,现两人要将各自桶 内的油互换。,解答:必须借助另外一个空桶,并按如下算法进行: (用Si表示第i步操作,A的桶叫A,B的桶叫B,空桶叫M) 开始: S0:将A桶中的油倒入M桶中; S1:将B桶中的油倒入A桶中; S2:将M桶中的油倒入B桶中;,2020/10/23,30,3、设计算法写出求n!的算法,解答: S0:给出n的值; S1: 1=p; S2:2=i; S3: p*i=p; S4: i+1=i; S5: 若i=n,返回S3;否则,结束,