《高中人a数学必修三-第一章学案六算法案例》由会员分享，可在线阅读，更多相关《高中人a数学必修三-第一章学案六算法案例（24页珍藏版）》请在金锄头文库上搜索。
1、学点一,学点二,学点三,学点四,1.九章算术中的“更相减损术”求两个数的最大公约数.翻译为现代汉语如下： 第一步，任意给定两个正整数，判断它们是否是偶数，若是，用2约简；若不是，执行第二步. 第二步，用两数中较大的数减去较小的数,再用 .和 构成新的一对数,再用大数减小数,以同样的操作一直做下去,直到产生 为止,这个数（等数）或这个数与约简的数的乘积就是最大公约数. 2.古希腊求两个正整数的最大公约数的方法是: ：用较大的数除以较小的数所得的 和 构成新的一对数,继续做上面的除法,直到大数被小数除尽,这个较小的数就是最大公约数.,差数,较小的数,一对相等的数,辗转相除法,余数,较小的数,3.把
2、一个n次多项式f(x)=anxn anxna1x a0改写成如下形式: f(x)= anxnanxna1xa0 = . = . = = . 求多项式的值时,首先计算最内层括号内一次多项式的值,即v1= ,然后由内向外逐层计算一次多项式的值,即 v2= , v3= , vn= ,(anxn-1anxn2a1)xa0,(anxn-2anxn3+a2)xa1)xa0,(（(anxan)x an2 )xa1)xa0,anxan,v2xan3,v1xan2,vn-1xa0,这样,求n次多项式f(x)的值就转化为 . 上述方法称为秦九韶算法. 观察上述秦九韶算法中的n个一次式,可见vk的计算要用到vk-1
3、的值.若令v0=an,我们可以得到公式: . 这是一个在秦九韶算法中反复执行的步骤,因此可用 来实现.,求n个一次多项式的值,vo=an vk=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
4、,r=18. 令m=36,n=18. 又有36=182,即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=362+8,36=84+4
5、,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
6、.用更相减损之术求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=19
7、6, 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+0x3-2
8、x2-5x+6再处理. 【解析】v0=1, v1=110+0=10, v2=1010-2=98, v3=9810-5=975, v4=97510+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)
9、x+10)x+10)x+5)x+1. 而x=-2,所以有: v0=1,v1=v0x+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
10、,用秦九韶算法求这个多项式当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=3 451.2; v5=3 451.25-0.8=17 255.2. 所以当x=5时,多项式的值为17 255.2.,学点四 进位制,将8进制数314 706(8)转化为十进制数. 【分析】本题考查进位制的换算步骤及注意事项.利用把k进制数转化为十进制数的一般方法就可以把8进制数314 706(8)化为十进制数. 【解析
11、】314 706(8)=385+184+483+782+0 81+680=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 1 4 24 1 4 6 0 4 1 2 0 1,第一个余数,1.如何理解辗转相除法? 辗转相除法是西方古代数学中的一个典型算法.更相减损术和秦九韶算法都是我国古代数学中的著名算法,而排序法和进位制算
12、法是计算机科学中普遍使用的算法.这些算法案例不仅蕴涵着深刻的算法思想,而且也更能体现出算法的重要性和有效性.因此,要切实理解算法案例的内容及具体算法的关键步骤.,2.如何掌握进位制? 进位制是一种记数方式,用有限的数字在不同的位置表示不同的数值.可使用数字符号的个数称为基数,基数为n,即可称n进位制,简称n进制.现在最常用的是十进制,通常使用10个阿拉伯数字09进行记数. 对于任何一个数,我们可以用不同的进位制来表示.比如:十进数57,可以用二进制表示为111001,也可以用八进制表示为71,用十六进制表示为39,它们所代表的数值都是一样的. 表示各种进制数一般在数字右下角加注来表示.如111001(2)表示二进制数,34(5)表示5进制数.电子计算机一般都使用二进制.,1.理解辗转相除法与更相减损术求最大公约数的方法;理解秦九韶算法的特点;理解两种排序法的排序步骤及计算机程序设计,各进位制表示数的方法及各进位制之间的转换. 2.把辗转相除法与更相减损术的方法转换成程序框图与程序语言;秦九韶算法的先进性理解;除k去余法的理解以及各进位制之间转换的程序框图的设计.,祝同学们学习上天天有进步！,
