第4章 算法及结构化程序设计优秀课件.ppt

《第4章 算法及结构化程序设计优秀课件.ppt》由会员分享，可在线阅读，更多相关《第4章 算法及结构化程序设计优秀课件.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第4章章 算法及结构化算法及结构化程序设计程序设计第1页，本讲稿共36页教学目标教学目标o算法的概念算法的概念o怎么样表示一个算法怎么样表示一个算法o结构化程序设计方法的基本思想结构化程序设计方法的基本思想第2页，本讲稿共36页学习要求学习要求掌握：掌握：n会用传统流程图表示算法会用传统流程图表示算法n熟练用熟练用N-S流程图表示算法流程图表示算法n结构化程序设计方法的基本思想结构化程序设计方法的基本思想第3页，本讲稿共36页本章授课内容本章授课内容o4.1 算法的概念算法的概念o4.2 算法的特性算法的特性o4.3 算法的表示算法的表示o4.4 结构化程序设计方法结构化程序设计方法第4页，

2、本讲稿共36页生活中的算法生活中的算法o问题：烤蛋糕问题：烤蛋糕o算法：算法：1.start2.将烤箱预热将烤箱预热3.准备一个盘子准备一个盘子4.在盘子上抹上一些黄油在盘子上抹上一些黄油5.将面粉、鸡蛋、糖和香精混合在搅拌将面粉、鸡蛋、糖和香精混合在搅拌6.将搅拌好的面粉团放在盘子上将搅拌好的面粉团放在盘子上7.将盘子放到烤箱内将盘子放到烤箱内8.end第5页，本讲稿共36页算法中的算法中的“分之策略分之策略”1.Start2.准备早餐准备早餐3.结束结束第6页，本讲稿共36页算法中的算法中的“分之策略分之策略”1.Start2.准备早餐准备早餐2.1 准备一个金枪鱼三明治准备一个金枪鱼三明

3、治2.2 准备一些薯条准备一些薯条2.3 冲一杯咖啡冲一杯咖啡3.结束结束第7页，本讲稿共36页算法中的算法中的“分之策略分之策略”1.Start2.准备早餐准备早餐2.1 准备一个金枪鱼三明治准备一个金枪鱼三明治 2.1.1 拿来两片面包拿来两片面包 2.1.2 准备一些金枪鱼浆准备一些金枪鱼浆2.2 准备一些薯条准备一些薯条2.3 冲一杯咖啡冲一杯咖啡3.结束结束第8页，本讲稿共36页算法中的算法中的“分之策略分之策略”1.Start2.准备早餐准备早餐2.1 准备一个金枪鱼三明治准备一个金枪鱼三明治 2.1.1 拿来两片面包拿来两片面包 2.1.2 准备一些金枪鱼浆准备一些金枪鱼浆2.2

4、 准备一些薯条准备一些薯条 2.2.1 将土豆切成条将土豆切成条 2.2.2 油炸这些土豆油炸这些土豆2.3 冲一杯咖啡冲一杯咖啡3.结束结束第9页，本讲稿共36页算法中的算法中的“分之策略分之策略”1.Start2.准备早餐准备早餐2.1 准备一个金枪鱼三明治准备一个金枪鱼三明治 2.1.1 拿来两片面包拿来两片面包 2.1.2 准备一些金枪鱼浆准备一些金枪鱼浆2.2 准备一些薯条准备一些薯条 2.2.1 将土豆切成条将土豆切成条 2.2.2 油炸这些土豆油炸这些土豆2.3 冲一杯咖啡冲一杯咖啡 2.3.1 烧些开水放入杯中烧些开水放入杯中 2.3.2 在水杯中加入一些咖啡和糖在水杯中加入一

5、些咖啡和糖3.结束结束第10页，本讲稿共36页4.1 4.1 算法的基本概念算法的基本概念o所谓算法，就是指为解决特定问题而采取的有所谓算法，就是指为解决特定问题而采取的有限操作步骤。限操作步骤。程序程序=数据结构数据结构+算法算法描述问题处理描述问题处理的对象及其关的对象及其关系系描述对问题处描述对问题处理对象的处理理对象的处理规则规则第11页，本讲稿共36页算法举例算法举例l已知苹果价格和公斤数，求苹果总价格算法：已知苹果价格和公斤数，求苹果总价格算法：步骤步骤1 1：输入苹果价格和所需公斤数：输入苹果价格和所需公斤数 步骤步骤2 2：处理数据，求得苹果总价格。：处理数据，求得苹果总价格。

6、步骤步骤3 3：输出苹果总价格。：输出苹果总价格。我们把这种将问题归结为有规律的操作步骤，并且用有限我们把这种将问题归结为有规律的操作步骤，并且用有限多个步骤来表示的具体过程就称之为多个步骤来表示的具体过程就称之为算法算法。l对同一个问题，可以有不同的解题方法和步骤。对同一个问题，可以有不同的解题方法和步骤。第12页，本讲稿共36页算法举例1：例如求解两个正整数p和q的最大公约数g的欧几里德算法：步骤1：如果pym=xm=y返回myesno例例1-4求两整型数中的较小的那个数的值求两整型数中的较小的那个数的值开始调用函数min=xmin(a,b)结束主程序主程序显示结果输入两个整数a，b第21

