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

1.1.1算法的概念,章头图说明,章头图的后景是元代朱世杰所著的四元玉鉴，前景的前部是一台计算机，后部是盛行一时的计算工具算筹和算盘。,中国古代数学在世界数学史上一度居于领先地们，它注重实际问题的解决，以算法为中心，寓理于算，其中蕴涵了丰富的算法思想，算筹是中国古代的计算工具，在春秋时期已经很普遍；算盘在明代开始盛行，即使在计算机普及的今天，许多人仍然在使用算盘。中国古代涌现了许多著名的数学家，如三国及两晋时期的赵爽、刘徽，南北朝的祖冲之、宋、元时期的秦九韶、杨辉、朱世杰，等。古时著名的数学专著如九章算术周髀算经数书九章四元玉鉴等。所有这些成就，都使中国数学曾经处于世界巅峰。,数学史简介,计算机的问世可谓是20世纪最伟大的科学技术发明。它把人类社会带进了信息技术时代。,计算机是对人脑的模拟，它强化了人的思维智能；,21世纪信息社会的两个主要特征：“计算机无处不在”“数学无处不在”,21世纪信息社会对科技人才的要求：-会“用数学”解决实际问题-会用计算机进行科学计算,算法的研究和应用正是本课程的主题！,现代科学研究的三大支柱,研究算法,而算法是计算机科学的重要基础。就像使用算盘一样，人们需要给计算机编制“口决”算法，才能让它工作，否则超级计算机只是一堆废铁而已。,要想了解计算机的工作原理，算法的学习是一个开始,问题的提出,有一个农夫带一条狼狗、一只羊和一筐白菜过河。如果没有农夫看管，则狼狗要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？,问题的提出,有一个农夫带一条狼狗、一只羊和一筐白菜过河。如果没有农夫看管，则狼狗要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？,方法和过程：,1、带羊到对岸，返回；,2、带菜到对岸，并把羊带回；,3、带狼狗到对岸，返回；,4、带羊到对岸。,我们可以归纳它的步骤:,第一步:-2，得5y=3,第三步:,第四步：得到方程组的解为：x=1/5,y=3/5,第二步：解，得,第一步：-，得,第三步：将代入，得,第四步：得到方程组的解.,二、建构数学,1、算法的含义,算法（algorithm)古代指的是用阿拉伯数字进行算术运算的过程。在数学中，通常是指按照一定规则解决某一类问题的明确和有限的步骤。现在，算法通常可以编成计算机程序，让计算机执行并解决问题。,注意：解决某一类问题，明确而且有效，有限性，程序性，不唯一,【例】写出你在家中烧开水的过程的一个算法。,总结：“第1”其实大部分事情都是按照一定的程序执行，因此要理清事情的每一步。“第2”判断水是否烧开与是否继续烧火的过程是一个反馈与判断过程，因此有必要不断重复过程“3”,解:1、往壶内注水；2、点火加热；3观察：如果水开，则停止烧火，否则继续烧火；4、如果水未开，重复“3”直至水开。,请写出下面一个算法：,写出已知直角三角形两边a,b，求斜边的一个算法,解：输入直角三角形两边a,b的值；计算=输出斜边长L的值。,请试写出一个算法：,写出求一个数绝对值的一个算法,解：请输入要求绝对值的数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,b。根据“f(a)f(m)0”是否成立，取出零点所在的区间a,m或m,b，仍记为a,b，对所得的区间a,b重复上述步骤，直到包含零点的区间a,b“足够小“，则a,b内的数可以作为方程的近似解。,例2,用二分