高中人A数学必修三-第一章学案六算法案例ppt课件

1、开场开场 学点一学点一学点二学点二学点三学点三学点四学点四1.1. 中的中的“更相减损术求两个数的最大公更相减损术求两个数的最大公约数约数. .翻译为现代汉语如下：翻译为现代汉语如下：第一步，恣意给定两个正整数，判别它们能否是偶数，第一步，恣意给定两个正整数，判别它们能否是偶数，假设是，用假设是，用2 2约简；假设不是，执行第二步约简；假设不是，执行第二步. .第二步，用两数中较大的数减去较小的数第二步，用两数中较大的数减去较小的数, ,再用再用 . .和和 构成新的一对数构成新的一对数, ,再用大数减小数再用大数减小数, ,以同样的以同样的操作不断做下去操作不断做下去, ,直到产生为止直到产

2、生为止, ,这个数这个数等数或这个数与约简的数的乘积就是最大公约数等数或这个数与约简的数的乘积就是最大公约数. .2.2.古希腊求两个正整数的最大公约数的方法是古希腊求两个正整数的最大公约数的方法是: :：用较大的数除以较小的数所得的和：用较大的数除以较小的数所得的和构成新的一对数构成新的一对数, ,继续做上面的除法继续做上面的除法, ,直到大数直到大数被小数除尽被小数除尽, ,这个较小的数就是最大公约数这个较小的数就是最大公约数. .差数差数 较小的数较小的数 一对相等的数一对相等的数 辗转相除法辗转相除法 余数余数 较小的数较小的数 前往前往 3.3.把一个把一个n n次多项式次多项式f(

3、x)=anxn f(x)=anxn ananxnxna1xa1x a0 a0改写成如下方式改写成如下方式: : f(x)= anxn f(x)= anxnananxnxna1xa1xa0a0= = . .= = . .= = . . 求多项式的值时求多项式的值时, ,首先计算最内层括号内一次多项式首先计算最内层括号内一次多项式的值的值, ,即即v1= ,v1= ,然后由内向外逐层计算一次然后由内向外逐层计算一次多项式的值多项式的值, ,即即v2=v2= , ,v3=v3= , ,vn=vn= , ,(anxn-1(anxn-1ananxnxn2 2a1)xa1)xa0 a0 (anxn-2(a

4、nxn-2ananxnxn3 3+a2)x+a2)xa1)xa1)xa0 a0 (anx(anxanan)x)x an an2 )x2 )xa1)xa1)xa0 a0 anxanxananv2xv2xanan3 3v1xv1xanan2 2vn-1xvn-1xa0a0前往前往 这样这样, ,求求n n次多项式次多项式f(x)f(x)的值就转化为的值就转化为. .上述方法称为秦九韶算法上述方法称为秦九韶算法. .察看上述秦九韶算法中的察看上述秦九韶算法中的n n个一次式个一次式, ,可见可见vkvk的计算要的计算要用到用到vk-1vk-1的值的值. .假设令假设令v0=an,v0=an,我们可以

5、得到公式我们可以得到公式: : . .这是一个在秦九韶算法中反复执行的步骤这是一个在秦九韶算法中反复执行的步骤, ,因此可用因此可用 来实现来实现. .求求n n个一次多项式的值个一次多项式的值 vo=anvo=anvk=vk-1x+an-k(k=1,2,n)vk=vk-1x+an-k(k=1,2,n)循环构造循环构造 前往前往 学点一学点一 辗转相除法辗转相除法用辗转相除法求用辗转相除法求9090与与3636的最大公约数的最大公约数. .【分析】此题调查辗转相除法求两个数的最大公约【分析】此题调查辗转相除法求两个数的最大公约数的步骤数的步骤. .运用辗转相除法求运用辗转相除法求9090与与3

