资源预览内容
第1页 / 共13页
第2页 / 共13页
第3页 / 共13页
第4页 / 共13页
第5页 / 共13页
第6页 / 共13页
第7页 / 共13页
第8页 / 共13页
第9页 / 共13页
第10页 / 共13页
亲,该文档总共13页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
高中数学 第八课时 算法案例教案 苏教版必修3第八课时 算法案例教学目标:本节通过算法案例的学习,进一步理解算法的含义,掌握算法设计的常用方法.教学重点:如何在伪代码中运用条件语句.教学难点:如何在伪代码中运用条件语句.教学过程:.课题导入1.中国古代数学中算法的内容是非常丰富的,比如,中国古代数学著作九章算术中介绍了下述“约分术”:“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也.以等数约之.”给出了求任意两个数的最大公约数的一种算法,被后人称为“更相减损术”.这种方法与欧氏的辗转相除法异曲同工,本质上是相同的.2.中国是研究不定方程最早的国家,公元初的五家共井问题就是一个不定方程组问题,公元5世纪的张丘建算经中的百鸡问题标志着中国对不定方程理论有了系统研究.秦九韶的大衍求一术将不定方程与同余理论联系起来.研究不定方程要解决三个问题:判断何时有解;有解时决定解的个数;求出所有的解.二分法是用计算机求解多项式方程的一种常用方法.基本思想是:如果取a,b的中点x0=(a+b)/2;若f(x0)=0,则x0就是方程的根,若f(a)f(x0)0,则解在(x0,b)上,以x0代替a,否则解在(a,x0)之间,以x0代替b,重复上述步骤,直到|ab|c,c是一个很小的正数,计算终止,x0就是方程的根.讲授新课例1:古今中外,许多人致力于圆周率的研究与计算.为了计算出圆周率的越来越好的近似值,一代代的数学家为这个神秘的数贡献了无数的时间与心血.我国东汉的数学家刘徽利用“割圆术”计算圆的面积及圆周率.“割圆术”被称为千古绝技,它的原理是用圆内接正多边形的面积去逼近圆的面积,具体计算如下:在单位圆内作内接正六边形,其面积记为A1,边长记为a1,在此基础上作圆内接正12边形,面积记为A2,边长为a2一直做下去,记该圆的内接正62n1边形面积为An,边长为an.由于所考虑的是单位圆,计算出的An即为圆周率的近似值,n越大,An与越接近.你能设计这样计算圆周率的一个算法吗?我的思路:应首先推导出an,an1,An,An1的关系.如图,设PQ为圆内接正62n1边形的一边,即PQ=an1,OR为与PQ垂直的半径,R为PQ弧的平分点,显然PR=an.a1=1,an=PR=(n=2,3,4),A1=61=,An=62n1|OR|PT|=32n2an1(n=2,3,4).通过上面两式,从a11开始进行迭代,可逐步计算出an与An.由于所考虑的是单位圆,计算出的An即为圆周率的近似值,n越大,An与越接近.算法和流程图如下:BeginRead n1aFor I from 2 to nA32I2aaSqrt22Sqrt1a2/4;Print I,A,aEnd forEnd流程图:例2:有一个故事是讲唐代大官杨埙提拔官员的经过.他让两个资格职位相同的候选人解答下面这个问题,谁先答出就提拔谁.“有人在林中散步,无意中听到几个强盗在商量怎样分配抢来的布匹.若每人分6匹,就剩5匹;若每人分7匹,就差8匹.问共有强盗几个?布匹多少?”你能用一个简单算式求出强盗个数和布匹数吗?我的思路:这个问题可看作二元一次方程组问题.问题的特点是给出两种分配方案,一种分法分不完,一种分法不够分.中国古代的九章算术一书中搜集了许多这类问题,各题都有完整的解法,后人称这种算法为“盈不足术”.这种算法可以概括为两句口诀:有余加不足,大减小来除.公式:(盈不足)两次所得之差人数,每人所得数人数盈物品总数,求得强盗有(85)(76)13(人),布匹有613583(匹).伪代码:Read a,b,c,dx(a+b)/(dc)ycx+aprint x,y流程图:例3:由F0=1,F1=1,Fn=Fn2+Fn1所定义的数列Fn,称为斐波那契数列,试设计一个求数列的前100项的值的算法,画出流程图并用伪代码表示.我的思路:数列Fn有个特点,前两个数都是1,从第3个数开始,每个数都是前两个数的和,例如:3是1和2的和;13是5和8的和等等.此问题的算法用流程图和伪代码表示:a1;b1;n1;输出n,;while nb),求它们的最大公约数.解析:求两个正整数a、b(ab)的最大公约数,可以归结为求一数列:a,b,r1,r2,rn1,rn,rn+1,0此数列的首项与第二项是a和b,从第三项开始的各项,分别是前两项相除所得的余数,如果余数为0,它的前项rn+1即是a和b的最大公约数,这种方法叫做欧几里得辗转相除法,其算法如下:S1输入a,b(ab);S2求a/b的余数r;S3如果r0,则将ba,rb,再次求a/b的余数r,转至S2;S4输出最大公约数b.伪代码如下:10Read a,b20rmod(a,b)30Ifr=0thenGoto 8040Else50ab60br70Goto 2080Print b流程图如下:点评:算法的多样性:对于同一个问题,可以有不同的算法.例如求1+2+3+100的和,可以采用如下方法:先求1+2,再加3,再加4,一直加到100,最后得到结果5050.也可以采用这样的方法:1+2+3+100=(1+100)+(2+99)+(3+98)+(50+51)=50101=5050.显然,对于算法来说,后一种方法更简便,而循环累加更适用于计算机解题.因此,为了有效地进行解题,不仅要保证算法正确,还要选择好的算法,即方法简单、运算步骤少,能迅速得出正确结果的算法.例5:求1734,816,1343的最大公约数.分析:三个数的最大公约数分别是每个数的约数,因此也是任意两个数的最大公约数的约数,也就是说三个数的最大公约数是其中任意两个数的最大公约数与第三个数的最大公约数.解:用“辗转相除法”.先求1734和816的最大公约数,1734=8162+102;816=1028;所以1734与816的最大公约数为102.再求102与1343的最大公约数,1343=10213+17;102=176.所以1343与102的最大公约数为17,即1734,816,1343的最大公约数为17.例6:猴子吃桃问题:有一堆桃子不知数目,猴子第一天吃掉一半,觉得不过瘾,又多吃了一只,第二天照此办法,吃掉剩下桃子的一半另加一个,天天如此,到第十天早上,猴子发现只剩一只桃子了,问这堆桃子原来有多少个?解析:此题粗看起来有些无从着手的感觉,那么怎样开始呢?假设第一天开始时有a1只桃子,第二天有a2只第9天有a9只,第10天有a10只.在a1,a2,a10中,只有a10=1是知道的,现要求a1,而我们可以看出a1,a2,a10之间存在一个简单的关系:a9=2(a10+1),a8=2(a9+1),a1=2(a2+1).也就是:ai=2(ai+1+1)i=9,8,7,6,1.这就是此题的数学模型.再考察上面从a9,a8直至a1的计算过程,这其实是一个递推过程,这种递推的方法在计算机解题中经常用到.另一方面,这九步运算从形式上完全一样,不同的只是ai的下标而已.由此,我们引入循环的处理方法,并统一用a0表示前一天的桃子数,a1表示后一天的桃子数,将算法改写如下:S1a11;第10天的桃子数,a1的初值S2i9;计数器初值为9S3a02(a1+1);计算当天的桃子数S4a1a0;将当天的桃子数作为下一次计算的初值S5ii1;S6若i1,转S3;S7输出a0的值;伪代码如下:10a1120i930a02(a1+1)40a1a0.50ii160Ifi1 then Goto 3070Else80Print a0流程图如下:点评:这是一个从具体到抽象的过程,具体方法:(1)弄清如果由人来做,应该采取哪些步骤;(2)对这些步骤进行归纳整理,抽象出数学模型;(3)对其中的重复步骤,通过使用相同变量等方式求得形式的统一,然后简练地用循环解决.课堂练习课本P30 1,2.课时小结算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗点说,就是计算机解题的过程.1.本节通过对解决具体问题过程与步骤的分析(如求两个数的最大公约数),体会算法的思想,进一步了解算法的含义.2.本节通过阅读中国古代数学中的算法案例,如约分术,体会中国古代数学对世界数学发展的贡献.通过学生自己的亲身实践,亲自去解决几个算法设计的问题,才能体会到算法的基本思想.数学的其他内容与算法密切相关,如函数、数列等.我们在学习这些内容时要和算法联系起来.课后作业课本P31 1,3.变式练习1.数4557、1953、5115的最大公约数是()A.31B.93C.217D.651答案:B2.下面的伪代码的算法目的是()10Read x,y20mx30ny40If m/n=int(m/n) then Goto 9050cmint(m/n)n60mn70nc80Goto 4090a(xy)/n100 Print aA.求x,y的最小公倍数B.求x,y的最大公约数C.求x被y整除的商D.求y除以x的余数答案:B3.下面的伪代码的算法目的是.ReadX,YIf XY thenPrint XElsePrint YEnd if答案:输出x,y两个值中较大的一个值4.下面的伪代码的算法目的是.Reada,b,c,If ab thentaabbtElse if ac thentaacctElse if bc thentbbccbEnd ifPrint a,b,c答案:输入三个数,要求由小到大的顺序输出5.流程图填空:输入x的值,通过函数y=求出y的值.其算法流程图如下:答案:x1x103x116.根据下面的流程图写出其算法的伪代码.答案:解:这是计算2+4+6+200的一个算法,可以用循环语句表示为T0For I from 2 to 200 step 2TT+IEnd for7.输入一个华氏温度,要求输出摄氏温度.公式为C=(F32).写出其算法的伪代码.答案:解:这是顺序结构.其伪代码如下:Read FC(F32)Print C8.一个小球从100 m高度自由落下,每次落地后反跳回原高度的一半,再落下.设计一个算法,求它在第10次落地时共经过多少米?第10次反弹多高?画出流程图并用伪代码表示.答案:解:这是一个循环结构,可以用循环语句实现.伪代码:S100HS/2For n from 2 to10SS+2HHH/2E
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号