第一讲算法与程序设计.ppt

算法与程序设计算法与程序设计一、算法及其描述方法一、算法及其描述方法 第一节第一节 算法与程序算法与程序计计算算机机系系统统硬件系统硬件系统软件系统软件系统系统软件系统软件应用软件应用软件★★软件的重要组成部分是：程序软件的重要组成部分是：程序想一想：什么是程序？想一想：什么是程序？什么是程序什么是程序计算机的任何动作都是在执行人给它的指令指令人们针对某一需要而为计算机编制的指令序列称为程序程序 程序程序指示计算机如何去解决问题或完成任务的一组可执行的指令那么，什么是算法呢？那么，什么是算法呢？讨论：用没有刻度的用没有刻度的3毫升量杯和毫升量杯和5毫升量杯如毫升量杯如何量出何量出1毫升的水？请写出自己的解决步毫升的水？请写出自己的解决步骤参考算法二参考算法二参考算法一参考算法一n算法算法是在有限步骤内求解某一问题所使是在有限步骤内求解某一问题所使用的具有精确定义的一系列操作规则用的具有精确定义的一系列操作规则简而言之，简而言之，算法是指解决问题的具体方算法是指解决问题的具体方法和步骤法和步骤说明：算法不是唯一的，针对同一问题的算说明：算法不是唯一的，针对同一问题的算法可以有多种。

法可以有多种一个完整的算法有三个部分：输入、处理、输出一个完整的算法有三个部分：输入、处理、输出算法与程序的关系是什么呢？算法与程序的关系是什么呢？ 算法是程序的灵魂，是解决问题的步骤程序代算法是程序的灵魂，是解决问题的步骤程序代码只是实现的手段码只是实现的手段例题：例题：某学校要进行学生电脑编程竞赛，竞赛将评出某学校要进行学生电脑编程竞赛，竞赛将评出1010名获奖名获奖者，分为一、二、三等奖奖项设置一等奖获得人数要者，分为一、二、三等奖奖项设置一等奖获得人数要少于二等奖人数，二等奖人数要少于三等奖人数问一少于二等奖人数，二等奖人数要少于三等奖人数问一二三等奖人数各为多少？二三等奖人数各为多少？分析：分析：1.1.已知竞赛将评出已知竞赛将评出1010名获奖者名获奖者 2. 2.一等奖获得人数要少于二等奖人数，二等奖人一等奖获得人数要少于二等奖人数，二等奖人数要少于三等奖人数数要少于三等奖人数设计算法：设计算法：1.X+y+z=101.X+y+z=10 X

满足条件的n n组数，组数， 即结果即结果3.3.编写程序编写程序4.4.调试程序调试程序n使用电脑解决问题的一般过程使用电脑解决问题的一般过程1.分析问题分析问题2.设计算法设计算法（（设计出解决某一问题的有限个求解步骤设计出解决某一问题的有限个求解步骤 ））3.编写程序编写程序4.运行程序运行程序算法的特征1.1.有穷性有穷性：一个算法必须保证执行有限步骤之后结束一个算法必须保证执行有限步骤之后结束 2.2.确定性确定性：算法的每一步骤必须有确切的含义算法的每一步骤必须有确切的含义 3.3.可行性可行性：算法的每一步骤都能有效地执行，并得到确定：算法的每一步骤都能有效地执行，并得到确定的结果4.4.输入输入：有：有0 0个或多个输入个或多个输入5.5.输出：有输出：有1 1个或多个输出，没有输出的算法毫无意义个或多个输出，没有输出的算法毫无意义 下一页例1：判断下列算法是否符合算法的特征① s=1① s=1② ② 将将s s的值增加的值增加1 1③ ③ 重复步骤重复步骤②②解答：该算法的步骤②②将被重复执行无穷次，不符合有穷性返回例2：判断下列算法是否符合算法的特征①①L=10L=10②②输出输出L/L/自然数自然数解答：自然数没有具体指明是哪个数，不符合算法的确定性返回例3：判断下列算法是否符合算法的特征①①x= -2x= -2②②计算计算x x的平方根的平方根解答：x是负数，没有平方根，该算法不可行，不符合算法的可行性。

返回例4：写出算法：计算半径为2的圆的面积解答：解答：①①R=2R=2②②S=3.14*R*RS=3.14*R*R③③输出面积输出面积S S说明：该算法中在执行时已包含计算所需的初始数据，不必另外提供数据，因此没有输入，即有0个输入返回例5：写出算法：从键盘输入圆的半径，计算其面积解答：解答：①①输入圆的半径输入圆的半径R R②②S=3.14*R*RS=3.14*R*R③③输出面积输出面积S S说明：该算法中计算面积所需的初始数据半径R待定，需要在算法执行时从键盘输入返回请画出例6的流程图解答：解答：①①输入圆的半径输入圆的半径R R②②S=3.14*R*RS=3.14*R*R③③C=2*3.14*RC=2*3.14*R④④输出面积输出面积S S，周长，周长C C 例例6 6：求从键盘输入的：求从键盘输入的任意半径的圆的面积任意半径的圆的面积和周长和周长开始结束S=3.14*R*R输入R输出面积S、周长CC=2*3.14*R例6：求从键盘输入的任意半径的圆的面积和周长解答：解答：①①输入圆的半径输入圆的半径R R②②S=3.14*R*RS=3.14*R*R③③C=2*3.14*RC=2*3.14*R④④输出面积输出面积S S，周长，周长C C 说明：通过前两个例子可以知道，算法可能有1个或多个输出。

