资源描述
1.2算法和算法的描述,导入,欧几里得是古代最有名望的学者之一，古希腊数学及，几何学的鼻祖。公元前300年左右，他所著几何原本十三卷，是世界上最早公理化的数学著作。在几何原本中，他充分总结了前人的生产经验和研究成果，创立了著名的欧几里得几何（简称欧式几何）,导入,辗转相除法欧几里得算法设给定的两个正整数为m和n,求它们的最大公约数的步骤如下：以m除以n，令所得的余数为r。若r=0，则输出结果n,算法结束；否则，继续步骤.令m=n,n=r,并返回步骤继续进行。,问题1：有一个牧羊人带着一头羊,一只狼和一颗大白菜准备过河,他找到一只很小的船,每次只能带一样东西过去,可是如果让狼与羊单独在一起,狼会吃羊,让羊与白菜单独在一起,羊会吃白菜，牧羊人应如何过河？要求：分组讨论，前后四个同学为一组,把你们的橡皮擦放到一块,分别写上狼、羊、白菜，你们自己是牧羊人，现在请同学们来设计一个方案,把3样东西安然无恙的带过河。我们来比一比看哪组同学最快完成。,过河的方案:第一步：人和羊过河，人返回，留下羊；第二步：人和狼过河，人和羊返回，留下狼；第三步：人和菜过河，人返回，留下菜；第四步：人和羊过河。,还有没有其它方案？还可以在第二步时，人和菜先过河，人羊返回，留下菜；第三步，带狼过河。,一、算法,1、算法的概念算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。,一、算法,设m=112,n=64，利用辗转相除法，求最大公约数。1、112除以64，余数为,48,2、64除以48，余数为,16,3、48除以16，余数为,0,答案：112和64的最大公约数为16,一、算法,2、算法的特征输入确定性有穷性输出能行性,一、算法,设m=112,n=64，利用辗转相除法，求最小公倍数1、112除以64，余数为,2、64除以48，余数为,3、48除以16，余数为,48,16,0,4、(11264)/16=448,答案：112和64的最小公倍数是448。,二、算法的描述,算法描述语言有：1、自然语言2、流程图3、伪代码,1、用自然语言描述算法,例题：鸡兔同笼问题一个笼子里有鸡和兔，现在只知道里面一共有35个头，94个脚，鸡和兔各有多少只？试设计一个求解的算法，并用自然语言描述出来。,1、用自然语言描述算法,1）分析问题设所求的鸡数是x，兔数是y，已知笼子里的头数是a,脚数是b，依题意得到如下的方程组：,解方程组得：x=2a-b/2y=b/2-a,1、用自然语言描述算法,2)设计算法输入a和b的值；求x=2a-b/2；求y=b/2-a；输出x和y的值；结束。,2、用流程图描述算法,在程序框图中流程图是描述算法的常用工具。,ab?,“流程图”的基本符号,鸡兔同笼流程图,开始,输入a,b的值,求x=2a-b/2,求y=b/2-a,输出x,y的值,结束,3、用伪代码描述算法,辗转相除法inputm.nr=mmodnDowhiler0m=nn=rr=mmodnLoopprintn,以m除以n，令所得的余数为r。若r=0，则输出结果n,算法结束；否则，继续步骤.令m=n,n=r,并返回步骤继续进行。,3、用伪代码描述算法,Inputa,b,输入a和b的值；,鸡兔同笼,求x=2a-b/2；,求y=b/2-a；,输出x和y的值；,结束。,x=2a-b/2,y=b/2-a,printx,y,复习与巩固,设计一个算法，求出100以内能被3整除的所有正整数，请用三种算法语言进行描述。,复习与巩固,自然语言令I=1；如果I能被3整除，则输出I；I=I+1;如果I100,则返回第步；结束,复习与巩固,流程图,开始,I=1,I能被3整除,I=I+1,I100,结束,输出I的值,是,否,是,否,复习与巩固,伪代码1I=1ForI=1to100IfImod3=0thenprintINextI,复习与巩固,伪代码2I=1DountilI100ifImod3=0thenprintIendifI=I+1Loop,伪代码3I=1DowhileI100ifImod3=0thenprintIendifI=I+1Loop,复习与巩固,伪代码4I=1DoifImod3=0thenprintIendifI=I+1LoopuntilI100,伪代码5I=1DoifImod3=0thenprintIendifI=I+1LoopwhileI100,
展开阅读全文