高中数学必修三课件1.1.1算法的概念

章头图说明,章头图的后景是元代朱世杰所著的四元玉鉴，前景的前部是一台计算机，后部是盛行一时的计算工具算筹和算盘。,四元玉鉴,作者朱世杰，全书共三卷，分二十四门、二百八十八问，所有问题都与方程式或方程组有关。介绍了朱世杰在多元高次方程组的解法”四元术”、高阶等差级数的计算”垛积术”以及”招差术”（有限差分）等方面的研究成果。它是一部成就辉煌的数学名著，受到近代数学史研究者的高度评价，认为是中国数学著作中最重要的一部，同时也是中世纪最杰出的数学著作之一。,中国古代数学在世界数学史上一度居于领先地们，它注重实际问题的解决，以算法为中心，寓理于算，其中蕴涵了丰富的算法思想，算筹是中国古代的计算工具，在春秋时期已经很普遍；算盘在明代开始盛行，即使在计算机普及的今天，许多人仍然在使用算盘。中国古代涌现了许多著名的数学家，如三国及两晋时期的赵爽、刘徽，南北朝的祖冲之、宋、元时期的秦九韶、杨辉、朱世杰，等。古时著名的数学专著如九章算术周髀算经数书九章四元玉鉴等。所有这些成就，都使中国数学曾经处于世界巅峰。,数学史简介,割圆术,公元263年，中国数学家刘徽在九章算术注中提出“割圆”之说，即先作一个圆内接正四边形，以此为基础作一个圆内接正八边形，再逐次加倍其边数，得到正16边形、正32边形等等，直至正多边形的边长小到恰与它们各自所在的圆周部分重合，他认为就可以完成化圆为方问题。他从圆内接正六边形开始，每次把边数加倍，直至圆内接正96边形，算得圆周率为3.14或157/50，后人称之为徽率。书中还记载了圆周率更精确的值3927/1250（等于3.1416）。刘徽断言“割之弥细，所失弥少，割之又割，以至于不可割，则与圆合体，而无所失矣”。,秦九韶算法,秦九韶（约公元1202年1261年），字道古，南宋末年人，秦九韶算法是一种将一元n次多项式的求值问题转化为n个一次式的算法。其大大简化了计算过程，即使在现代，利用计算机解决多项式的求值问题时，秦九韶算法依然是最优的算法。把一个n次多项式f(x)=anxn+an-1x(n-1)+.+a1x+a0改写成如下形式：f(x)=anxn+an-1x(n-1)+.+a1x+a0=(anx(n-1)+an-1x(n-2)+.+a1)x+a0=(anx(n-2)+an-1x(n-3)+.+a2)x+a1)x+a0=.=(.(anx+an-1)x+an-2)x+.+a1)x+a0.求多项式的值时，首先计算最内层括号内一次多项式的值，即v1=anx+an-1然后由内向外逐层计算一次多项式的值，即v2=v1x+an-2v3=v2x+an-3.vn=vn-1x+a0这样，求n次多项式f(x)的值就转化为求n个一次多项式的值。（注：中括号里的数表示下标）上述方法称为秦九韶算法。直到今天，这种算法仍是多项式求值比较先进的算法,计算机的问世可谓是20世纪最伟大的科学技术发明。它把人类社会带进了信息技术时代。,计算机是对人脑的模拟，它强化了人的思维智能；,21世纪信息社会的两个主要特征：“计算机无处不在”“数学无处不在”,21世纪信息社会对科技人才的要求：-会“用数学”解决实际问题-会用计算机进行科学计算,计算机科学与技术和软件工程、信息安全、网络工程、软件工程1、网页制作，将来去网站工作！2、学习3DMAX等软件，去作动画！3、学习美术设计！4、网络，将来考个CCNA，去专业组网！5、在保证能顺利毕业的前提下，去疯狂玩游戏，做个职业玩家或做一个或几个网络游戏的GM。,算法的研究和应用正是本课程的主题！,现代科学研究的三大支柱,研究算法,而算法是计算机科学的重要基础。就像使用算盘一样，人们需要给计算机编制“口决”算法，才能让它工作，否则超级计算机只是一堆废铁而已。,要想了解计算机的工作原理，算法的学习是一个开始,1.1.1算法的概念,把大象放进冰箱里需要几步？,第一步，把冰箱门打开,第二步，把大象装进去,第三步，把冰箱门关上,问题的提出,有一个农夫带一条狼狗、一只羊和一筐白菜过河。如果没有农夫看管，则狼狗要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？,方法和过程：,1、带羊到对岸，返回；,2、带菜到对岸，并把羊带回；,3、带狼狗到对岸，返回；,4、带羊到对岸。,我们可以归纳它的步骤:,第一步:-2，得5y=3,第三步:,第四步：得到方程组的解为：x=1/5,y=3/5,第二步：解，得,第一步：-，得,第三步：将代入，得,第四步：得到方程组的解.,二、建构数学,1、算法的含义,算法（algorithm)古代指的是用阿拉伯数字进行算术运算的过程。在数学中，通常是指按照一定规则解决某一类问题的明确和有限的步骤。现在，算法通常可以编成计算机程序，让计算机执行并解决问题。,注意：解决某一类问题，明确而且有效，有限性，程序性，不唯一,【例】写出你在家中烧开水的过程的一个算法。,总结：“第1”其实大部分事情都是按照一定的程序执行，因此要理清事情的每一步。“第2”判断水是否烧开与是否继续烧火的过程是一个反馈与判断过程，因此有必要不断重复过程“3”,解:1、往壶内注水；2、点火加热；3观察：如果水开，则停止烧火，否则继续烧火；4、如果水未开，重复“3”直至水开。,请试写出一个算法：,写出求一个数绝对值的一个算法,解：请输入要求绝对值的数a.,若a=0,则b=0(b为a的绝对值)。若a0，则b=a；若a0，则b=-a.,输出a的绝对值b。,新课讲解,算法的基本特点,1、有限性,一个算法应包括有限的操作步骤，能在执行有穷的操作步骤之后结束。,2、确定性,一个算法的计算规则及相应的计算步骤必须是唯一确定的，既不能含糊其词，也不能有二义性。,3、有效性,算法中的每一个步骤都是可以在有限的时间内有效地完成的基本操作，并能得到确定的结果。,广播操图解是广播操的算法；菜谱是做菜的算法；歌谱是一首歌曲的算法；空调说明书是空调使用的算法等,例1、（1）设计一个算法，判断7是否为质数。（2）设计一个算法，判断35是否为质数。,算法（1）,第一步，用2除7，得到余数1。因为余数不为0，所以2不能整除7。,三、数学运用,第二步，用3除7，得到余数1。因为余数不为0，所以3不能整除7。,第三步，用4除7，得到余数3。因为余数不为0，所以4不能整除7。,第四步，用5除7，得到余数2。因为余数不为0，所以5不能整除7。,第五步，用6除7，得到余数1。因为余数不为0，所以6不能整除7。因此，7是质数。,例1、（1）设计一个算法，判断7是否为质数。（2）设计一个算法，判断35是否为质数。,算法（2）,第一步，用2除35，得到余数1。因为余数不为0，所以2不能整除35。,三、数学运用,第二步，用3除35，得到余数2。因为余数不为0，所以3不能整除35。,第三步，用4除35，得到余数3。因为余数不为0，所以4不能整除35。,第四步，用5除35，得到余数0。因为余数为0，所以5能整除35。因此，35不是质数。,你能写出“判断整数n(n2)是否为质数”的算法吗？,第一步，给定大于2的整数n。,四、数学探究,第二步，令i=2.,第三步，用i除n，得到余数r。第四步：判断余数r是否为0，若是则n不是质数，结束算法；否则，将i的值增加1，仍用i表示。,第五步，判断i是否大于(n-1)，若是，则n是质数，结束算法；否则，返回第三步。,算法分析：对于任意的整数n(n2),若用i表示2（n-1)中的任意整数，则“判断n是否为质数“的算法包含下面的重复操作：用i除n，得到余数r，判断余数r是否为0，若是，则n不是质数；否则，将i的值增加1，再执行同样的操作这个操作一直要进行到i的值等于(n-1)为止。因此，”判断i是否为质数“的算法可以写成：,例2,用二分法设计一个求方程的近似正根的算法，精确度0.05。,算法分析：令f(x)=x2-2=0(x0)，则方程x2-2=0的解就是函数f(x)的零点。“二分法”的基本思想是：把函数f(x)的零点所在的区间a,b(满足f(a)f(b)0)“一分为二”。得到a,m和m