2020-2021学年1.3 算法与案例说课ppt课件

这是一份2020-2021学年1.3 算法与案例说课ppt课件
学点一学点二学点三学点四　　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＋a0 anx＋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.　　程序步骤如下:　　INPUT　m=;n=;　　m=90;n=36;　　DO　　r=m MOD n　　m=n　　n=r　　LOOP　UNTIL　r=0　　PRINT　“90与36的最大公约数为:”;m　　END　　【评析】辗转相除法是当大数被小数除尽时,结束除法运算,较小的数就是最大公约数;更相减损术是当大数减去小数的差等于小数时停止减法,较小的数就是最大公约数.用辗转相除法求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.先要将它们分别全部装入小瓶中,每个小瓶装入液体的重量相同.问:每瓶最多装多少?　　【分析】本题考查更相减损术的计算步骤及思想.根据题意,每个小瓶装的溶液的质量应是三种溶液质量的最大公约数.先求任意两个数的最大公约数,然后再求这个数与第三个数的最大公约数.　　【解析】　　即　　和　　的最大公约数是　　.　　即　　　　　　的最大公约数是 .　　【评析】本题考查更相减损术.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.　　【评析】等值算法是当大数减去小数的差等于小数时停止减法,较小的数就是所求的最大公约数.有甲、乙、丙三种溶液分别重147 kg,343 kg,133 kg,现要将它们分别全部装入小瓶中,每个小瓶装入液体的质量相同,问每瓶最多装多少? 解：由题意,每小瓶装的溶液的质量应是三种溶液质量的最大公约数,先求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. 故每瓶最多装7 kg.学点三 秦九韶算法1.已知函数f(x)=x4-2x2-5x+6,用秦九韶算法求f(10)的值.　　【分析】本题考查秦九韶算法求值的步骤.根据秦九韶算法,我们需要处理多项式的系数以及最高次项的系数.该多项式函数没有中间的三次项,应先把多项式变形为f(x)=x4+0×x3-2x2-5x+6再处理.　　【解析】v0=1, v1=1×10+0=10,　　 v2=10×10-2=98, 　　v3=98×10-5=975, 　　v4=975×10+6=9 756,　　 ∴f(10)=9 756.　　【评析】当多项式函数中间出现空项要以系数为零的齐次项补齐.否则,在处理问题时,多项式运算的次数不会达到对应的次数.因此,我们在应用秦九韶算法求多项式的值时,先要依次从最高次项往常数项观察各项是否都存在,再进行处理.2.求多项式f(x)=x5+5x4+10x3+10x2+5x+1当x=-2时的值.　【解析】解：先改写多项式,再由内向外计算.　　 f(x)=x5+5x4+10x3+10x2+5x+1　　=((((x+5)x+10)x+10)x+5)x+1.　　而x=-2,所以有:　　v0=1,v1=v0x+a4=1×(-2)+5=3,　　v2=v１x+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=5×5+2=27; v2=27×5+3.5=138.5; v3=138.5×5-2.6=689.9; v4=689.9×5+1.7=3 451.2; v5=3 451.2×5-0.8=17 255.2. 所以当x=5时,多项式的值为17 255.2.学点四 进位制将8进制数314 706(8)转化为十进制数.　　【分析】本题考查进位制的换算步骤及注意事项.利用把k进制数转化为十进制数的一般方法就可以把8进制数314 706(8)化为十进制数.　　【解析】314 706(8)=3×85+1×84+4×83+7×82+0×81+6×80=104 902.　　所以314 706(8)化为十进制数是104 902.　　8进制数314 706中共有6位,因此可令a=314 706,k=8,n=6.　　【评析】本题考查进位制.将389化成四进制数的末位是　　　　　　　.　　1( ,末位是第一个余数,389=12 011(4).注意:余数自下而上排列.)4 389 余4 97 14 24 14 6 04 1 2 0 1第一个余数1.如何理解辗转相除法? 辗转相除法是西方古代数学中的一个典型算法.更相减损术和秦九韶算法都是我国古代数学中的著名算法,而排序法和进位制算法是计算机科学中普遍使用的算法.这些算法案例不仅蕴涵着深刻的算法思想,而且也更能体现出算法的重要性和有效性.因此,要切实理解算法案例的内容及具体算法的关键步骤.2.如何掌握进位制? 进位制是一种记数方式,用有限的数字在不同的位置表示不同的数值.可使用数字符号的个数称为基数,基数为n,即可称n进位制,简称n进制.现在最常用的是十进制,通常使用10个阿拉伯数字0~9进行记数. 对于任何一个数,我们可以用不同的进位制来表示.比如:十进数57,可以用二进制表示为111001,也可以用八进制表示为71,用十六进制表示为39,它们所代表的数值都是一样的. 表示各种进制数一般在数字右下角加注来表示.如111001(2)表示二进制数,34(5)表示5进制数.电子计算机一般都使用二进制.　　1.理解辗转相除法与更相减损术求最大公约数的方法;理解秦九韶算法的特点;理解两种排序法的排序步骤及计算机程序设计,各进位制表示数的方法及各进位制之间的转换.　　2.把辗转相除法与更相减损术的方法转换成程序框图与程序语言;秦九韶算法的先进性理解;除k去余法的理解以及各进位制之间转换的程序框图的设计.祝同学们学习上天天有进步！