高中数学 16 算法算法案例同步学案(PPT) 新人教A版必修3 学案VIP免费

开始学点一学点二学点三学点四1.《九章算术》中的“更相减损术”求两个数的最大公约数.翻译为现代汉语如下：第一步，任意给定两个正整数，判断它们是否是偶数，若是，用2约简；若不是，执行第二步.第二步，用两数中较大的数减去较小的数,再用.和构成新的一对数,再用大数减小数,以同样的操作一直做下去,直到产生为止,这个数（等数）或这个数与约简的数的乘积就是最大公约数.2.古希腊求两个正整数的最大公约数的方法是:：用较大的数除以较小的数所得的和构成新的一对数,继续做上面的除法,直到大数被小数除尽,这个较小的数就是最大公约数.差数较小的数一对相等的数辗转相除法余数较小的数返回3.把一个n次多项式f(x)=anxn＋an－１xn－１＋…＋a1x＋a0改写成如下形式:f(x)=anxn＋an－１xn－１＋…＋a1x＋a0=.=.=…=.求多项式的值时,首先计算最内层括号内一次多项式的值,即v1=,然后由内向外逐层计算一次多项式的值,即v2=,v3=,…vn=,(anxn-1＋an－１xn－2＋…＋a1)x＋a0((anxn-2＋an－１xn－3＋…+a2)x＋a1)x＋a0(…（(anx＋an－１)x＋an－2)x＋…＋a1)x＋a0anx＋an－１v2x＋an－3v1x＋an－2vn-1x＋a0返回这样,求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=18×2,即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=36×2+8,36=8×4+4,8=4×2+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.先要将它们分别全部装入小瓶中,每个小瓶装入液体的重量相同.问:每瓶最多装多少?【分析】本题考查更相减损术的计算步骤及思想.根据题意,每个小瓶装的溶液的质量应是三种溶液质量的最大公约数.先求任意两个数的最大公约数,然后再求这个数与第三个数的最大公约数.;;;;;367536153690369036153610536105361536120361203615361353615361353615036809209223613541543336150625614;;;.;;;361536153630363036153645364536153660366036153675【解析】614433922返回即和的最大公约数是.即的最大公约数是.614433361536153620362036153635363536153650365036153665366536153680;;;;,;;365365361036103653615365922433614,,【评析】本题考查更相减损术.3615返回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....