第1课算法和算法的描述

上课须知之1.课程介绍模块主要内容考核比例必修部分①信息与信息的数字化②计算机软硬件系统③计算机网络④计算机安全75/120选修部分①算法基本概念②算法的三种基本结构③基本算法：解析、枚举、排序、查找45/120（1）课程重要性（学业考）（2）课程内容及考核比例（3）本学期教学任务：算法与程序设计上课须知之2.课堂常规（1）每位同学准备一本练习本，用于：①记笔记；②书面作业（2）上课时将教材和笔记本备好（3）授课教师信箱[e-mail]用于授课教师和学生的交流，布置和上交作业星期四之前（截止星期三9月4日晚24:00）每位同学发送邮件至上述信箱，邮件的主题为：学号+姓名例如：1号同学XX（1号同学的姓名）的邮件主题应为：01XX上课须知之3.机房规则（1）上课正式铃响之前须在自己的座位上坐好（2）上课时除本学科教材和笔记本外不准携带其他科目作业等材料，一经发现即予没收（3）不得擅自使用u盘等存储设备（4）不准玩游戏，一经发现报学生发展部处理（5）自觉维护机房卫生，零食和饮料不得带入机房。（6）不得在机房打闹、跑动（7）不得故意损坏机器设备，否则照价赔偿并通报处分（8）不得擅自调换座位第一讲算法和算法的描述例1:有一个3毫升的量杯和一个5毫升的量杯，杯上没有刻度，你能想办法用它们量出1毫升的水吗？方法一：1、将3毫升的量杯装满2、将3毫升量杯中的水全部注入5毫升的量杯3、将3毫升的量杯装满4、利用3毫升量杯中的水将5毫升量杯倒满，3毫升量杯中剩余1毫升水。方法二：1、将5毫升的量杯装满2、将5毫升量杯中的水注入3毫升量杯，注满后5毫升量杯中剩余2毫升水3、将3毫升量杯倒空4、将5毫升量杯中剩余的2毫升注入3毫升量杯5、将5毫升量杯装满6、将5毫升量杯中的水注入3毫升量杯，注满后5毫升量杯中剩余4毫升水7、将3毫升量杯倒空8、将5毫升量杯中的水注入3毫升量杯，注满后5毫升量杯中剩余1毫升水为解决某一问题而设计的确定的有限的步骤就称为算法说明：算法不是唯一的，针对同一问题的算法可以有多种。2、算法的特点：①有限性②确定性③可行性④有0个或多个输入⑤有1个或多个输出1、有穷性：广义地说，“有穷性”一般指操作步骤的数量有限或能在合理的时间范围内完成全部操作。算法可以有重复执行的步骤，只要这些步骤的执行能够终止。有些算法虽然是有穷的，但它所花费的时间如果超出了合理的限度，如天气预报采用的算法若要几个月后才能计算出来，那就不能算是有效地算法。例1：判断下列算法是否符合算法的特征：①给s赋值为1②将s的值增加1③重复步骤②解答：该算法的步骤②将被重复执行无穷次，不符合算法的有穷性返回2、确定性：算法中的每个步骤必须有确切的含义，而不应当是含糊的、模棱两可的。例2：判断下列算法是否符合算法的特征①L=10②输出L/自然数解答：正整数没有具体指明是哪个数，不符合算法的确定性返回3、可行性：算法中每一个步骤都是要能够实际做到的，而且是在有限的时间内完成。例3：判断下列算法是否符合算法的特征①x=-2②计算x的平方根解答：x是负数，没有平方根，该算法不可行，不符合算法的可行性返回4、有0个或多个输入：所谓输入就是只算法在执行时要从外界获得数据，其目的是为算法建立某些初始状态。如果建立初始状态所需的数据已经包含在算法中了，那就不需要输入。如果所需的数据没有包含在算法中，则需要在运行时动态输入所需数据。例4：写出算法：计算半径为2的圆的面积解答：①R=2②S=3.14*R*R③输出面积S说明：该算法中已包含计算所需的初始数据，因此没有输入说明：该算法中计算面积所需的初始数据半径R待定，要在程序运行后从键盘输入。而算法是解决一类问题的，往往所需的初始数据不止1个，可能会有多个。通过前两个例子可以知道，算法可能有0个或多个输入。解答：①输入圆的半径R②S=3.14*R*R③输出面积S例5：写出算法：从键盘输入圆的半径，计算其面积返回5、有1个或多个输出：设计算法的目的是让计算机解决某个问题，计算机处理该问题的结果必须以人能接受的方式输出来，该算法才会是有效的。说明：算法可能有1个或多个输出。例6：求从键盘输入的任意半径的圆的面积和周长解答：①输入圆的半径R②S=3.14*R*R③C=2*3.14*R④输出面积S，周长C返回3、计算机算法的描述方法自然语言描述法流程图描述法用图形符号表示算法必须要有一组统一规定、含义确定的专用符号；用流程图表示算法就较直观、形象；计算机不能识别和执行。伪代码或程序设计语言描述法只有用计算机能理解和执行的程序设计语言把算法表示出来，输入计算机执行，计算机才能按照预定的算法去解决问题；不同类型的计算机能够识别的指令和语言不尽相同，即使对同一种计算机语言，不同类型的计算机对该语言的翻译程序也有差异。3、计算机算法的描述方法自然语言描述法用自然语言表示算法，人比较容易理解，但书写较烦琐，具有不确切性，容易引起歧义，造成误解；对较复杂的问题，用自然语言难以表达准确；计算机不能识别和执行。流程图描述法用图形符号表示算法必须要有一组统一规定、含义确定的专用符号；用流程图表示算法就较直观、形象；计算机不能识别和执行。伪代码或程序设计语言描述法只有用计算机能理解和执行的程序设计语言把算法表示出来，输入计算机执行，计算机才能按照预定的算法去解决问题；不同类型的计算机能够识别的指令和语言不尽相同，即使对同一种计算机语言，不同类型的计算机对该语言的翻译程序也有差异。输入x,求分段函数值y：y=x2x32x+1x=3TF输入x开始x3结束y=x*xy=2*x+1输出y流程图描述算法图形符号符号名称说明流线起始、终止框表示算法的开始或结束开始框：一流出线结束框：一流入线输入、输出框框中标明输入输出的内容只有一流入线和一流出线处理框框中标明进行什么处理只有一流入线和一流出线判断框框中标明判定条件并在框外标明判定后的两种结果的流向一流入线两流出线(T和F)流线表示从某一框到另一框的程序运行流向连接圈表示算法流向出口或入口连接点一条流线算法的流程图表示起止框表示一个算法的开始或结束算法的流程图表示输入、输出框框内标明输入、输出的内容算法的流程图表示处理框框内标明所进行的处理算法的流程图表示判别框框内标明条件，并在框外标明判定后的两种结果的流向。算法的流程图表示流程线表示从某一框到另一框的流向算法的流程图表示连接圈表示算法流向出口或入口连接点同一出口入口点的连接圈内，必须标以相同的符号。算法的流程图表示例7：用流程图表示：从键盘输入圆的半径，计算其面积开始输入RS=3.14*R*R结束输出S解答：①输入圆的半径R②S=3.14*R*R③输出面积S例8：用流程图表示：求从键盘输入的任意半径的圆的面积和周长开始输入RS=3.14*R*R结束输出S，CC=2*3.14*R解答：①输入圆的半径R②S=3.14*R*R③C=2*3.14*R④输出面积S，周长C回家作业：1、下列算法违背了算法的哪个特征①L=10②输出L/正整数2、下列算法违背了算法的哪个特征•a=3•b=0•输出a/b描述方法描述是否繁琐描述是否精确能否被计算机直接识别或执行理解的难易其他特点自然语言流程图程序代码3、算法三种描述方法的特点，用表格作对比回家作业：4、用流程图表示算法：求边长为a的正方形及其内切圆所夹阴影部分的面积a回家作业：