高级语言程序设计(c)2算法.ppt

《高级语言程序设计(c)2算法.ppt》由会员分享，可在线阅读，更多相关《高级语言程序设计(c)2算法.ppt（33页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1第二章 算法华电信息管理教研室 梁春燕E-mail:2主要内容n算法的概念n算法的特性n算法的表示方法n结构化程序设计方法n小结n作业13算法的概念n尼古拉斯沃斯（Niklaus Wirth）Algorithm+Date Structure=Programs 算法算法+数据结构数据结构=程序程序n算法(Algorithm)q对操作的描述，解决问题的方法n数据结构(Date Structure)q对数据的描述，数据的组织形式n程序(Programs)q对算法的具体实现q程序的效率不可能超过算法的限制算法是程序的灵魂4算法的概念n广义地说，为解决一个问题采取的方法和步骤。如：菜谱、乐谱n计算机算

2、法分类q数值算法n求方程的根n求函数的定积分q非数值算法n图书检索n人事管理n排序算法5算法举例n简单算法举例：q求5！q闰年的判定方法（能被4不被100整除，或者能被100和400整除的年份）q素数的判定方法nS1：输入一个正整数nnS2：i=2（作为除数）nS3：n被i除，得余数rnS4：如果r=0，则输出 n不是素数，算法结束，否则执行S5nS5：i+1赋予inS6：如果i=，返回S3，否则输出n是素数，然后结束6算法的特性n有穷性q包含有限的步骤，在合理限度内可以完成n确定性q每一步必须明确，惟一性，非歧义性n有零个或多个输入q需要从外界获取必要的信息n有一个或多个输出q需要把求解结果

3、进行输出，有意义n有效性q每一步都能有效地执行7算法的表示方法n自然语言n传统流程图n改进的流程图nN-S图（盒图）nPAD图（问题分析图）n伪代码8自然语言n优点q通俗易懂n缺点q文字冗长q易出现歧义性9传统流程图n优点：q描绘直观，容易掌握n缺点：q对流程线没有严格控制n七种基本流程图符号（P20）q求最大公约数求最大公约数S1：输入m，nS2：如果mn，则m,n交换S3：求m除以n的余数rS4：如果r不为0，则n赋给m，r赋给n，求m除以n的余数r，返回S4S5：如果r为0，则打印n，然后结束q求素数？求素数？开始开始输入输入m,nmn?m,n交换交换求求m除以除以n的余数的余数rr0打

4、印打印nn赋给赋给m，r赋给赋给n，求求m除以除以n的余数的余数r结束YYNN10改进的流程图n优点q限制箭头滥用，保证算法质量q构成结构化算法n三种基本算法结构q顺序结构q选择结构（分支结构）q循环结构（重复结构）n当型循环（While型循环）n直到型循环（Until型循环）11顺序结构ABba12选择结构ABabpYN当p为“真”当p为“假”13循环结构Aabp1YWhile型循环N当p1为“真”当p1为“假”Aabp2NUntil型循环Y当p2为“真”当p2为“假”14循环结构的比较Aabp1YWhile型循环NAabp2NUntil型循环Y 条件的判定位置不同条件的判定位置不同 条件真

5、假的走向不同条件真假的走向不同15三种基本算法结构的共同特点n只有一个入口n只有一个出口n结构内每一部分都有机会被执行到n结构内不存在“死循环”例：求素数？AabBABa16改进的流程图q用三种基本控制结构顺序组成的算法，可以解决任何复杂的问题n整体顺序组成n可相互嵌套17其他基本结构多分支选择结构多分支选择结构 A Bp G18N-S图（盒图）nI.Nassi和B.Shneiderman提出q取消流程线，不能任意转移控制q使用N-S图设计出来的程序必然是结构化程序q容易表示嵌套关系q容易确定局部和全局数据的作用域19ABC条件条件TFAB循环条件循环条件循环体循环体循环条件循环条件循环体循环

6、体条件条件Case1部分部分值值1值值2值值nCase2部分部分Casen部分部分N-S的基本符号20N-S图n用N-S图表示各种算法q闰年的判定q求素数q求最大公约数21PAD图（问题分析图）Problem Analysis Diagram n用二维树型结构表示q使用PAD符号设计出来的程序必然是结构化程序q描绘的结构非常清晰q用PAD图表现程序逻辑，易读、易懂、易记q支持自顶向下，逐步求精方法的使用22P1P2P1P2CL1L2LnP1P2PnWHILE CPUNTIL CPPAD图基本符号23伪代码（Pseudo Code）n用结构化程序设计语言的语法控制框架，在内部可以灵活使用自然语言

7、来表示各种操作q比流程图灵活易改，可以使用普通的正文编辑程序进行修改q可以作为注释直接插在源程序中，提高文档质量q缺点：不如图形工具直观24举例nBEGINinput m,nif mn exchange m and nm%n rwhile r 0 0 n m r n m%n rprint nnEND开始开始输入输入m,nmn?m,n交换交换求求m除以除以n的余数的余数rr0打印打印nn赋给赋给m，r赋给赋给n，求求m除以除以n的余数的余数结束25计算机语言n计算机语言q对算法的实现q必须严格遵循所用语言的语法规则26计算机语言 CnBEGINinput m,nif mn exchange m

8、and nm%n rwhile r 0 0 n m r n m%n rprint nnENDnmain()int m,n,r,t;scanf(“%d,%d”,&m,&n);if(mn)t=m;m=n;n=t;r=m%n;while(r!=0)m=n;n=r;r=m%n;printf(“n=%d”,n);27结构化程序设计方法n程序：q数据结构：数据的描述q算法：操作的描述q语言：具体的实现工具q程序设计方法：设计的方法28结构化程序设计方法n结构化算法q由基本结构顺序组成的算法结构n结构化程序设计方法n自顶向下n逐步细化n模块化设计n结构化编码n如：求解二次方程的根。29小结n算法是程序的灵魂

9、n算法的特性：q有穷性、确定性、有零个或多个输入、有一个或多个输出、有效性n算法的表示方法：q自然语言、传统流程图、改进的流程图、N-S图、PAD图、伪代码n结构化程序设计方法：q自顶向下、逐步细化、模块化设计、结构化编码30上机安排q时间：周四12节q地点：n教一楼101经贸1501n教一楼105会计1501、会计1502n教一楼112商务1501、信管1501n教一楼115金融1501n教一楼124经济150131上机作业1q上机作业1：熟悉C程序的运行环境和运行方法1.安装和熟悉 Turbo C/VC+6.02.输入并运行教材例题1.1和1.2，熟悉运行环境和运行方法3.编写一个程序，求两个整数m和n的最大公约数。q作业提交n作业管理系统：n经管院网站首页-网上实验室-实验报告提交n课程+教师姓名+学号32上交作业要求n作业计入平时成绩n请按时按指定方式交作业，逾期未交累计三次者取消考试资格n请独立完成作业，不准相互抄袭，一经发现，抄袭者和被抄袭者均计零分，累计三次者取消考试资格n编程作业包含程序文档和说明文档，并把这些文件压缩成一个ZIP或者RAR文件。ZIP文件按作业序号、学号、姓名、班级来命名，其中姓名、班级用中文，各项之间用下划线“_”来分割 示例：01_1178030101_郭凯敏_商务1401.zip33END