高中数学 1.6 算法算法案例同步学案PPT 新人教A必修

学点一,学点二,学点三,学点四,1.九章算术中的“更相减损术”求两个数的最大公约数.翻译为现代汉语如下：第一步，任意给定两个正整数，判断它们是否是偶数，若是，用2约简；若不是，执行第二步.第二步，用两数中较大的数减去较小的数,再用.和构成新的一对数,再用大数减小数,以同样的操作一直做下去,直到产生为止,这个数（等数）或这个数与约简的数的乘积就是最大公约数.2.古希腊求两个正整数的最大公约数的方法是:：用较大的数除以较小的数所得的和构成新的一对数,继续做上面的除法,直到大数被小数除尽,这个较小的数就是最大公约数.,差数,较小的数,一对相等的数,辗转相除法,余数,较小的数,3.把一个n次多项式f(x)=anxnanxna1xa0改写成如下形式:f(x)=anxnanxna1xa0=.=.=.求多项式的值时,首先计算最内层括号内一次多项式的值,即v1=,然后由内向外逐层计算一次多项式的值,即v2=,v3=,vn=,(anxn-1anxn2a1)xa0,(anxn-2anxn3+a2)xa1)xa0,(（(anxan)xan2)xa1)xa0,anxan,v2xan3,v1xan2,vn-1xa0,这样,求n次多项式f(x)的值就转化为.上述方法称为秦九韶算法.观察上述秦九韶算法中的n个一次式,可见vk的计算要用到vk-1的值.若令v0=an,我们可以得到公式:.这是一个在秦九韶算法中反复执行的步骤,因此可用来实现.,求n个一次多项式的值,vo=anvk=vk-1x+an-k(k=1,2,n),循环结构,学点一辗转相除法,用辗转相除法求90与36的最大公约数.【分析】本题考查辗转相除法求两个数的最大公约数的步骤.使用辗转相除法求90与36的最大公约数时,先用90除以36,余数为18,用36除以18,余数为0,18就是90与36的最大公约数.顺便提示一下,两个数a,b的最大公约数一般写成(a,b),如90与36的最大公约数为18,写成(90,36)=18.【解析】令m=90,n=36,m=2n+18,r=18.令m=36,n=18.又有36=182,即m=2n,此时r=0.令m=18,n=0.故90与36的最大公约数为18.程序步骤如下:INPUTm=;n=;m=90;n=36;DOr=mMODnm=nn=rLOOPUNTILr=0PRINT“90与36的最大公约数为:”;mEND,【评析】辗转相除法是当大数被小数除尽时,结束除法运算,较小的数就是最大公约数;更相减损术是当大数减去小数的差等于小数时停止减法,较小的数就是最大公约数.,用辗转相除法求80与36的最大公约数,并用更相减损术检验所得结果.,解：用辗转相除:80=362+8,36=84+4,8=42+0;用更相减损术检验:80-36=44,44-36=8,36-8=28,28-8=20,20-8=12,12-8=4,8-4=4.故80和36的最大公约数是4.,学点二更相减损术,1.有甲、乙、丙三种溶液,分别重kg,kg,kg.先要将它们分别全部装入小瓶中,每个小瓶装入液体的重量相同.问:每瓶最多装多少?【分析】本题考查更相减损术的计算步骤及思想.根据题意,每个小瓶装的溶液的质量应是三种溶液质量的最大公约数.先求任意两个数的最大公约数,然后再求这个数与第三个数的最大公约数.,【解析】,即和的最大公约数是.即的最大公约数是.,【评析】本题考查更相减损术.,2.用更相减损之术求98和63的最大公约数.【分析】由于63不是偶数,把98和63以大数减小数,并辗转相减.【解析】98-63=35,63-35=28,35-28=7,28-7=21,21-7=14,14-7=7.所以98和63的最大公约数为7.【评析】等值算法是当大数减去小数的差等于小数时停止减法,较小的数就是所求的最大公约数.,有甲、乙、丙三种溶液分别重147kg,343kg,133kg,现要将它们分别全部装入小瓶中,每个小瓶装入液体的质量相同,问每瓶最多装多少?,解：由题意,每小瓶装的溶液的质量应是三种溶液质量的最大公约数,先求147与343的最大公约数:343-147=196,196-147=49,147-49=98,98-49=49.所以147与343的最大公约数是49.再求49与133的最大公约数:133-49=84,84-49=35,49-35=14,35-14=21,21-14=7,14-7=7.所以147,343,133的最大公约数为7.故每瓶最多装7kg.,学点三秦九韶算法,1.已知函数f(x)=x4-2x2-5x+6,用秦九韶算法求f(10)的值.【分析】本题考查秦九韶算法求值的步骤.根据秦九韶算法,我们需要处理多项式的系数以及最高次项的系数.该多项式函数没有中间的三次项,应先把多项式变形为f(x)=x4+0x3-2x2-5x+6再处理.【解析】v0=1,v1=110+0=10,v2=1010-2=98,v3=9810-5=975,v4=97510+6=9756,f(10)=9756.,【评析】当多项式函数中间出现空项要以系数为零的齐次项补齐.否则,在处理问题时,多项式运算的次数不会达到对应的次数.因此,我们在应用秦九韶算法求多项式的值时,先要依次从最高次项往常数项观察各项是否都存在,再进行处理.,2.求多项式f(x)=x5+5x4+10 x3+10 x2+5x+1当x=-2时的值.,【解析】解：先改写多项式,再由内向外计算.f(x)=x5+5x4+10 x3+10 x2+5x+1=(x+5)x+10)x+10)x+5)x+1.而x=-2,所以有:v0=1,v1=v0 x+a4=1(-2)+5=3,v2=vx+a3=3(-2)+10=4,v3=v2x+a2=4(-2)+10=2,v4=v3x+a1=2(-2)+5=1,v5=v4x+a0=1(-2)+1=-1.所以当x=-2时，多项式的值为-1.,【分析】本题考查秦九韶算法.,【评析】利用秦九韶算法计算多项式的值关键是能正确地将所给多项式改写,然后由内向外逐次计算,由于后项计算需用到前项的结果,故应认真、细心,确保中间结果的准确性.,已知一个5次多项式为:f(x)=5x5+2x4+3.5x3-2.6x2+1.7x-0.8,用秦九韶算法求这个多项式当x=5时的值.解：f(x)=(5x+2)x+3.5)x-2.6)x+1.7)x-0.8,当x=5时,v0=5;v1=55+2=27;v2=275+3.5=138.5;v3=138.55-2.6=689.9;v4=689.95+1.7=3451.2;v5=3451.25-0.8=17255.2.所以当x=5时,多项式的值为17255.2.,学点四进位制,将8进制数314706(8)转化为十进制数.【分析】本题考查进位制的换算步骤及注意事项.利用把k进制数转化为十进制数的一般方法就可以把8进制数314706(8)化为十进制数.【解析】314706(8)=385+184+483+782+081+680=104902.所以314706(8)化为十进制数是104902.8进制数314706中共有6位,因此可令a=314706,k=8,n=6.【评析】本题考查进位制.,将389化成四进制数的末位是.,1(,末位是第一个余数,389=12011(4).注意:余数自下而上排列.),4389余4971424146041201,第一个余数,1.如何理解辗转相除法?辗转相除法是西方古代数学中的一个典型算法.更相减损术和秦九韶算法都是我国古代数学中的著名算法,而排序法和进位制算法是计算机科学中普遍使用的算法.这些算法案例不仅蕴涵着深刻的算法思想,而且也更能体现出算法的重要性和有效性.因此,要切实理解算法案例的内容及具体算法的关键步骤.,2.如何掌握进位制?进位制是一种记数方式,用有限的数字在不同的位置表示不同的数值.可使用数字符号的个数称为基数,基数为n,即可称n进位制,简称n进制.现在最常用的是十进制,通常使用10个阿拉伯数字09进行记数.对于任何一个数,我们可以用不同的进位制来表示.比如:十进数57,可以用二进制表示为111001,也可以用八进制表示为71,用十六进制表示为39,它们所代表的数值都是一样的.表示各种进制数一般在数字右下角加注来表示.如111001(2)表示二进制数,34(5)表示