返回参考算法一：①①将将3 3毫升的量杯装满毫升的量杯装满②②将将3 3毫升量杯中的水注入毫升量杯中的水注入5 5毫升量杯毫升量杯③③将将3 3毫升的量杯装满毫升的量杯装满④④将将3 3毫升量杯中的水注入毫升量杯中的水注入5 5毫升量杯，注满后毫升量杯，注满后3 3毫升量杯中剩余毫升量杯中剩余1 1毫升水返回参考算法二：①①将将5毫升的量杯装满毫升的量杯装满②②将将5毫升量杯中的水注入毫升量杯中的水注入3毫升量杯，注满后毫升量杯，注满后5毫升量杯中剩余毫升量杯中剩余2毫升水毫升水③③将将3毫升量杯倒空毫升量杯倒空④④将将5毫升量杯中剩余的毫升量杯中剩余的2毫升注入毫升注入3毫升量杯毫升量杯⑤⑤将将5毫升量杯装满毫升量杯装满⑥⑥将将5毫升量杯中的水注入毫升量杯中的水注入3毫升量杯，注满后毫升量杯，注满后5毫升量杯中剩余毫升量杯中剩余4毫升水毫升水⑦⑦将将3毫升量杯倒空毫升量杯倒空⑧⑧将将5毫升量杯中的水注入毫升量杯中的水注入3毫升量杯，注满后毫升量杯，注满后5毫升量杯中剩余毫升量杯中剩余1毫升水毫升水返回二、算法的描述二、算法的描述1、用自然语言描述算法、用自然语言描述算法n例题：鸡兔同笼问题n一个笼子里有鸡和兔，现在只知道里面一共有a个头，b个脚，鸡和兔各有多少只？试设计一个求解的算法，并用自然语言描述出来。

1、用自然语言描述算法、用自然语言描述算法n1）分析问题 设所求的鸡数是x，兔数是y，已知笼子里的头数是a,脚数是b，依题意得到如下的方程组：x+y=a2x+4y=b解方程组得：x=2a-b/2 y=b/2-a1、用自然语言描述算法、用自然语言描述算法n2)设计算法①输入a和b的值；②求x=2a-b/2；③求y=b/2-a；④输出x和y的值；⑤结束鸡兔同笼流程图开始开始输入a,b的值求x=2a-b/2求y=b/2-a输出x,y的值结束结束3、用程序代码描述算法、用程序代码描述算法Input a,b①输入a和b的值；鸡兔同笼②求x=2a-b/2；③求y=b/2-a；④输出x和y的值；⑤结束x=2a-b/2y=b/2-aprint x,y算法描述语言有：算法描述语言有：n1、自然语言、自然语言n2、流程图、流程图n3、伪代码、伪代码二、算法的描述二、算法的描述算法的表示方法优缺点： １．１．自然语言自然语言　　（通过文字来描述解决问题的过程）　　（通过文字来描述解决问题的过程）　　优点：容易理解　　优点：容易理解　　缺点：书写烦琐，具有不确切性，容易引起歧义，造成误解；　　缺点：书写烦琐，具有不确切性，容易引起歧义，造成误解；对较复杂的问题，用自然语言难以表达准确；对较复杂的问题，用自然语言难以表达准确；计算机不能直接识别和执行。

计算机不能直接识别和执行２．流程图　　（用图形符号来描述算法）２．流程图　　（用图形符号来描述算法）　　必须要有一组统一规定、含义确定的　　必须要有一组统一规定、含义确定的专用符号专用符号；；　　优点：用流程图表示算法比较直观、形象；　　优点：用流程图表示算法比较直观、形象；　　缺点：计算机不能识别和执行　　缺点：计算机不能识别和执行３．程序代码　使用程序设计语言描述算法３．程序代码　使用程序设计语言描述算法下一页流程图中的符号的用途 图形符号图形符号符号名称符号名称说明说明流线流线起始、终止框起始、终止框表示算法的开始或结束表示算法的开始或结束开始框：一流出线开始框：一流出线结束框：一流入线结束框：一流入线输入、输出框输入、输出框框中标明输入输出的内容框中标明输入输出的内容只有一流入线和一只有一流入线和一流出线流出线处理框处理框框中标明进行什么处理框中标明进行什么处理只有一流入线和一只有一流入线和一流出线流出线判断框判断框框中标明判定条件并在框外标明判定框中标明判定条件并在框外标明判定后的两种结果的流向后的两种结果的流向一流入线一流入线两流出线两流出线(T和和F)流线流线表示从某一框到另一框的程序运行流表示从某一框到另一框的程序运行流向向返回例7：请画出例5的流程图解答：解答：①①输入圆的半径输入圆的半径R R②②S=3.14*R*RS=3.14*R*R③③输出面积输出面积S S例例5 5：写出算法：从：写出算法：从键盘输入圆的半径，键盘输入圆的半径，计算其面积计算其面积开始结束S=3.14*R*R输入R输出S课堂练习课堂练习1 1：：物理老师想编写一个描述小球做平抛的运动轨迹程序物理老师想编写一个描述小球做平抛的运动轨迹程序（小球运动时间限定在（（小球运动时间限定在（1-1001-100秒），你能否帮助先秒），你能否帮助先用流程图描述一下解体的方法？用流程图描述一下解体的方法？ 描课堂练习描课堂练习2 2：：描述描述S=1+2*2+3*3+……S=1+2*2+3*3+……直到呢直到呢S>10000S>10000算法算法4、分、分别别用自然用自然语语言和流程言和流程图图表示算法：求表示算法：求边边长为长为a的正方形及其内切的正方形及其内切圆圆所所夹夹阴影部分的面阴影部分的面积积a课堂练习课堂练习3：：课堂练习课堂练习1 1：：开始开始结束结束i=1,n=0i=1,n=0i<1000i<1000是是否否i=i*ii=i*iN=n+iN=n+ii=i+1i=i+1。