第三版c语言ppt课件讲解第02章程序的灵魂——算法

《第三版c语言ppt课件讲解第02章程序的灵魂——算法》由会员分享，可在线阅读，更多相关《第三版c语言ppt课件讲解第02章程序的灵魂——算法（33页珍藏版）》请在金锄头文库上搜索。

1、第二章 程序的灵魂-算法程序设计概述一个程序应包括对数据的描述和对数据处理的描述。 1对数据的描述，即数据结构。数据结构是计算机学 科的核心课程之一，有许多专门著作论述，本课程就不 再赘述。 在C语言中，系统提供的数据结构，是以数据 类型的形式出现的。程序设计概述2对数据处理的描述，即计算机算法。算法是为解决 一个问题而采取的方法和步骤，是程序的灵魂。为此，著名计算机科学家沃思（Nikiklaus Wirth ）提出一个公式：数据结构 + 算法 = 程序 实际上，一个程序除了数据结构和算法外，还必 须使用一种计算机语言，并采用结构化方法来表示。 2.1 算法的概念算法:是指解决一个具体问题的意

2、义明确的步骤的集合 。是有限的. 概括地说，算法是指解题方案的准确而完整 的描述。从程序来说，也可以说算法是一个有限条指令 的集合，这些指令确定了解决某一特定类型问题的运算 序列。对于同一个问题可以有不同的解题方法和步骤， 也就是有不同的算法。算法有优劣，一般而言，应当选 择简单的、运算步骤少的，既运算快、内存开销小的算 法（算法的时空效率）。2.2、 简单算法举例n例1 求12345可先写出这样的算法：（1）先求12，得到结果2；（2）将步骤1得到的结果再乘以3，得到结果6；（3）将6再乘以4，得到24；（4）将24再乘以5，得到120。上述算法太繁琐，我们找一种通用的表示方法。S1:设变量

3、p，被乘数，p=1;s2:设变量i,代表乘数，i=2;s3:使pi,乘积放在被乘数变量p中,可表示为:pi p;s4:使i的值加1，即i+1 i;s5:如果i不大于5，返回重新执行步骤s3以及其后的s4 、s5;否则，算法结束。最后得到的p就是5!的值。n例2.求13579 11如果题目改为求13579 11。上述算法稍作改动：s1: 1-p;s2: 3-i;s3: pi-p;s4: i+2-is5: 若ii;S2: 如果gi=80,则打印ni和gi,否则不打印。S3: i+1-i;S4: 如果iS（执行迭代，S为迭代变量）；（4）N+1-N；（5）若N100，转去执行（3）以及其后的各步骤；

4、否则执行（6）；（6）打印S的值（即所求之总和）。2.3. 算法的特性1、有穷性：一个算法应当包含有限的步骤，而不能是无限的 步骤；同时一个算法应当在执行一定数量的步骤后，算法结束，不 能死循环。事实上“有穷性”往往指“在合理的范围之内”的有限步骤。如果让 计算机执行一个历时1000年才结束的算法，算法尽管有穷，但超过 了合理的限度，人们也不认为此算法是有用的。2、确定性：算法中的每一个步骤都应当是确定的，而不是含 糊的、摸棱两可的。也就是说不应当产生歧义。特别是算法用自然 语言描述时应当注意这点。例如：“将成绩优秀的同学名单打印输出”就是有歧义的。“成绩 优秀”是要求每门课程都90分以上，还

5、是平均成绩在90分以上？不 明确，有歧义，不适合描述算法步骤。3、有0个或多个输入（即可以没有输入,也可以有输入）所谓输入是指算法执行时从外界获取必要信息。（外界是 相对算法本身的，输入可以是人工键盘输入的数据，也可以是程序其它 部分传递给算法的数据）例如：不需要输入任何信息，就可以计算出5！；（0个输入）例如：如果要计算两个整数的最大公约数，则需要输入2个整数m ，n。（2个输入）4、有1个或多个输出（即算法必须得到结果）算法的输出：算法得到的结果。算法必须有结果，没有结果的 算法没有意义。（结果可以是显示在屏幕上的，也可以是将结果数据传 递给程序的其它部分） 5、有效性算法的每个步骤都应当

6、能有效执行，并能得到确定的结果。例 如：b=0，则执行a/b是不能有效执行的。2.4. 怎样表示一个算法？为了表示一个算法，可以用不同的方法。常用的 算法表示方法：自然语言，传统流程图，结构化流程图（N-S流程图），伪代码、计算机语言等。（重点：传统流程图，N-S流程图）2.4.1 用自然语言表示算法1.自然语言就是人们常用的语言，可以是汉语、英语或其他语言。用自然语言表示通俗易懂；但文字冗长，容易出现“歧义”性；而且，用自然语言描述包含 分支和循环的算法，不很方便。一般不使用自然语言描述算法自然语言描述举例例如：描述计算并输出z=y/x的流程，可以用自然语言描述如下：（1）输入x，y。（2）

