资源描述
成才之路 数学,路漫漫其修远兮 吾将上下而求索,人教A版 必修3,算法初步,第一章,1.3 算法案例,第一章,第1课时 辗转相除法与更相减损术、秦九韶算法,鸡兔同笼问题是中国古代数学名著孙子算法中的一道名题，题目是这样的：“今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？”书中给出的解法是：鸡有两只脚，兔有四只脚，把脚数除以2，共有47对脚由于鸡有1对脚，兔有2对脚，所以从47中减去25，得12即为兔子数因为如要笼子里的动物每只都只有1对脚，就会多出12对脚来，把这12对脚分别加到有2对脚的动物身上，就有12只脚动物，即兔子数整个解题过程可以简单地写作：,知识衔接,1辗转相除法与更相减损术 (1)辗转相除法 算法步骤： 第一步，给定两个正整数m，n. 第二步，计算m除以n所得的余数r. 第三步，mn，nr. 第四步，若r_，则m，n的最大公约数等于m；否则返回 第_步,自主预习,0,二,程序框图如图所示,程序： INPUT m，n DO rm MOD n mn nr LOOP UNTIL _ PRINT _ END,r0,m,(2)更相减损术 算法步骤： 第一步，任意给定两个正整数，判断它们是否都是_若是，用_约简；若不是，执行第二步 第二步，以较大的数_去较小的数，接着把所得的差与较小的数比较，并以_数减_数继续这个操作，直到所得的差与减数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数,偶数,2,减,大,小,2秦九韶算法 (1)概念：求多项式f(x)anxnan1xn1a1xa0的值时，常用秦九韶算法，这种算法的运算次数较少，是多项式求值比较先进的算法，其实质是转化为求n个_多项式的值，共进行_次乘法运算和_次加法运算其过程是： 改写多项式为： f(x)anxnan1xn1a1xa0 (anxn1an1xn2a1)xa0 (anxn2an1xn3a2)xa1)xa0 (anxan1)xan2)xa1)xa0. 设v1_，,一次,n,n,anxan1,v2v1xan2， v3v2xan3， ， vn_.,vn1xa0,(2)算法步骤： 第一步，输入多项式的次数n、最高次项的系数an和x的值 第二步，将v的值初始化为an，将i的值初始化为n1. 第三步，输入i次项的系数ai. 第四步，vvxai，i_. 第五步，判断i是否大于或等于_.若是，则返回第三步；否则，输出多项式的值_.,i1,0,v,(3)程序框图如图所示,(4)程序： INPUT “n”；n INPUT “an”；a INPUT “x”；x va in1 WHILE _ PRINT “i”；i INPUT “ai”；a,i0,v_ ii1 WEND PRINT _ END,v*xa,v,1用辗转相除法求36与134的最大公约数，第一步是( ) A1343698 B13436326 C先除以2，得到18与67 D3626110 答案 B 解析 求36与134的最大公约数，第一步是13436326，第二步是3626110，故选D.,预习自测,2(2015河北省廊坊一中月考)用辗转相除法求294和84的最大公约数时，需要做除法的次数是( ) A1 B2 C3 D4 答案 B 解析 本题考查辗转相除法的过程.29484342,84422，故选B.,3设计程序框图，用秦九韶算法求多项式的值，所选用的结构是( ) A顺序结构 B条件结构 C循环结构 D以上都有 答案 D 4用更相减损术求294和84的最大公约数时，第一步是_ 答案 用2约简 解析 由于294和84都是偶数，先用2约简,5(2015云南省景洪一中月考)用秦九韶算法计算多项式f(x)3x62x54x45x37x28x1在x0.5时的值，需做乘法和加法的次数分别是_ 答案 6次乘法，6次加法 解析 将多项式改写为f(x)(3x2)x4)x5)x7)x8)x1，化为6个一次因式求解，故只做了6次乘法和6次加法,用辗转相除法求80和36的最大公约数，并用更相减损术检验所得结果 探究 1.辗转相除法与更相减损术的主要区别是什么？ 2将80作为大数，36作为小数，执行辗转相除法和更相减损术的步骤即可,辗转相除法和更相减损术的应用,互动探究,解析 用辗转相除法： 803628， 36844， 8420. 故80和36的最大公约数是4.,用更相减损术检验： 803644， 44368， 36828， 28820， 20812， 1284， 844. 故80和36的最大公约数是4.,规律总结 更相减损术与辗转相除法都能求两个数的最大公约数，二者的区别与联系如下表.,(1)用辗转相除法求288与123的最大公约数 (2)用更相减损术求57与93的最大公约数 (3)求567与405的最小公倍数 解析 (1)288123242,12342239， 423913,39313， 288和123的最大公约数是3. (2)(93,57)(36,57)(36,21)(15,21)(15,6)(9,6)(3,6)(3,3)， 93与57的最大公约数是3.,(3)5674051162 405162281 1628120 81是567与405的最大公约数，从而567与405的最小公倍数为567405812835.,(1)(2015三明高一检测)用秦九韶算法计算多项式f(x)3x64x55x46x37x28x1，当x0.4时的值时，需要做乘法和加法的次数分别是( ) A6,6 B5,6 C5,5 D6,5 (2)已知一个五次多项式f(x)2x54x33x25x1，用秦九韶算法求这个多项式当x3是的值,用秦九韶算法求多项式的值,探究 1.用秦九韶算法求多项式的值时，几次多项式就做几次乘法运算，对吗？ 2用秦九韶算法求多项式f(x)anxnan1xn1a1xa0在xx0时的值时，v0是什么？v1呢？ 解析 (1)将多项式改写成如下形式f(x)(3x4)x5)x6)x7)x8)x1，显然，把x0.4代入计算其值时，共做了6次乘法，6次加法,(2)因为f(x)(2x0)x4)x3)x5)x1， v02， v12306， v263414， v3143345， v44535130， v513031391， 所以f(3)391. 答案 (1)A (2)391,规律总结 用秦九韶算法时要正确将多项式的形式进行改写，然后由内向外依次计算当多项式函数中间出现空项时，要以系数为零的齐次项补充,用秦九韶算法求多项式f(x)7x76x65x54x43x32x2x当x3时的值 探究 解决本题首先需要将原多项式化成f(x)(7x6)x5)x4)x3)x2)x1)x的形式，其次再弄清v0，v1，v2，v7分别是多少，再针对这些式子进行计算,解析 f(x)(7x6)x5)x4)x3)x2)x1)x，所以有 v07； v173627； v2273586； v38634262； v426233789； v5789322369； v62369317108； v77108321324. 故当x3时，多项式f(x)7x76x65x54x43x32x2x的值为21324.,试用辗转相除法求325、130、270的最大公约数 探究 应用辗转相除法去除，即依据mnqr反复执行，直到r0为止,求多个数的最大公约数,探索延拓,解析 325130265,130652， 325与130的最大公约数是65. 27065410,651065,10652， 65与270的最大公约数是5， 故325、130、270三个数的最大公约数为5. 规律总结 理解辗转相除法的实质，从计算结果上看，辗转相除法是以相除余数为零而得到结果的,求三个数175,100,75的最大公约数 探究 求三个数的最大公约数时，可以先求出其中两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，所得的结果就是这三个数的最大公约数,解析 先求175与100的最大公约数： 175100175,10075125， 75253， 175与100的最大公约数是25. 再求25与75的最大公约数： 752550,502525， 75和25的最大公约数是25. 175,100,75的最大公约数是25. 点评 本题的解法可以推广到求多个数的最大公约数，只需依次计算即可,已知f(x)3x42x24x2，利用秦九韶算法求f(2)的值 错解 f(x)(3x22)x4)x2， v13(2)2214； v214(2)424； v324(2)250. 故f(2)50. 错因分析 所求f(2)的值是正确的，但是错解中没有抓住秦九韶算法原理的关键，正确改写多项式，并使每一次计算只含有一次项,误区警示,正解 f(x)3x40x32x24x2(3x0)x2)x4)x2， v03， v13(2)06； v26(2)214； v314(2)424； v424(2)250. 故f(2)50.,(2015贵阳高一检测)用秦九韶算法计算多项式f(x)1235x8x279x36x45x53x6在x4的值时，v3的值为_ 答案 57,解析 多项式变形为f(x)3x65x56x479x38x235x12(3x5)x6)x79)x8)x35)x12， 当x4时， v03， v13(4)57， v27(4)634， v334(4)7957， v457(4)8220， v5220(4)35845， v6845(4)123392.,1下列有关辗转相除法的说法正确的是( ) A它和更相减损术一样是求多项式值的一种方法 B基本步骤是用较大的数m除以较小的数n得到除式mnqr，直至rn为止 C基本步骤是用较大的数m除以较小的数n得到除式mqnr(0rn)反复进行，直到r0为止 D以上说法均不正确 答案 C,2更相减损术的理论依据是( ) A每次操作所得的两数和前两数具有相同的最小公倍数 B每次操作所得的两数和前两数具有相同的最大公约数 C每次操作所得的两数和前两数的最小公倍数不同 D每次操作所得的两数和前两数的最大公约数不同 答案 B,3用更相减损术求123与51的最大公约数时，需做减法的次数是( ) A3 B5 C6 D8 答案 D,解析 1235172， 725121， 512130， 30219， 21912， 1293， 936， 633， 所以共做了8次减法,4(2015山西省太原五中月考)用秦九韶算法求多项式f(x)7x66x53x22当x4时的值时，先算的是( ) A4416 B7428 C44464 D74634 答案 D 解析 本题考查秦九韶算法的计算原理因为f(x)anxnan1xn1a1xa0(anxan1)xan2)xa1)xa0，所以用秦九韶算法求多项式f(x)7x66x53x22当x4时的值时，先算的是74634，故选D.,5分别用辗转相除法和更相减损术求357和105的最大公约数，并求最小公倍数 解析 辗转相除法：357105342,10542221,42212. 故105与357的最大公约数为21. 更相减损术：357105252,252105147,14710542,1054263， 634221,422121. 故105与357的最大公约数为21.最小公倍数为105357211785.,
展开阅读全文