1、学案513 算法案例1.3算法案例知识一辗转相除法与更相减损术提出问题问题1:如何求18与54的最大公约数?问题2:要求6 750与3 492的最大公约数,上述法还好用吗?问题3:还有没有其他方法,可用来解决问题2中的问题?导入新知1辗转相除法(1)辗转相除法,又叫欧几里得算法,是一种求两个正整数的最大公约数的古老而有效的算法(2)辗转相除法的算法步骤:第一步,给定两个正整数m,n.第二步,计算m除以n所得的余数r.第三步,mn,nr.第四步,若r0,则m,n的最大公约数等于m;否则返回第二步2更相减损术(1)更相减损术是我国古代数学专著九章算术中介绍的一种求两个正整数的最大公约数的算法(2)
2、其基本过程是:第一步,任意给定两个正整数,判断它们是否都是偶数若是,用2约简;若不是,执行第二步第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减小数,继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数化解疑难辗转相除法与更相减损术的比较两种方法辗转相除法更相减损术计算法则除法减法终止条件余数为0减数与差相等最大公约数的选取最后一步中的除数最后一步中的减数计算次数步骤较少,运算复杂步骤较多,运算简单相同点同为求两个正整数最大公约数的方法,都是递归过程知识点二秦九韶算法提出问题已知多项式f(x)x53x43x34x2x1.问题1
3、:提示:f(1)1334113.问题2:若求f(39),再代入运算出现什么情况?问题3:当x的值较大时,有没有更好的方法求函数值呢?导入新知秦九韶算法的算法原理把一个n次多项式f(x)anxnan1xn1a1xa0改写成如下形式:f(x)anxnan1xn1a1xa0(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1)xa0(anxan1)xan2)xa1)xa0.求多项式的值时,首先计算最内层括号内一次多项式的值,即v1anxan1,然后由内向外逐层计算一次多项式的值,即v2v1xan2,v3v2xan3,vnvn1xa0,这样,求n次多项式f(x)的值就转化为求n个一
4、次多项式的值化解疑难秦九韶算法的步骤知识点三进位制提出问题问题1:今天是星期二,那么20天后是星期几?问题2:每周七天,逢七便又是一循环,这与我们所学过的十进制,逢十进一是否有相似之处?导入新知1进位制(1)概念:进位制是为了计数和运算方便而约定的记数系统,“满几进一”就是几进制(2)基数:几进制的基数就是几2不同进位制之间的互化(1)k进制化为十进制的方法:anan1a1a0(k)anknan1kn1a1ka0(an,an1,a1,a0N,0ank,0an1,a1,a0k)(2)十进制化为k进制的方法除k取余数化解疑难常见的进位制(1)二进制:只使用0和1两个数字;满二进一,如1110.(2
5、)八进制:使用0,1,2,3,4,5,6,7八个不同的数字;满八进一,如7110.(3)十六进制:使用0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F这十六个不同的数码,其中A,B,C,D,E,F分别代表十进制中的10,11,12,13,14,15;满十六进一,如F12E10.题型一求最大公约数例1分别用辗转相除法和更相减损术求779与209的最大公约数类题通法1用辗转相除法求最大公约数的步骤2用更相减损术求最大公约数的步骤第一步,给定两个正整数m,n(mn且m,n不全是偶数)第二步,计算mn所得的差k.第三步,比较n与k的大小,其中大者用m表示,小者用n表示第四步,若mn,则m
6、,n的最大公约数等于m;否则,返回第二步活学活用用辗转相除法和更相减损术求1515与600的最大公约数,需要运算的次数分别为()A4,15 B5,14C5,13 D4,12题型二秦九韶算法及其应用例2(1)已知f(x)x52x33x2x1,应用秦九韶算法计算当x3时,v3的值为()A27 B11C109 D36(2)用秦九韶算法求多项式f(x)6x65x54x43x32x2x,当x2时的值类题通法秦九韶算法原理及注意事项(1)秦九韶算法的原理是(k1,2,n)(2)在运用秦九韶算法进行计算时,应注意每一步的运算结果,像这种一环扣一环的运算,如果错一步,那么下一步,一直到最后一步就会全部算错,同
7、学们在计算这种题时应格外小心活学活用用秦九韶算法计算多项式f(x)3x64x55x46x37x28x1当x0.4时的值时,需要做乘法和加法的次数分别是()A6,6 B5, 6C5,5 D6,5题型三进位制例3(1)将101 111 011(2)转化为十进制的数;(2)将235(7)转化为十进制的数;(3)将137(10)转化为六进制的数;(4)将53(8)转化为二进制的数类题通法1k进制数化为十进制数的步骤(1)把k进制数写成不同数位上的数字与k的幂的乘积之和的形式(2)按十进制数的运算规则运算出结果2十进制数化为k进制数(除k取余法)的步骤活学活用若六进制数13m502(6)化为十进制数等于
8、12 710,求数字m的值典例利用秦九韶算法求f(x)x5x3x2x1当x3时的值()A121 B283C321 D239成功破障用秦九韶算法求多项式f(x)x50.11x30.15x0.04当x0.3时的值随堂即时演练1在对16和12求最大公约数时,整个操作如下:16124,1248,844.由此可以看出12和16的最大公约数是()A4 B12C16 D82用秦九韶算法求多项式f(x)12xx23x32x4在x1时的值,v2的结果是()A4 B1C5 D63将51化为二进制数得_4用辗转相除法求294和84的最大公约数时,需要做除法的次数是_5将1 234(5)转化为八进制数参考答案知识一问
9、题1:提示:短除法问题2:提示:数值太大,短除法不方便用问题3:提示:有知识二问题1:求f(1)问题2:提示:运算量太大,不易运算问题3:提示:有可将f(x)转化为求一次多项式的值知识三问题1:提示:20天后是星期一问题2:提示:其实一周七天,与十进制一样,相当于逢七进一,是七进制论法例1解:(1)辗转相除法:7792093152,209152157,15257238,5738119,38192.所以,779与209的最大公约数为19.(2)更相减损术:779209570,1525795,570209361, 955738,361209152, 573819,20915257, 381919.
10、所以779和209的最大公约数为19. 活学活用【解析】选B辗转相除法:15156002315;6003151285,315285130,28530915,30152故最大公约数为15,且需计算5次用更相减损术法:1515600915,915600315,600315285,31528530,28530255,25530225,22530195,19530165,16530135,13530105,1053075,753045,453015,301515.故最大公约数为15,且需计算14次.【答案】B例2 (1)【解析】将多项式改写成如下形式:f(x)(x0)x2)x3)x1)x1,由内向外依
11、次计算:v01,v11303,v233211,v3113336.【答案】D (2) 解:f(x)(6x5)x4)x3)x2)x1)x,当x2时,有v06,v162517,v2172438,v3382379,v47922160,v516021321,v63212642,故当x2时,多项式f(x)6x65x54x43x32x2x的值为642.活学活用【解析】选Af(x)(3x4)x5)x6)x7)x8)x1,所以需要进行6次乘法和6次加法.【答案】A例3 解:(1)101 111 011(2)128027126125124123022121120379(10)(2)235(7)2723715701
12、24(10)(3)137(10)345(6)(4)53(8)58138043(10)53(8)101 011(2)活学活用解:因为13m502(6)165364m63562061260216m11 846,令216m11 84612 710,所以m4.典例【解析】原多项式可化为:f(x)(x0)x1)x1)x1)x1当x3时v01,v11303,v233110,v3103131,v4313194,v59431283.所以,当x3时f(3)283.【答案】B易错防范当多项式中间出现空项时,用秦九韶算法求函数值要补上系数为0的相应项,否则,本题极易出现如下所示的错误算法,从而误选A.f(x)(x1
13、)x1)x1)x1,当x3时,v01,v1314,v243113,v3133140,v440311201121,所以当x3时,f(3)121. 成功破障解:根据秦九韶算法,将f(x)写为:f(x)(x0)x0.11)x0)x0.15)x0.04.按照从内到外的顺序,依次计算一次多项式当x0.3时的值;v01v1v00.300.3;v2v10.30.110.2;v3v20.300.06;v4v30.30.150.132;v5v40.30.040.079 6.所以,当x0.3时,多项式的值为0.079 6.1.【解析】选A根据更相减损术的方法判断【答案】A2.【解析】选Dn4,a42,a33, a21,a12,a01,由秦九韶算法的递推关系式得v02,v1v0xa35,v2v1xa26.【答案】D3.【解析】【答案】110 011(2)4.【解析】29484342,84422.【答案】25.解:将1 234(5)转化为十进制数:1 234(5)153252351450194.再将十进制数194转化为八进制数:所以1 234(5)302(8)