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