算法和算法的描述.ppt

1.2算法和算法的描述,新都一中网络中心王强 QQ:7210904,算法与程序设计,要求：现在请同学们设计个方案。,导入,有一个牧羊人带着一头羊，一只狼和一棵大白菜准备过河，他找到一只很小的船，每次只能带一样东西过去，如果狼和羊单独在一起，狼会吃羊，让羊和白菜单独在一起，羊会吃白菜，牧羊人应如何过河？,要求：现在请同学们设计个方案，把3样东西安然无恙的渡过河,导入,导入,往壶里加水,加热,水是否开,停止加热,否,算法的图形描述：烧开水,是,导入,导入,欧几里得是古代最有名望的学者之一，古希腊数学及，几何学的鼻祖。 公元前300年左右，他所著几何原本十三卷，是世界上最早公理化的数学著作。 在几何原本中，他充分总结了前人的生产经验和研究成果，创立了著名的欧几里得几何（简称欧式几何）,导入,辗转相除法欧几里得算法 设给定的两个正整数为m和n,求它们的最大公约数的步骤如下： 以m除以n，令所得的余数为r。 若r=0，则输出结果n,算法结束；否则，继续步骤. 令m=n,n=r,并返回步骤继续进行。,一、算法,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、用自然语言描述算法,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、用流程图描述算法,在程序框图中流程图是描述算法的常用工具。,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,流程图: 伪代码：,i1:sum=0,i=5,sum=sum+i,i=i+1,yes,no,输出sum的值,开始,结束,sum=0 For i=1 to 5 sum=sum+i Next I Print sum,复习与巩固,设计一个算法，求出100以内能被3整除的所有正整数，请用三种算法语言进行描述。,复习与巩固,自然语言 令I=1； 如果I能被3整除，则输出I； I=I+1; 如果I100,则返回第步； 结束,复习与巩固,流程图,开始,I=1,I能被3整除,