6、636的最大公约数时的最大公约数时, ,先先用用9090除以除以36,36,余数为余数为18,18,用用3636除以除以18,18,余数为余数为0,180,18就是就是9090与与3636的最大公约数的最大公约数. .顺便提示一下顺便提示一下, ,两个数两个数a,ba,b的最大公的最大公约数普通写成约数普通写成(a,b),(a,b),如如9090与与3636的最大公约数为的最大公约数为18,18,写成写成(90,36)=18.(90,36)=18.【解析】令【解析】令m=90,n=36,m=2n+18,r=18.m=90,n=36,m=2n+18,r=18.令令m=36,n=18.m=36,n

7、=18.又有又有36=1836=182,2,即即m=2n,m=2n,前往前往 此时此时r=0.r=0.令令m=18,n=0.m=18,n=0.故故9090与与3636的最大公约数为的最大公约数为18.18.程序步骤如下程序步骤如下: :INPUTINPUTm=;n=;m=;n=;m=90;n=36;m=90;n=36;DODOr=m MOD nr=m MOD nm=nm=nn=rn=rLOOPLOOPUNTILUNTILr=0r=0PRINTPRINT“9090与与3636的最大公约数为的最大公约数为: :;m;mENDEND前往前往 【评析】辗转相除法是当大数被小数除尽时【评析】辗转相除法是

8、当大数被小数除尽时, ,终了终了除法运算除法运算, ,较小的数就是最大公约数较小的数就是最大公约数; ;更相减损术是当大更相减损术是当大数减去小数的差等于小数时停顿减法数减去小数的差等于小数时停顿减法, ,较小的数就是最较小的数就是最大公约数大公约数. .前往前往 用辗转相除法求用辗转相除法求8080与与3636的最大公约数的最大公约数, ,并用更相减损术检并用更相减损术检验所得结果验所得结果. .解：用辗转相除解：用辗转相除:80=36:80=362+8,36=82+8,36=84+4,8=44+4,8=42+0;2+0;用更相减损术检验用更相减损术检验:80-36=44,44-36=8,3

9、6-8=28,28-8=20,:80-36=44,44-36=8,36-8=28,28-8=20,20-8=12,12-8=4,8-4=4.20-8=12,12-8=4,8-4=4.故故8080和和3636的最大公约数是的最大公约数是4.4.前往前往 学点二学点二 更相减损术更相减损术1.1.有甲、乙、丙三种溶液有甲、乙、丙三种溶液, ,分别重分别重 kg, kg, kg. kg, kg, kg.先要将它们分别全部装入小瓶中先要将它们分别全部装入小瓶中, ,每个小瓶装入液体的分每个小瓶装入液体的分量一样量一样. .问问: :每瓶最多装多少每瓶最多装多少? ?【分析】此题调查更相减损术的计算步骤

10、及思想【分析】此题调查更相减损术的计算步骤及思想. .根根据题意据题意, ,每个小瓶装的溶液的质量应是三种溶液质量的最每个小瓶装的溶液的质量应是三种溶液质量的最大公约数大公约数. .先求恣意两个数的最大公约数先求恣意两个数的最大公约数, ,然后再求这个数然后再求这个数与第三个数的最大公约数与第三个数的最大公约数. .;367536153690369036153610536105361536120361203615361353615 361353615036809209223613541543336150625614 ;.;361536153630363036153645364536153660

11、366036153675 【解析】【解析】614433922前往前往 即和的最大公约数是即和的最大公约数是. .即的最大公约数是即的最大公约数是 . .614433361536153620362036153635363536153650365036153665366536153680 ;,;365365361036103653615365 922433614,【评析】此题调查更相减损术【评析】此题调查更相减损术. .3615前往前往 2.2.用更相减损之术求用更相减损之术求9898和和6363的最大公约数的最大公约数. .【分析】由于【分析】由于6363不是偶数不是偶数, ,把把9898和和6

12、363以大数减小数以大数减小数, ,并并辗转相减辗转相减. .【解析】【解析】98-63=35,63-35=28,35-28=7,28-7=21,21-98-63=35,63-35=28,35-28=7,28-7=21,21-7=14,14-7=7.7=14,14-7=7.所以所以9898和和6363的最大公约数为的最大公约数为7.7.【评析】等值算法是当大数减去小数的差等于小数时【评析】等值算法是当大数减去小数的差等于小数时停顿减法停顿减法, ,较小的数就是所求的最大公约数较小的数就是所求的最大公约数. .前往前往 有甲、乙、丙三种溶液分别重有甲、乙、丙三种溶液分别重147 kg,343 k

