《第4章 算法及结构化程序设计精选文档.ppt》由会员分享，可在线阅读，更多相关《第4章 算法及结构化程序设计精选文档.ppt（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第4章章 算法及结构化算法及结构化程序设计程序设计本讲稿第一页，共三十六页教学目标教学目标o算法的概念算法的概念o怎么样表示一个算法怎么样表示一个算法o结构化程序设计方法的基本思想结构化程序设计方法的基本思想本讲稿第二页，共三十六页学习要求学习要求掌握：掌握：n会用传统流程图表示算法会用传统流程图表示算法n熟练用熟练用N-S流程图表示算法流程图表示算法n结构化程序设计方法的基本思想结构化程序设计方法的基本思想本讲稿第三页，共三十六页本章授课内容本章授课内容o4.1 算法的概念算法的概念o4.2 算法的特性算法的特性o4.3 算法的表示算法的表示o4.4 结构化程序设计方法结构化程序设计方法本
2、讲稿第四页，共三十六页生活中的算法生活中的算法o问题：烤蛋糕问题：烤蛋糕o算法：算法：1.start2.将烤箱预热将烤箱预热3.准备一个盘子准备一个盘子4.在盘子上抹上一些黄油在盘子上抹上一些黄油5.将面粉、鸡蛋、糖和香精混合在搅拌将面粉、鸡蛋、糖和香精混合在搅拌6.将搅拌好的面粉团放在盘子上将搅拌好的面粉团放在盘子上7.将盘子放到烤箱内将盘子放到烤箱内8.end本讲稿第五页，共三十六页算法中的算法中的“分之策略分之策略”1.Start2.准备早餐准备早餐3.结束结束本讲稿第六页，共三十六页算法中的算法中的“分之策略分之策略”1.Start2.准备早餐准备早餐2.1 准备一个金枪鱼三明治准备一
3、个金枪鱼三明治2.2 准备一些薯条准备一些薯条2.3 冲一杯咖啡冲一杯咖啡3.结束结束本讲稿第七页，共三十六页算法中的算法中的“分之策略分之策略”1.Start2.准备早餐准备早餐2.1 准备一个金枪鱼三明治准备一个金枪鱼三明治 2.1.1 拿来两片面包拿来两片面包 2.1.2 准备一些金枪鱼浆准备一些金枪鱼浆2.2 准备一些薯条准备一些薯条2.3 冲一杯咖啡冲一杯咖啡3.结束结束本讲稿第八页，共三十六页算法中的算法中的“分之策略分之策略”1.Start2.准备早餐准备早餐2.1 准备一个金枪鱼三明治准备一个金枪鱼三明治 2.1.1 拿来两片面包拿来两片面包 2.1.2 准备一些金枪鱼浆准备一
4、些金枪鱼浆2.2 准备一些薯条准备一些薯条 2.2.1 将土豆切成条将土豆切成条 2.2.2 油炸这些土豆油炸这些土豆2.3 冲一杯咖啡冲一杯咖啡3.结束结束本讲稿第九页，共三十六页算法中的算法中的“分之策略分之策略”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.结束结束本讲稿第十页，共三十六页4.1 4.1 算法的基本概念算法的基本概念o所谓算法，就是指为解决特定问题而采取的有所谓算法，就是指为解决特定问题而采取的有限操作步骤。限操作步骤。程序程序=数据结构数据结构+算法算法描述问题处理描述问题处理的对象及其关的对象及其关系系描述对问题处描述对问题处理对象的处理理对象的处理规则规则本讲稿第十一页，共三十六页算法举例算法举例l已知苹果价格和公斤数，求苹果总价格算法：已知苹果价格和公斤数，求苹果总价格算法：步骤步骤1 1：输入苹果价格和所需公斤数：输入苹果价格和所需公斤数 步骤步骤2 2：处理数据，求得苹果总价格。：处理数
6、据，求得苹果总价格。步骤步骤3 3：输出苹果总价格。：输出苹果总价格。我们把这种将问题归结为有规律的操作步骤，并且用有限我们把这种将问题归结为有规律的操作步骤，并且用有限多个步骤来表示的具体过程就称之为多个步骤来表示的具体过程就称之为算法算法。l对同一个问题，可以有不同的解题方法和步骤。对同一个问题，可以有不同的解题方法和步骤。本讲稿第十二页，共三十六页算法举例算法举例1 1：例如求解两个正整数p和q的最大公约数g的欧几里德算法：步骤步骤1 1：如果pym=xm=y返回myesno例例1-4求两整型数中的较小的那个数的值求两整型数中的较小的那个数的值开始调用函数min=xmin(a,b)结束主
7、程序主程序显示结果输入两个整数a，b本讲稿第二十一页，共三十六页用传统流程图描述出求用传统流程图描述出求n!的算法的算法开始读入n的值n0fac=1,i=1in输出fac的值fac=0 then 输出输出 x else 输出输出 -x本讲稿第二十三页，共三十六页oC语言的控制结构语句和自然语言结合语言的控制结构语句和自然语言结合起来描述算法起来描述算法o比画流程图省时、省力，且更容易转化比画流程图省时、省力，且更容易转化为程序为程序o不能运行不能运行3 伪代码描述法伪代码描述法本讲稿第二十四页，共三十六页4 N-S 图表示法：图表示法：1973年年美美国国学学者者I.Nassi 和和 B.Sh
8、neiderman提出一种新的流程图形式。提出一种新的流程图形式。NS流程图符号：流程图符号：顺序结构：图顺序结构：图12选择结构：图选择结构：图13循环结构：图循环结构：图14，图，图15AB P成立 不成立 A B 当P成立A 直到P成立A图12 图13 图14 图15本讲稿第二十五页，共三十六页读入n的值n0NYfac=1,i=1fac=fac*iin为止输出fac的值输出错误提示信息本讲稿第二十六页，共三十六页结构化程序设计结构化程序设计n思路：思路：结构化程序设计是以结构化程序设计是以模块化模块化设计为中心，设计为中心，将待开发的软件系统划分为将待开发的软件系统划分为若干个相互独立若
9、干个相互独立的模块的模块，这样使完成每一个模块的工作变，这样使完成每一个模块的工作变单纯而明确，为设计一些较大的软件打下单纯而明确，为设计一些较大的软件打下了良好的基础。了良好的基础。本讲稿第二十七页，共三十六页4.4 程序设计方法程序设计方法o自顶向下自顶向下 是将复杂、大的问题划分为小问题，找出问题的是将复杂、大的问题划分为小问题，找出问题的关键、重点所在，然后用精确的思维定性、定量地去描述问题。关键、重点所在，然后用精确的思维定性、定量地去描述问题。o逐步求精逐步求精 是将现实世界的问题经抽象转化为逻辑空间是将现实世界的问题经抽象转化为逻辑空间或求解空间的问题。复杂问题经抽象化处理变为相
10、对比较或求解空间的问题。复杂问题经抽象化处理变为相对比较简单的问题。经若干步抽象（精化）处理，最后到求解域简单的问题。经若干步抽象（精化）处理，最后到求解域中只是比较简单的编程问题。中只是比较简单的编程问题。本讲稿第二十八页，共三十六页4.4 结构化程序设计（结构化程序设计（SP）o北京大学王选院士北京大学王选院士n没有没有GOTO语句语句n一个入口一个出口一个入口一个出口n自顶向下、逐步求精自顶向下、逐步求精的分解的分解n主程序员组主程序员组o清华大学潭浩强教清华大学潭浩强教授授n自顶向下、逐步求精自顶向下、逐步求精n程序结构按功能划分程序结构按功能划分为模块化为模块化n模块功能单一、简单模
11、块功能单一、简单n模块由三种基本程序模块由三种基本程序结构组成结构组成n程序由函数、子程序来程序由函数、子程序来实现实现oSP方法的基本思想是方法的基本思想是：把一个复杂问题的求解过程分：把一个复杂问题的求解过程分 阶段阶段 进行，每个阶段处理的问题都控制在人们容易理解进行，每个阶段处理的问题都控制在人们容易理解 和处理的范围内。和处理的范围内。本讲稿第二十九页，共三十六页4.4 结构化程序设计结构化程序设计人事管理数据录入数据查询数据维护数据统计本讲稿第三十页，共三十六页结构化程序的特点结构化程序的特点o每个模块内部，只能使用顺序结构、分支结构、循环每个模块内部，只能使用顺序结构、分支结构、
12、循环结构三种基本形式。结构三种基本形式。本讲稿第三十一页，共三十六页c较大的数较大的数开始开始结束结束显示结果c输入两个整数a，b功能：求两个整数中较大的那个数的值功能：求两个整数中较大的那个数的值本讲稿第三十二页，共三十六页abc=bc=ayesno开始开始结束结束显示结果c输入两个整数a，b功能：求两个整数中较大的那个数的值功能：求两个整数中较大的那个数的值本讲稿第三十三页，共三十六页课堂练习课堂练习1o问题问题1：从键盘输入大写字母，用小写字母输出。：从键盘输入大写字母，用小写字母输出。o解题思路：解题思路：n分析大写字母、小写字母的关系，得到转换方分析大写字母、小写字母的关系，得到转换
13、方法；法；n写出处理问题的步骤（算法）；写出处理问题的步骤（算法）；n根据算法，编写程序。根据算法，编写程序。本讲稿第三十四页，共三十六页流程图流程图开始输入一个大写字母c1c2c132输出一个小写字母c2结束开始开始定义字符变量定义字符变量c1，c2输入一个大写字母输入一个大写字母c1c2c132输出一个小写字母输出一个小写字母c2结束结束本讲稿第三十五页，共三十六页源程序参考源程序参考#include stdio.hint main()char c1,c2;printf(please input a character:);c1=getchar();c2=c1+32;printf(%cn,c2);return 0;本讲稿第三十六页，共三十六页