第4.1章 算法及结构化程序设计

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