13、g,133 kg,147 kg,343 kg,133 kg,现现要将它们分别全部装入小瓶中要将它们分别全部装入小瓶中, ,每个小瓶装入液体的质量每个小瓶装入液体的质量一样一样, ,问每瓶最多装多少问每瓶最多装多少? ? 解：由题意解：由题意, ,每小瓶装的溶液的质量应是三种溶液质每小瓶装的溶液的质量应是三种溶液质量的最大公约数量的最大公约数, ,先求先求147147与与343343的最大公约数的最大公约数: : 343-147=196, 196-147=49, 343-147=196, 196-147=49, 147-49=98, 98-49=49. 147-49=98, 98-49=49.

14、所以所以147147与与343343的最大公约数是的最大公约数是49.49. 再求再求4949与与133133的最大公约数的最大公约数: : 133-49=84, 84-49=35, 133-49=84, 84-49=35, 49-35=14, 35-14=21, 49-35=14, 35-14=21, 21-14=7, 14-7=7. 21-14=7, 14-7=7. 所以所以147,343,133147,343,133的最大公约数为的最大公约数为7.7. 故每瓶最多装故每瓶最多装7 kg.7 kg.前往前往 学点三学点三 秦九韶算法秦九韶算法1.1.知函数知函数f(x)=x4-2x2-5x

15、+6,f(x)=x4-2x2-5x+6,用秦九韶算法求用秦九韶算法求f(10)f(10)的值的值. .【分析】此题调查秦九韶算法求值的步骤【分析】此题调查秦九韶算法求值的步骤. .根据秦九根据秦九韶算法韶算法, ,我们需求处置多项式的系数以及最高次项的系数我们需求处置多项式的系数以及最高次项的系数. .该多项式函数没有中间的三次项该多项式函数没有中间的三次项, ,应先把多项式变形为应先把多项式变形为f(x)=x4+0f(x)=x4+0 x3-2x2-5x+6x3-2x2-5x+6再处置再处置. .【解析】【解析】v0=1,v0=1, v1=1 v1=110+0=10,10+0=10, v2=1

16、0 v2=1010-2=98,10-2=98, v3=98v3=9810-5=975,10-5=975, v4=975v4=97510+6=9 756,10+6=9 756, f(10)=9 756. f(10)=9 756.前往前往 【评析】当多项式函数中间出现空项要以系数为零的【评析】当多项式函数中间出现空项要以系数为零的齐次项补齐齐次项补齐. .否那么否那么, ,在处置问题时在处置问题时, ,多项式运算的次数不多项式运算的次数不会到达对应的次数会到达对应的次数. .因此因此, ,我们在运用秦九韶算法求多项式我们在运用秦九韶算法求多项式的值时的值时, ,先要依次从最高次项往常数项察看各项能

17、否都存先要依次从最高次项往常数项察看各项能否都存在在, ,再进展处置再进展处置. .前往前往 2.2.求多项式求多项式f(x)=x5+5x4+10 x3+10 x2+5x+1f(x)=x5+5x4+10 x3+10 x2+5x+1当当x=-2x=-2时的值时的值. .【解析】解：先改写多项式【解析】解：先改写多项式, ,再由内向外计算再由内向外计算. . f(x)=x5+5x4+10 x3+10 x2+5x+1 f(x)=x5+5x4+10 x3+10 x2+5x+1=(x+5)x+10)x+10)x+5)x+1.=(x+5)x+10)x+10)x+5)x+1.而而x=-2,x=-2,所以有所

18、以有: :v0=1,v1=v0 x+a4=1v0=1,v1=v0 x+a4=1(-2)+5=3,(-2)+5=3,v2=vv2=vx+a3=3x+a3=3(-2)+10=4,(-2)+10=4,v3=v2x+a2=4v3=v2x+a2=4(-2)+10=2,(-2)+10=2,v4=v3x+a1=2v4=v3x+a1=2(-2)+5=1,(-2)+5=1,v5=v4x+a0=1v5=v4x+a0=1(-2)+1=-1.(-2)+1=-1.所以当所以当x=-2x=-2时，多项式的值为时，多项式的值为-1.-1.前往前往 【分析】此题调查秦九韶算法【分析】此题调查秦九韶算法. . 【评析】利用秦九

