《高级语言程序设计（c）2算法》由会员分享，可在线阅读，更多相关《高级语言程序设计（c）2算法（33页珍藏版）》请在金锄头文库上搜索。
1、1 1第二章 算法2 2主要内容算法的概念算法的特性算法的表示方法结构化程序设计方法小结作业13 3算法的概念尼古拉斯沃斯（Niklaus Wirth） Algorithm + Date Structure = Programs 算法算法+数据结构数据结构=程序程序算法(Algorithm)对操作的描述，解决问题的方法数据结构(Date Structure )对数据的描述，数据的组织形式程序 (Programs)对算法的具体实现程序的效率不可能超过算法的限制算法是程序的灵魂4 4算法的概念广义地说，为解决一个问题采取的方法和步骤。 如：菜谱、乐谱计算机算法分类数值算法求方程的根求函数的定积分非
2、数值算法图书检索人事管理排序算法5 5算法举例简单算法举例：求5！闰年的判定方法（能被4不被100整除，或者能被100和400整除的年份）素数的判定方法S1：输入一个正整数nS2：i=2（作为除数）S3：n被i除，得余数rS4：如果r=0，则输出 n不是素数，算法结束，否则执行S5S5：i+1赋予iS6：如果i = ，返回S3，否则输出n是素数，然后结束6 6算法的特性有穷性包含有限的步骤，在合理限度内可以完成确定性每一步必须明确，惟一性，非歧义性有零个或多个输入需要从外界获取必要的信息有一个或多个输出需要把求解结果进行输出，有意义有效性每一步都能有效地执行7 7算法的表示方法自然语言传统流程
3、图改进的流程图N-S图（盒图）PAD图（问题分析图）伪代码8 8自然语言优点通俗易懂缺点文字冗长易出现歧义性9 9传统流程图优点：描绘直观，容易掌握缺点：对流程线没有严格控制七种基本流程图符号（P20）求最大公约数求最大公约数S1： 输入m，nS2：如果mn，则m,n交换S3：求m除以n的余数rS4：如果r不为0，则n赋给m，r赋给n，求m除以n的余数r，返回S4S5：如果r为0，则打印n，然后结束求素数？求素数？开始开始输入输入m,nmn?m,n交换交换求求m除以除以n的余数的余数rr0打印打印nn赋给赋给m，r赋给赋给n，求求m除以除以n的余数的余数r结束YYNN1010改进的流程图优点限
4、制箭头滥用，保证算法质量构成结构化算法三种基本算法结构顺序结构选择结构（分支结构）循环结构（重复结构）当型循环（While型循环）直到型循环（Until型循环）1111顺序结构ABba1212选择结构ABabpYN当p为“真”当p为“假”1313循环结构Aabp1YWhile型循环N当p1为“真”当p1为“假”Aabp2NUntil型循环Y当p2为“真”当p2为“假”1414循环结构的比较Aabp1YWhile型循环NAabp2NUntil型循环Y 条件的判定位置不同条件的判定位置不同 条件真假的走向不同条件真假的走向不同1515三种基本算法结构的共同特点只有一个入口只有一个出口结构内每一部分
5、都有机会被执行到结构内不存在“死循环”例：求素数？AabBABa1616改进的流程图用三种基本控制结构顺序组成的算法，可以解决任何复杂的问题整体顺序组成可相互嵌套1717其他基本结构多分支选择结构多分支选择结构 A Bp G1818N-S图（盒图）和提出取消流程线，不能任意转移控制使用N-S图设计出来的程序必然是结构化程序容易表示嵌套关系容易确定局部和全局数据的作用域1919ABC条件条件TFAB循环条件循环条件循环体循环体循环条件循环条件循环体循环体条件条件Case1部分部分值值1值值2值值nCase2部分部分Casen部分部分N-S的基本符号2020N-S图用N-S图表示各种算法闰年的判定
6、求素数求最大公约数2121PAD图（问题分析图）Problem Analysis Diagram 用二维树型结构表示使用PAD符号设计出来的程序必然是结构化程序描绘的结构非常清晰用PAD图表现程序逻辑，易读、易懂、易记支持自顶向下，逐步求精方法的使用2222P1P2P1P2CL1L2LnP1P2PnWHILE CPUNTIL CPPAD图基本符号2323伪代码（Pseudo Code）用结构化程序设计语言的语法控制框架，在内部可以灵活使用自然语言来表示各种操作比流程图灵活易改，可以使用普通的正文编辑程序进行修改可以作为注释直接插在源程序中，提高文档质量缺点：不如图形工具直观2424举例BEGI
7、Ninput m,nif mn exchange m and nm%n rwhile r 0 0 n m r n m%n rprint nEND开始开始输入输入m,nmn?m,n交换交换求求m除以除以n的余数的余数rr0打印打印nn赋给赋给m，r赋给赋给n，求求m除以除以n的余数的余数结束2525计算机语言计算机语言对算法的实现必须严格遵循所用语言的语法规则2626计算机语言 CBEGINinput m,nif mn exchange m and nm%n rwhile r 0 0 n m r n m%n rprint nENDmain() int m,n,r,t; scanf(“%d,%d”
8、,&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); 2727结构化程序设计方法程序：数据结构：数据的描述算法：操作的描述语言：具体的实现工具程序设计方法：设计的方法2828结构化程序设计方法结构化算法由基本结构顺序组成的算法结构结构化程序设计方法自顶向下逐步细化模块化设计结构化编码如：求解二次方程的根。2929小结算法是程序的灵魂算法的特性：有穷性、确定性、有零个或多个输入、有一个或多个输出、有效性算法的表示方法：自然语言、传统流程图、改进的流程图、N-S图、PAD图、伪代码结构化程序
9、设计方法：自顶向下、逐步细化、模块化设计、结构化编码3030上机安排时间：周四12节地点：教一楼101经贸1501教一楼105会计1501、会计1502教一楼112商务1501、信管1501教一楼115金融1501教一楼124经济15013131上机作业1上机作业1： 熟悉C程序的运行环境和运行方法1.安装和熟悉 2.输入并运行教材例题和，熟悉运行环境和运行方法3.编写一个程序，求两个整数m和n的最大公约数。作业提交作业管理系统：经管院网站首页-网上实验室-实验报告提交课程+教师姓名+学号3232上交作业要求作业计入平时成绩请按时按指定方式交作业，逾期未交累计三次者取消考试资格请独立完成作业，不准相互抄袭，一经发现，抄袭者和被抄袭者均计零分，累计三次者取消考试资格编程作业包含程序文档和说明文档，并把这些文件压缩成一个ZIP或者RAR文件。ZIP文件按作业序号、学号、姓名、班级来命名，其中姓名、班级用中文，各项之间用下划线“_”来分割 示例： 01_1178030101_郭凯敏_商务3333END