7、判断x是否为0：若X=0,则输出错误信息；否则计算 y/x-z，且输出z。2.算法描述语言算法描述语言：是为了说明程序的流程而专门规定的 某种语言。它一般介于自然语言与程序设计语言之间，它具有 自然语言灵活的特点，同时又接近于程序设计语言的描述。注意：算法描述语言所描述的流程，一般不能直接作为 程序来使用，最后还需转换成用某种程序设计语言所描述的程 序。与程序设计语言的区别：前者比较自由，不象后者那样受语法的约束，只要描 述得人们能理解就行，而不必考虑计算机处理时所要遵循的规 定或其它一些细节。2.4.2 2.4.2 用流程图表示算法用流程图表示算法一、流程的描述在程序设计过程中，一般不可能在

8、一开始就用某 种程序设计语言编制计算机程序，而是先用某种简单、 直观、灵活的描述工具来描述处理问题的流程。当方案 确定以后，再将这样的流程转换成计算机程序，这种转 换往往是机械的，已经不涉及功能的重新设计或控制流 程的变化，而只需考虑程序设计语言所规定的语法要求 以及一细节问题。n流程图：用一些约定的几何图形来描述算法。用某种图 框表示某种操作，用箭头表示算法流程.n流程图（的符号及意义）美国标准化协会ANSI规定了一 些常用的流程图符号，已为世界各国程序工作者普遍采用.起止框输入输出框判断选择框处理框流程线连接点注释框n处理框：表示算法的某个处理步骤， 一般内部常常填写赋值操作。n n输入输

9、出框：表示算法请求输入输入输入输出框：表示算法请求输入输入 需要的数据或算法将某些结果输出。一需要的数据或算法将某些结果输出。一 般内部常常填写般内部常常填写“ “输入输入”,“”,“打印打印/ /显示显示 ”n n起止框：表示算法的开始和结束。起止框：表示算法的开始和结束。 一般内部只写一般内部只写“ “开始开始” ”或或“ “结束结束” ”。n n菱形框（判断框）：作用主要是对一菱形框（判断框）：作用主要是对一 个给定条件进行判断，根据给定的条件个给定条件进行判断，根据给定的条件 是否成立来决定如何执行其后的操作。是否成立来决定如何执行其后的操作。 它有一个入口，两个出口。它有一个入口，两

10、个出口。n连接点：用于将画在不同地方的流程 线连接起来。同一个编号的点是相互连 接在一起的，实际上同一编号的点是同 一个点，只是画不下才分开画。使用连 接点，还可以避免流程线的交叉或过长 ，使流程图更加清晰。n n注释框：注释框不是流程图中必须的注释框：注释框不是流程图中必须的 部分，不反映流程和操作，它只是对流部分，不反映流程和操作，它只是对流 程图中某些框的操作做必要的补充说明程图中某些框的操作做必要的补充说明 ，以帮助阅读流程图的人更好地理解流，以帮助阅读流程图的人更好地理解流 程图的作用。程图的作用。例： 求5 ！t=1t=1i=2i=2t=t*it=t*ii=i+1i=i+1i5i5

11、结束结束NY 开始开始传统流程图的优缺点传统流程图采用流程线指出各框的执行顺序，对 流程线的使用没有严格限制。因此，使用者可以不受限 制地使流程转来转去，使流程图变得毫无规律。人们对 这种流程图进行改进，规定几种基本的结构，然后由这 些基本结构按一定规律组成算法结构，整个算法结构是 由上而下地将各个基本结构顺序排列起来。这样可以在 一定程度上，提高算法的质量。2.4.3 三种基本结构和改进的流程图三种基本结构是：（1）顺序结构按指令的顺序依次执行（2）判断选择结构根据判别条件有选择地改变执行流程（3）循环结构有条件的重复地执行某个程序块(1)顺序结构程序设计n依次顺序执行程序语句执行a块执行b

12、块a块b块AB 传统流程图传统流程图N-SN-S流程图流程图(2)判别选择结构程序设计n首先判别条件,若条件满足,程序执行a块,否则,执行b块；条件成立？执行a块执行b块成立不成立满足条件否满足不满足执行a块执行b块传统流程图传统流程图N-SN-S流程图流程图(3)循环结构程序设计 循环又分“当型循环”和“直到型循环”条件成立？执行循环体成立不成立条件成立？执行循环体成立不成立直到条件满足为止执行循环中的指令当条件满足时执行循环中指令当型当型直到型直到型n举例，求1100的累加和 。int i，sum=0；while（i5打印t2.4.5 用伪代码表示算法用伪代码表示算法（常常用于算法设计）n

13、用传统流程图、N-S图表示算法，直观易懂，但绘制 比较麻烦，在设计一个算法时，可能要反复修改，而修 改流程图是比较麻烦的，因此，流程图适合表示算法， 但在设计算法过程中使用不是很理想。为了设计算法方 便，常使用伪代码工具。n伪代码是用介于自然语言和计算机语言之间的文字和 符号来描述算法。伪代码不用图形符号，书写方便，格 式紧凑，便于向计算机语言算法过渡2.4.6 用计算机语言表示算法用某种程序设计语言编写的程序本质上也是问题 处理方案的描述，并且是最终的描述。在一般的程序设计过程中，不提倡一开始就编写 程序，特别是对于大型的程序。程序是程序设计的最终 产品，需要经过每一步的细致加工才能得到，如果企图 一开始就编写出程序，往往会适得其反，达不到预想的 结果。n例2.20 求5!，用C语言表示main( ) int i,t;t=1;i=2;while(i=5) t=t*i;i=i+1;printf(“%d”,t);