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

1,第二章算法,华电信息管理教研室梁春燕E-mail:cyliang,2,主要内容,算法的概念算法的特性算法的表示方法结构化程序设计方法小结作业1,3,算法的概念,尼古拉斯沃斯（NiklausWirth）Algorithm+DateStructure=Programs算法+数据结构=程序算法(Algorithm)对操作的描述，解决问题的方法数据结构(DateStructure)对数据的描述，数据的组织形式程序(Programs)对算法的具体实现程序的效率不可能超过算法的限制,算法是程序的灵魂,4,算法的概念,广义地说，为解决一个问题采取的方法和步骤。如：菜谱、乐谱计算机算法分类数值算法求方程的根求函数的定积分非数值算法图书检索人事管理排序算法,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,算法的特性,有穷性包含有限的步骤，在合理限度内可以完成确定性每一步必须明确，惟一性，非歧义性有零个或多个输入需要从外界获取必要的信息有一个或多个输出需要把求解结果进行输出，有意义有效性每一步都能有效地执行,7,算法的表示方法,自然语言传统流程图改进的流程图N-S图（盒图）PAD图（问题分析图）伪代码,8,自然语言,优点通俗易懂缺点文字冗长易出现歧义性,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，然后结束求素数？,10,改进的流程图,优点限制箭头滥用，保证算法质量构成结构化算法三种基本算法结构顺序结构选择结构（分支结构）循环结构（重复结构）当型循环（While型循环）直到型循环（Until型循环）,11,顺序结构,A,B,b,a,12,选择结构,当p为“真”,当p为“假”,13,循环结构,A,a,b,p1,Y,While型循环,N,当p1为“真”,当p1为“假”,A,a,b,p2,N,Until型循环,Y,当p2为“真”,当p2为“假”,14,循环结构的比较,A,a,b,p1,Y,While型循环,N,A,a,b,p2,N,Until型循环,Y,条件的判定位置不同条件真假的走向不同,15,三种基本算法结构的共同特点,只有一个入口只有一个出口结构内每一部分都有机会被执行到结构内不存在“死循环”例：求素数？,16,改进的流程图,用三种基本控制结构顺序组成的算法，可以解决任何复杂的问题整体顺序组成可相互嵌套,17,其他基本结构,多分支选择结构,A,B,p,G,18,N-S图（盒图）,I.Nassi和B.Shneiderman提出取消流程线，不能任意转移控制使用N-S图设计出来的程序必然是结构化程序容易表示嵌套关系容易确定局部和全局数据的作用域,19,N-S的基本符号,20,N-S图,用N-S图表示各种算法闰年的判定求素数求最大公约数,21,PAD图（问题分析图）ProblemAnalysisDiagram,用二维树型结构表示使用PAD符号设计出来的程序必然是结构化程序描绘的结构非常清晰用PAD图表现程序逻辑，易读、易懂、易记支持自顶向下，逐步求精方法的使用,22,P1,P2,P1,P2,C,L1,L2,Ln,P1,P2,Pn,WHILEC,P,UNTILC,P,PAD图基本符号,23,伪代码（PseudoCode）,用结构化程序设计语言的语法控制框架，在内部可以灵活使用自然语言来表示各种操作比流程图灵活易改，可以使用普通的正文编辑程序进行修改可以作为注释直接插在源程序中，提高文档质量缺点：不如图形工具直观,24,举例,BEGINinputm,nifmnexchangemandnm%nrwhiler0nmrnm%nrprintnEND,25,计算机语言,计算机语言对算法的实现必须严格遵循所用语言的语法规则,26,计算机语言C,BEGINinputm,nifmnexchangemandnm%nrwhiler0nmrnm%nrprintnEND,main()intm,n,r,t;scanf(“%d,%d”,27,结构化程序设计方法,程序：数据结构：数据的描述算法：操作的描述语言：具体的实现工具程序设计方法：设计的方法,28,结构化程序设计方法,结构化算法由基本结构顺序组成的算法结构结构化程序设计方法自顶向下逐步细化模块化设计结构化编码如：求解二次方程的根。,29,小结,算法是程序的灵魂算法的特性：有穷性、确定性、有零个或多个输入、有一个或多个输出、有效性算法的表示方法：自然语言、传统流程图、改进的流程图、N-S图、PAD图、伪代码结构化程序设计方法：自顶向下、逐步细化、模块化设计、结构化编码,30,上机安排,时间：周四12节地点：教一楼101经贸1501教一楼105会计1501、会计1502教一楼112商务1501、信管1501教一楼115金融1501教一楼124经济1501,31,上机作业1,上机作业1：熟悉C程序的运行环境和运行方法安装和熟悉TurboC/VC+6.0输入并运行教材例题1.1和1.2，熟悉运行环境和运行方法编写一个程序，求两个整数m和n的最大公约数。作业提交作业管理系统：经管院网站首页-网上实验室-实验报告提交课程+教师姓名+学号,32,上交作业要求,作业计入平时成绩请按时按指定方式交作业，逾期未交累计三次者取消考试资格请独立完成作业，不准相互抄袭，一经发现，抄袭者和被抄袭者均计零分，累计三次者取消考