C程序设计 教学课件 ppt 作者 安俊秀 第3章 算法

第3章 算法的基本概念与表示方法,程序的灵魂,教学目标,算法的概念 怎么样表示一个算法 结构化程序设计方法的基本思想,学习要求,掌握： 会用传统流程图表示算法 熟练用N-S流程图表示算法 结构化程序设计方法的基本思想,本章授课内容,3.1 算法的概念 3.2 算法的特性 3.3 算法的表示 3.4 结构化程序设计方法,3.1 算法的基本概念,所谓算法，就是指为解决特定问题而采取的有限操作步骤。,程序=数据结构+算法,描述问题处理的对象及其关系,描述对问题处理对象的处理规则,算法举例1： 例如求解两个正整数p和q的最大公约数g的欧几里德算法： 步骤1：如果pq，则交换p和q。 步骤2：令r是p/q的余数。 步骤3：如果r0，则令gq，结束算法，g即 为求得的最大公约数；否则令pq，q r，转向步骤2。 我们把这种将问题归结为有规律的操作步骤，并且用有限多个步骤来表示的具体过程就称之为算法。对同一个问题，可以有不同的解题方法和步骤,3.1 算法的基本概念,3.2 算法的特征,有穷性： 算法通过有限的步骤，即能解决问题。 确定性： 算法做的每一步都是确定的，而不是含 糊的。 可行性：算法做的每一步都能有效的被执行，并 且能得到确定的结果。 输入： 执行算法必须有零个或多个输入。 输出： 至少有一个或多个输出。,3.3 算法的表示,自然语言描述法 流程图描述法 伪代码描述法 NS流程图描述法,1 自然语言描述法,自然语言描述法： 自然语言描述就是用人们日常使用的语言，如：汉语、英语或其他语言来描述算法。如例1.1就是用自然语言来描述求解最大公约数的算法。用自然语言来描述和表示算法的优点是通俗易懂，缺点是但文字过于冗长，容易出现歧义性。因此，除了简单的问题外，一般不用自然语言描述算法。,2 流程图描述法,算法常用“流程图”描述，更直观，容易阅读和理解。 流程图中基本的图形符号,例1-2的程序流程图,问题：求两个数的和。 void main() int i,j,sum; i=2; j=-3; sum=i+j; printf(“结果是：%dn”,sum); ,变量赋初值 i=2,j=-3,开始,计算sum=i+j,结束,显示结果,将例1-4的处理流程用程序流程图表示出来。,函数xmin,例1-4求两整型数中的较小的那个数的值,开始,调用函数min=xmin(a,b),结束,主程序,显示结果,输入两个整数a，b,3 伪代码描述法,伪代码（pseudo code）是用介于自然语言和计算机程序设计语言之间的文字和符号来描述算法，即用计算机程序设计语言中具有的关键字和汉字相结合的方法表示算法的操作流程。用伪代码表示算法，并无固定的、严格的语法规则，只要求把意思表达清楚，但书写的格式要写成清晰易懂的形式。可以很方便的向计算机语言过渡。 例如：“打印x的绝对值”的算法。 if x =0 then 输出 x else 输出 -x,C语言的控制结构语句和自然语言结合起来描述算法 比画流程图省时、省力，且更容易转化为程序 不能运行,3 伪代码描述法,4 N- S 图表示法：,1973年美国学者I . Nassi 和 B . Shneiderman提出一种新的流程图形式。 NS流程图符号： 顺序结构：图12 选择结构：图13 循环结构：图14，图15,3.4 程序设计方法,自顶向下 是将复杂、大的问题划分为小问题，找出问题的关键、重点所在，然后用精确的思维定性、定量地去描述问题。 逐步求精 是将现实世界的问题经抽象转化为逻辑空间或求解空间的问题。复杂问题经抽象化处理变为相对比较简单的问题。经若干步抽象（精化）处理，最后到求解域中只是比较简单的编程问题。,3.4 结构化程序设计（SP）,北京大学王选院士 没有GOTO语句 一个入口一个出口 自顶向下、逐步求精的分解 主程序员组,清华大学潭浩强教授 自顶向下、逐步求精 程序结构按功能划分为模块化 模块功能单一、简单 模块由三种基本程序结构组成 程序由函数、子程序来实现,SP方法的基本思想是：把一个复杂问题的求解过程分 阶段 进行，每个阶段处理的问题都控制在人们容易理解 和处理的范围内。,3.4 结构化程序设计,