《算法和算法的描述.ppt》由会员分享,可在线阅读,更多相关《算法和算法的描述.ppt(30页珍藏版)》请在金锄头文库上搜索。
1、1.2算法和算法的描述算法和算法的描述新都一中网络中心王强新都一中网络中心王强新都一中网络中心王强新都一中网络中心王强QQ:7210904QQ:7210904要求:要求:现在在请同同学学们设计个个方案。方案。导入导入 有一个牧羊人带着有一个牧羊人带着一头羊一头羊,一只狼一只狼和和一棵大白菜一棵大白菜准备过河,他找到一只很准备过河,他找到一只很小的船,每次只能带一样东西过去,如小的船,每次只能带一样东西过去,如果狼和羊单独在一起,狼会吃羊,让羊果狼和羊单独在一起,狼会吃羊,让羊和白菜单独在一起,羊会吃白菜,牧羊和白菜单独在一起,羊会吃白菜,牧羊人应如何过河?人应如何过河? 要求:要求:现在在请同
2、同学学们设计个个方案,把方案,把3样东西安然无恙的渡西安然无恙的渡过河河导入导入导入导入往壶里加水往壶里加水加热加热水是否开水是否开停止加热停止加热否否算法的图形描述:烧开水算法的图形描述:烧开水是是导入导入导入导入欧几里得是古代最有名望的学者之一,古希腊数学及,几何学的鼻祖。公元前300年左右,他所著几何原本十三卷,是世界上最早公理化的数学著作。在几何原本中,他充分总结了前人的生产经验和研究成果,创立了著名的欧几里得几何(简称欧式几何)导入导入辗转相除法辗转相除法欧几里得算法欧几里得算法设给定的两个正整数为设给定的两个正整数为m和和n,求它们的最大求它们的最大公约数的步骤如下:公约数的步骤如
3、下:以以m除以除以n,令所得的余数为,令所得的余数为r。若若r=0,则输出结果,则输出结果n,算法结束;否则,算法结束;否则,继续步骤继续步骤.令令m=n,n=r,并返回步骤并返回步骤继续进行。继续进行。一、算法一、算法1、算法的概念 算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。一、算法一、算法设m=112,n=64,利用辗转相除法,求最大公约数。1、112除以64,余数为 482、64除以48,余数为163、48除以16,余数为 0答案:答案:112和和64的最大公约数为的最大公约数为16一、算法一、算法2、算法的特征输入(可以不要)确定性(确切的定义)有穷性(有限的步骤)输出
4、(必须有)能行性(可行性)一、算法一、算法设m=112,n=64,利用辗转相除法,求最小公倍数1、112除以64,余数为2、64除以48,余数为3、48除以16,余数为481604、(11264)/16=448答案:答案:112和和64的最小公倍数是的最小公倍数是448。二、算法的描述二、算法的描述算法描述语言有:算法描述语言有:1、自然语言、自然语言2、流程图、流程图3、伪代码、伪代码人们日常生活中使用的语言 通俗易懂,但缺乏直观性通俗易懂,但缺乏直观性不简洁,且易产生歧义不简洁,且易产生歧义 如:如:“张先生对李先生张先生对李先生说他的孩子考上了大学说他的孩子考上了大学”。请问是张先生的孩
5、请问是张先生的孩子考上大学,还是李先子考上大学,还是李先生的孩子考上大学呢?生的孩子考上大学呢?1、用自然语言描述算法、用自然语言描述算法1、用自然语言描述算法、用自然语言描述算法例题:鸡兔同笼问题一个笼子里有鸡和兔,现在只知道里面一共有35个头,94个脚,鸡和兔各有多少只?试设计一个求解的算法,并用自然语言描述出来。1、用自然语言描述算法、用自然语言描述算法1)分析问题 设所求的鸡数是x,兔数是y,已知笼子里的头数是a,脚数是b,依题意得到如下的方程组:x+y=a2x+4y=b解方程组得:x=2a-b/2 y=b/2-a1、用自然语言描述算法、用自然语言描述算法2)设计算法输入a和b的值;求
6、x=2a-b/2;求y=b/2-a;输出x和y的值;结束。2、用流程图描述算法、用流程图描述算法在程序框图中流程图是描述算法的常用工具。2、用流程图描述算法、用流程图描述算法在程序框图中流程图是描述算法的常用工具。ab?“流程图流程图” ” 的基本符号的基本符号 图形符号符号名称说明流线起始、终止框起始、终止框表示算法的开始或结束开始框:一流入线结束框:一流出线输入、输出框输入、输出框框中标明输入、输出的内容只有一流入线和一流出线处理框处理框框中标明进行什么处理只有一流入线和一流出线判定框判定框框中标明判定条件框中标明判定条件框中标明判定条件框中标明判定条件并在框外标明判定并在框外标明判定并在
7、框外标明判定并在框外标明判定后的两种结果的流后的两种结果的流后的两种结果的流后的两种结果的流向向向向一流入线两流出线(一流入线两流出线(一流入线两流出线(一流入线两流出线(和和和和F F F F)但同时只能一流出但同时只能一流出但同时只能一流出但同时只能一流出线起作用线起作用线起作用线起作用流线表示从某一框到另一框的流向连接圈表示算法流向出口或入口连接点一条流线,用于大型流程图(一张纸写不完) 鸡兔同笼流程图开始开始输入a,b的值求x=2a-b/2求y=b/2-a输出x,y的值结束结束3、用伪代码描述算法、用伪代码描述算法辗转相除法input m.nr=m mod nDo while r0 m
8、=n n=r r=m mod nLoopprint n以以m除以除以n,令所得的余数为,令所得的余数为r。若若r=0,则输出结果,则输出结果n,算法结算法结束;否则,继续步骤束;否则,继续步骤.令令m=n,n=r,并返回步骤并返回步骤继继续进行。续进行。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三种描述算法的比较三种描述算法的比较自然自然语言语言优点优点 通俗易懂通俗易懂缺点缺点 缺乏直观性、简洁性,容缺乏直观性、简洁性,容易产生歧义易产生歧义流程流
9、程图图优点优点 形象、直观、更容易理解形象、直观、更容易理解伪代伪代码码优点优点 书写自由,专业书写自由,专业流程图流程图: 伪代码:伪代码:i1:sum=0i=5sum=sum+ii=i+1yesno输出sum的值开始结束sum=0For i=1 to 5 sum=sum+iNext IPrint sum复习与巩固复习与巩固设计一个算法,求出100以内能被3整除的所有正整数,请用三种算法语言进行描述。复习与巩固复习与巩固自然语言令I=1;如果I能被3整除,则输出I;I=I+1;如果I100,则返回第步;结束复习与巩固复习与巩固流程图开始I=1I能被3整除I=I+1I100结束输出I的值是是否否是是否否复习与巩固复习与巩固伪代码1I=1For I=1 to 100If I mod 3=0 then print INext I