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