19、韶算法计算多项式的值关键是能正【评析】利用秦九韶算法计算多项式的值关键是能正确地将所给多项式改写确地将所给多项式改写, ,然后由内向外逐次计算然后由内向外逐次计算, ,由于后项由于后项计算需用到前项的结果计算需用到前项的结果, ,故应仔细、细心故应仔细、细心, ,确保中间结果的确保中间结果的准确性准确性. .前往前往 知一个知一个5 5次多项式为次多项式为:f(x)=5x5+2x4+3.5x3-2.6x2+1.7x-:f(x)=5x5+2x4+3.5x3-2.6x2+1.7x-0.8,0.8,用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x=5x=5时的值时的值. .解：解： f(x)=

20、(5x+2)x+3.5)x-2.6)x+1.7)x-0.8, f(x)=(5x+2)x+3.5)x-2.6)x+1.7)x-0.8, 当当x=5x=5时时, , v0=5; v0=5; v1=5 v1=55+2=27;5+2=27; v2=27 v2=275+3.5=.5;5+3.5=.5; v3=.5 v3=.55-2.6=689.9;5-2.6=689.9; v4=689.9 v4=689.95+1.7=3 451.2;5+1.7=3 451.2; v5=3 451.2 v5=3 451.25-0.8=17 255.2.5-0.8=17 255.2. 所以当所以当x=5x=5时时, ,多项

21、式的值为多项式的值为17 255.2.17 255.2.前往前往 学点四学点四 进位制进位制将将8 8进制数进制数314 706(8)314 706(8)转化为十进制数转化为十进制数. .【分析】此题调查进位制的换算步骤及本卷须知【分析】此题调查进位制的换算步骤及本卷须知. .利利用把用把k k进制数转化为十进制数的普通方法就可以把进制数转化为十进制数的普通方法就可以把8 8进制数进制数314 706(8)314 706(8)化为十进制数化为十进制数. .【解析】【解析】314 706(8)=3314 706(8)=385+185+184+484+483+783+782+082+081+681

22、+680=104 902.80=104 902.所以所以314 706(8)314 706(8)化为十进制数是化为十进制数是104 902.104 902.8 8进制数进制数314 706314 706中共有中共有6 6位位, ,因此可令因此可令a=314 706,a=314 706,k=8,n=6.k=8,n=6.【评析】此题调查进位制【评析】此题调查进位制. .前往前往 将将389389化成四进制数的末位是化成四进制数的末位是. .1( ,1( ,末位是第一个余数末位是第一个余数,389=12 011(4).,389=12 011(4).留意留意: :余数自下而上陈列余数自下而上陈列.).

23、)4 389 4 389 余余4 97 14 97 14 24 14 24 14 6 04 6 04 1 24 1 2 0 1 0 1第一个余数第一个余数前往前往 1.1.如何了解辗转相除法如何了解辗转相除法? ? 辗转相除法是西方古代数学中的一个典型算法辗转相除法是西方古代数学中的一个典型算法. .更相更相减损术和秦九韶算法都是我国古代数学中的著名算法减损术和秦九韶算法都是我国古代数学中的著名算法, ,而而排序法和进位制算法是计算机科学中普遍运用的算法排序法和进位制算法是计算机科学中普遍运用的算法. .这这些算法案例不仅蕴涵着深化的算法思想些算法案例不仅蕴涵着深化的算法思想, ,而且也更能表达而且也更能表达出算法的重要性和有效性出算法的重要性和有效性. .因此因此, ,要真实了解算法案例的内要真实了解算法案例的内容及详细算法的关键步骤容及详细算法的关键步骤. .前往前往 2.2.如何掌握进位制如何掌握进位制? ? 进位制是一种记数方式进位制是一种记数方式, ,用有限的数字在不同的位置用有