学年高中数学 1.6 算法算法案例同步学案（PPT） 新人教A必修3.ppt
开始开始 2021/8/8 星期日12021/8/8 星期日21.1.九章算术中的九章算术中的“更相减损术更相减损术”求两个数的最大求两个数的最大公约数公约数.翻译为现代汉语如下：翻译为现代汉语如下：第一步，任意给定两个正整数，判断它们是否是偶数，第一步，任意给定两个正整数，判断它们是否是偶数，若是，用若是，用2 2约简；若不是，执行第二步约简；若不是，执行第二步.第二步，用两数中较大的数减去较小的数第二步，用两数中较大的数减去较小的数,再用再用 .和和 构成新的一对数构成新的一对数,再用大数减小数再用大数减小数,以同样的以同样的操作一直做下去操作一直做下去,直到产生直到产生为止为止,这个数这个数（等数）或这个数与约简的数的乘积就是最大公约数（等数）或这个数与约简的数的乘积就是最大公约数.2.2.古希腊求两个正整数的最大公约数的方法是古希腊求两个正整数的最大公约数的方法是:：用较大的数除以较小的数所得的：用较大的数除以较小的数所得的和和构成新的一对数构成新的一对数,继续做上面的除法继续做上面的除法,直到大数直到大数被小数除尽被小数除尽,这个较小的数就是最大公约数这个较小的数就是最大公约数.差数差数 较小的数较小的数 一对相等的数一对相等的数 辗转相除法辗转相除法 余数余数 较小的数较小的数 返回返回 2021/8/8 星期日33.3.把一个把一个n n次多项式次多项式f f(x x)=)=a an nx xn n a an nx xn na a1 1x x a a0 0改写成如下形式改写成如下形式:f f(x x)=)=a an nx xn na an nx xn na a1 1x xa a0 0=.=.=.求多项式的值时求多项式的值时,首先计算最内层括号内一次多项式首先计算最内层括号内一次多项式的值的值,即即v v1 1=,然后由内向外逐层计算一次然后由内向外逐层计算一次多项式的值多项式的值,即即v v2 2=,v v3 3=,v vn n=,(a an nx xn n-1-1a an nx xn n2 2a a1 1)x xa a0 0 (a an nx xn n-2-2a an nx xn n3 3+a a2 2)x xa a1 1)x xa a0 0 (（(a an nx xa an n)x x a an n2 2 )x xa a1 1)x xa a0 0 a an nx xa an nv v2 2x xa an n3 3v v1 1x xa an n2 2v vn n-1-1x xa a0 0返回返回 2021/8/8 星期日4这样这样,求求n n次多项式次多项式f f(x x)的值就转化为的值就转化为.上述方法称为秦九韶算法上述方法称为秦九韶算法.观察上述秦九韶算法中的观察上述秦九韶算法中的n n个一次式个一次式,可见可见vkvk的计算要的计算要用到用到v vk k-1-1的值的值.若令若令v v0 0=a an n,我们可以得到公式我们可以得到公式:.这是一个在秦九韶算法中反复执行的步骤这是一个在秦九韶算法中反复执行的步骤,因此可用因此可用 来实现来实现.求求n n个一次多项式的值个一次多项式的值 v vo o=a=an nv vk k=v=vk-k-1 1x+ax+an-kn-k(k=k=1,2,1,2,n n)循环结构循环结构 返回返回 2021/8/8 星期日5学点一学点一 辗转相除法辗转相除法用辗转相除法求用辗转相除法求9090与与3636的最大公约数的最大公约数.【分析】【分析】本题考查辗转相除法求两个数的最大公约本题考查辗转相除法求两个数的最大公约数的步骤数的步骤.使用辗转相除法求使用辗转相除法求9090与与3636的最大公约数时的最大公约数时,先先用用9090除以除以36,36,余数为余数为18,18,用用3636除以除以18,18,余数为余数为0,180,18就是就是9090与与3636的最大公约数的最大公约数.顺便提示一下顺便提示一下,两个数两个数a a,b b的最大公的最大公约数一般写成约数一般写成(a a,b b),),如如9090与与3636的最大公约数为的最大公约数为18,18,写成写成(90,36)=18.(90,36)=18.【解析】【解析】令令m m=90,=90,n n=36,=36,m m=2=2n n+18,+18,r r=18.=18.令令m m=36,=36,n n=18.=18.又有又有36=182,36=182,即即m m=2=2n n,返回返回 2021/8/8 星期日6此时此时r r=0.=0.令令m m=18,=18,n n=0.=0.故故9090与与3636的最大公约数为的最大公约数为18.18.程序步骤如下程序步骤如下:INPUTINPUTm m=;=;n n=;=;m m=90;=90;n n=36;=36;DODOr r=m m MOD MOD n nm m=n nn n=r rLOOPLOOPUNTILUNTILr r=0=0PRINTPRINT“90“90与与3636的最大公约数为的最大公约数为:”;:”;m mENDEND返回返回 2021/8/8 星期日7【评析】辗转相除法是当大数被小数除尽时【评析】辗转相除法是当大数被小数除尽时,结束结束除法运算除法运算,较小的数就是最大公约数较小的数就是最大公约数;更相减损术是当大更相减损术是当大数减去小数的差等于小数时停止减法数减去小数的差等于小数时停止减法,较小的数就是最较小的数就是最大公约数大公约数.返回返回 2021/8/8 星期日8用辗转相除法求用辗转相除法求8080与与3636的最大公约数的最大公约数,并用更相减损术检并用更相减损术检验所得结果验所得结果.解：解：用辗转相除用辗转相除:80=362+8,36=84+4,8=42+0;:80=362+8,36=84+4,8=42+0;用更相减损术检验用更相减损术检验:80-36=44,44-36=8,36-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.返回返回 2021/8/8 星期日9学点二学点二 更相减损术更相减损术1.1.有甲、乙、丙三种溶液有甲、乙、丙三种溶液,分别重分别重 kg,kg,kg.kg,kg,kg.先要将它们分别全部装入小瓶中先要将它们分别全部装入小瓶中,每个小瓶装入液体的重每个小瓶装入液体的重量相同量相同.问问:每瓶最多装多少每瓶最多装多少?【分析】【分析】本题考查更相减损术的计算步骤及思想本题考查更相减损术的计算步骤及思想.根根据题意据题意,每个小瓶装的溶液的质量应是三种溶液质量的最每个小瓶装的溶液的质量应是三种溶液质量的最大公约数大公约数.先求任意两个数的最大公约数先求任意两个数的最大公约数,然后再求这个数然后再求这个数与第三个数的最大公约数与第三个数的最大公约数.【解析】【解析】返回返回 2021/8/8 星期日10即和的最大公约数是即和的最大公约数是.即的最大公约数是即的最大公约数是 .【评析】本题考查更相减损术【评析】本题考查更相减损术.返回返回 2021/8/8 星期日112.2.用更相减损之术求用更相减损之术求9898和和6363的最大公约数的最大公约数.【分析】【分析】由于由于6363不是偶数不是偶数,把把9898和和6363以大数减小数以大数减小数,并并辗转相减辗转相减.【解析】【解析】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.【评析】等值算法是当大数减去小数的差等于小数时【评析】等值算法是当大数减去小数的差等于小数时停止减法停止减法,较小的数就是所求的最大公约数较小的数就是所求的最大公约数.返回返回 2021/8/8 星期日12有甲、乙、丙三种溶液分别重有甲、乙、丙三种溶液分别重147 kg,343 kg,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.所以所以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.返回返回 2021/8/8 星期日13学点三学点三 秦九韶算法秦九韶算法1.1.已知函数已知函数f f(x x)=)=x x4 4-2-2x x2 2-5-5x x+6,+6,用秦九韶算法求用秦九韶算法求f f(10)(10)的值的值.【分析】【分析】本题考查秦九韶算法求值的步骤本题考查秦九韶算法求值的步骤.根据秦九根据秦九韶算法韶算法,我们需要处理多项式的系数以及最高次项的系数我们需要处理多项式的系数以及最高次项的系数.该多项式函数没有中间的三次项该多项式函数没有中间的三次项,应先把多项式变形为应先把多项式变形为f f(x x)=)=x x4 4+0+0 x x3 3-2-2x x2 2-5-5x x+6+6再处理再处理.【解析】【解析】v v0 0=1,=1,v v1 1=110+0=10,=110+0=10,v v2 2=1010-2=98,=1010-2=98,v v3 3=9810-5=975,=9810-5=975,v v4 4=97510+6=9 756,=97510+6=9 756,f f(10)=9 756.(10)=9 756.返回返回 2021/8/8 星期日14【评析】当多项式函数中间出现空项要以系数为零的【评析】当多项式函数中间出现空项要以系数为零的齐次项补齐齐次项补齐.否则否则,在处理问题时在处理问题时,多项式运算的次数不会多项式运算的次数不会达到对应的次数达到对应的次数.因此因此,我们在应用秦九韶算法求多项式的我们在应用秦九韶算法求多项式的值时值时,先要依次从最高次项往常数项观察各项是否都存在先要依次从最高次项往常数项观察各项是否都存在,再进行处理再进行处理.返回返回 2021/8/8 星期日152.2.求多项式求多项式f f(x x)=)=x x5 5+5+5x x4 4+10+10 x x3 3+10+10 x x2 2+5+5x x+1+1当当x x=-2=-2时的值时的值.【解析】【解析】解：解：先改写多项式先改写多项式,再由内向外计算再由内向外计算.f f(x x)=)=x x5 5+5+5x x4 4+10+10 x x3 3+10+10 x x2 2+5+5x x+1+1=(=(x x+5)+5)x x+10)+10)x x+10)+10)x x+5)+5)x x+1.+1.而而x x=-2,=-2,所以有所以有:v v0 0=1,=1,v v1 1=v v0 0 x x+a a4 4=1(-2)+5=3,=1(-2)+5=3,v v2 2=v vx x+a a3 3=3(-2)+10=4,=3(-2)+10=4,v v3 3=v v2 2x x+a a2 2=4(-2)+10=2,=4(-2)+10=2,v v4 4=v v3 3x x+a a1 1=2(-2)+5=1,=2(-2)+5=1,v v5 5=v v4 4x x+a a0 0=1(-2)+1=-1.=1(-2)+1=-1.所以当所以当x x=-2=-2时，多项式的值为时，多项式的值为-1.-1.返回返回【分析】【分析】本题考查秦九韶算法本题考查秦九韶算法.2021/8/8 星期日16 【评析】利用秦九韶算法计算多项式的值关键是能正【评析】利用秦九韶算法计算多项式的值关键是能正确地将所给多项式改写确地将所给多项式改写,然后由内向外逐次计算然后由内向外逐次计算,由于后项由于后项计算需用到前项的结果计算需用到前项的结果,故应认真、细心故应认真、细心,确保中间结果的确保中间结果的准确性准确性.返回返回 2021/8/8 星期日17已知一个已知一个5 5次多项式为次多项式为:f f(x x)=5)=5x x5 5+2+2x x4 4+3.5+3.5x x3 3-2.6-2.6x x2 2+1.7+1.7x x-0.8,0.8,用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x x=5=5时的值时的值.解：解：f f(x x)=(5)=(5x x+2)+2)x x+3.5)+3.5)x x-2.6)-2.6)x x+1.7)+1.7)x x-0.8,-0.8,当当x x=5=5时时,v v0 0=5;=5;v v1 1=55+2=27;=55+2=27;v v2 2=275+3.5=138.5;=275+3.5=138.5;v v3 3=138.55-2.6=689.9;=138.55-2.6=689.9;v v4 4=689.95+1.7=3 451.2;=689.95+1.7=3 451.2;v v5 5=3 451.25-0.8=17 255.2.=3 451.25-0.8=17 255.2.所以当所以当x x=5=5时时,多项式的值为多项式的值为17 255.2.17 255.2.返回返回 2021/8/8 星期日18学点四学点四 进位制进位制将将8 8进制数进制数314 706314 706(8)(8)转化为十进制数转化为十进制数.【分析】【分析】本题考查进位制的换算步骤及注意事项本题考查进位制的换算步骤及注意事项.利利用把用把k k进制数转化为十进制数的一般方法就可以把进制数转化为十进制数的一般方法就可以把8 8进制数进制数314 706314 706(8)(8)化为十进制数化为十进制数.【解析】【解析】314 706314 706(8)(8)=38=385 5+18+184 4+48+483 3+78+782 2+0+08 81 1+68+680 0=104 902.=104 902.所以所以314 706314 706(8)(8)化为十进制数是化为十进制数是104 902.104 902.8 8进制数进制数314 706314 706中共有中共有6 6位位,因此可令因此可令a a=314 706,=314 706,k k=8,=8,n n=6.=6.【评析】本题考查进位制【评析】本题考查进位制.返回返回 2021/8/8 星期日19将将389389化成四进制数的末位是化成四进制数的末位是.1(1(,末位是第一个余数末位是第一个余数,389=12 011,389=12 011(4)(4).注意注意:余数自下而上排列余数自下而上排列.).)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第一个余数第一个余数返回返回 2021/8/8 星期日201.1.如何理解辗转相除法如何理解辗转相除法?辗转相除法是西方古代数学中的一个典型算法辗转相除法是西方古代数学中的一个典型算法.更相更相减损术和秦九韶算法都是我国古代数学中的著名算法减损术和秦九韶算法都是我国古代数学中的著名算法,而而排序法和进位制算法是计算机科学中普遍使用的算法排序法和进位制算法是计算机科学中普遍使用的算法.这这些算法案例不仅蕴涵着深刻的算法思想些算法案例不仅蕴涵着深刻的算法思想,而且也更能体现而且也更能体现出算法的重要性和有效性出算法的重要性和有效性.因此因此,要切实理解算法案例的内要切实理解算法案例的内容及具体算法的关键步骤容及具体算法的关键步骤.返回返回 2021/8/8 星期日212.2.如何掌握进位制如何掌握进位制?进位制是一种记数方式进位制是一种记数方式,用有限的数字在不同的位置用有限的数字在不同的位置表示不同的数值表示不同的数值.可使用数字符号的个数称为基数可使用数字符号的个数称为基数,基数为基数为n n,即可称即可称n n进位制进位制,简称简称n n进制进制.现在最常用的是十进制现在最常用的是十进制,通通常使用常使用1010个阿拉伯数字个阿拉伯数字0 0 9 9进行记数进行记数.对于任何一个数对于任何一个数,我们可以用不同的进位制来表示我们可以用不同的进位制来表示.比比如如:十进数十进数57,57,可以用二进制表示为可以用二进制表示为111001,111001,也可以用八进也可以用八进制表示为制表示为71,71,用十六进制表示为用十六进制表示为39,39,它们所代表的数值都是它们所代表的数值都是一样的一样的.表示各种进制数一般在数字右下角加注来表示表示各种进制数一般在数字右下角加注来表示.如如111001111001(2)(2)表示二进制数表示二进制数,34,34(5)(5)表示表示5 5进制数进制数.电子计算机一电子计算机一般都使用二进制般都使用二进制.返回返回 2021/8/8 星期日221.1.理解辗转相除法与更相减损术求最大公约数的方法理解辗转相除法与更相减损术求最大公约数的方法;理解秦九韶算法的特点理解秦九韶算法的特点;理解两种排序法的排序步骤及计理解两种排序法的排序步骤及计算机程序设计算机程序设计,各进位制表示数的方法及各进位制之间的各进位制表示数的方法及各进位制之间的转换转换.2.2.把辗转相除法与更相减损术的方法转换成程序框图把辗转相除法与更相减损术的方法转换成程序框图与程序语言与程序语言;秦九韶算法的先进性理解秦九韶算法的先进性理解;除除k k去余法的理解去余法的理解以及各进位制之间转换的程序框图的设计以及各进位制之间转换的程序框图的设计.返回返回 2021/8/8 星期日23祝同学们学习上天天有进步！2021/8/8 星期日242021/8/8 星期日25