7、页，本讲稿共36页用传统流程图描述出求用传统流程图描述出求n!的算法的算法开始读入n的值n0fac=1,i=1in输出fac的值fac=0 then 输出输出 x else 输出输出 -x第23页，本讲稿共36页oC语言的控制结构语句和自然语言结合语言的控制结构语句和自然语言结合起来描述算法起来描述算法o比画流程图省时、省力，且更容易转化比画流程图省时、省力，且更容易转化为程序为程序o不能运行不能运行3 伪代码描述法第24页，本讲稿共36页4 N-S 图表示法：图表示法：1973年年美美国国学学者者I.Nassi 和和 B.Shneiderman提出一种新的流程图形式。提出一种新的流程图形式。

8、NS流程图符号：流程图符号：顺序结构：图顺序结构：图12选择结构：图选择结构：图13循环结构：图循环结构：图14，图，图15AB P成立 不成立 A B 当P成立A 直到P成立A图12 图13 图14 图15第25页，本讲稿共36页读入n的值n0NYfac=1,i=1fac=fac*iin为止输出fac的值输出错误提示信息第26页，本讲稿共36页结构化程序设计结构化程序设计n思路：思路：结构化程序设计是以结构化程序设计是以模块化模块化设计为中心，设计为中心，将待开发的软件系统划分为将待开发的软件系统划分为若干个相互独立若干个相互独立的模块的模块，这样使完成每一个模块的工作变单，这样使完成每一个

9、模块的工作变单纯而明确，为设计一些较大的软件打下了良纯而明确，为设计一些较大的软件打下了良好的基础。好的基础。第27页，本讲稿共36页4.4 程序设计方法程序设计方法o自顶向下自顶向下 是将复杂、大的问题划分为小问题，找出问题的关键、是将复杂、大的问题划分为小问题，找出问题的关键、重点所在，然后用精确的思维定性、定量地去描述问题。重点所在，然后用精确的思维定性、定量地去描述问题。o逐步求精逐步求精 是将现实世界的问题经抽象转化为逻辑空间是将现实世界的问题经抽象转化为逻辑空间或求解空间的问题。复杂问题经抽象化处理变为相对比较或求解空间的问题。复杂问题经抽象化处理变为相对比较简单的问题。经若干步抽

10、象（精化）处理，最后到求解域简单的问题。经若干步抽象（精化）处理，最后到求解域中只是比较简单的编程问题。中只是比较简单的编程问题。第28页，本讲稿共36页4.4 结构化程序设计（结构化程序设计（SP）o北京大学王选院士北京大学王选院士n没有没有GOTO语句语句n一个入口一个出口一个入口一个出口n自顶向下、逐步求精自顶向下、逐步求精的分解的分解n主程序员组主程序员组o清华大学潭浩强教清华大学潭浩强教授授n自顶向下、逐步求精自顶向下、逐步求精n程序结构按功能划分程序结构按功能划分为模块化为模块化n模块功能单一、简单模块功能单一、简单n模块由三种基本程序结模块由三种基本程序结构组成构组成n程序由函数

11、、子程序来程序由函数、子程序来实现实现oSP方法的基本思想是：把一个复杂问题的求解过程分 阶段 进行，每个阶段处理的问题都控制在人们容易理解 和处理的范围内。第29页，本讲稿共36页4.4 结构化程序设计人事管理数据录入数据查询数据维护数据统计第30页，本讲稿共36页结构化程序的特点结构化程序的特点o每个模块内部，只能使用顺序结构、分支结构、每个模块内部，只能使用顺序结构、分支结构、循环结构三种基本形式。循环结构三种基本形式。第31页，本讲稿共36页c较大的数较大的数开始开始结束结束显示结果c输入两个整数a，b功能：求两个整数中较大的那个数的值第32页，本讲稿共36页abc=bc=ayesno

12、开始开始结束结束显示结果c输入两个整数a，b功能：求两个整数中较大的那个数的值功能：求两个整数中较大的那个数的值第33页，本讲稿共36页课堂练习课堂练习1o问题问题1：从键盘输入大写字母，用小写字母输出。：从键盘输入大写字母，用小写字母输出。o解题思路：解题思路：n分析大写字母、小写字母的关系，得到转换方法；分析大写字母、小写字母的关系，得到转换方法；n写出处理问题的步骤（算法）；写出处理问题的步骤（算法）；n根据算法，编写程序。根据算法，编写程序。第34页，本讲稿共36页流程图流程图开始输入一个大写字母c1c2c132输出一个小写字母c2结束开始定义字符变量c1，c2输入一个大写字母c1c2c132输出一个小写字母c2结束第35页，本讲稿共36页源程序参考源程序参考#include stdio.hint main()char c1,c2;printf(please input a character:);c1=getchar();c2=c1+32;printf(%cn,c2);return 0;第36页，本讲稿共36页