《算法和算法的描述》PPT课件.ppt

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/2 y=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、用伪代码描述算法,辗转相除法 input m.n r=m mod n Do while r0 m=n n=r r=m mod n Loop print 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/2,y=b/2-a,print x,y,复习与巩固,设计一个算法，求出100以内能被3整除的所有正整数，请用三种算法语言进行描述。,复习与巩固,自然语言 令I=1； 如果I能被3整除，则输出I； I=I+1; 如果I100,则返回第步； 结束,复习与巩固,流程图,开始,I=1,I能被3整除,I=I+1,I100,结束,输出I的值,是,否,是,否,复习与巩固,伪代码1 I=1 For I=1 to 100 If I mod 3=0 then print I Next I,复习与巩固,伪代码2 I=1 Do until I100 if I mod 3=0 then print I end if I=I+1 Loop,伪代码3 I=1 Do while I100 if I mod 3=0 then print I end if I=I+1 Loop,复习与巩固,伪代码4 I=1 Do if I mod 3=0 then print I