《高中数学 1.3第1课时辗转相除法与更相减损术、秦九韶算法课件 新人教A版必修3.ppt》由会员分享，可在线阅读，更多相关《高中数学 1.3第1课时辗转相除法与更相减损术、秦九韶算法课件 新人教A版必修3.ppt（49页珍藏版）》请在金锄头文库上搜索。
1、成才之路成才之路 数学数学路漫漫其修远兮路漫漫其修远兮 吾将上下而求索吾将上下而求索人教人教A版版 必修必修3 算法初步算法初步第一章第一章1.3算法案例算法案例第一章第一章第第1课时辗转相除法与更相减损术、课时辗转相除法与更相减损术、秦九韶算法秦九韶算法高高 效效 课课 堂堂2课课 时时 作作 业业4优优 效效 预预 习习1当当 堂堂 检检 测测3优优 效效 预预 习习鸡兔同笼问题是中国古代数学名著孙子算法中的一道名题，题目是这样的：“今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？”书中给出的解法是：鸡有两只脚，兔有四只脚，把脚数除以2，共有47对脚由于鸡有1对脚，兔有2对脚，所以
2、从47中减去25，得12即为兔子数因为如要笼子里的动物每只都只有1对脚，就会多出12对脚来，把这12对脚分别加到有2对脚的动物身上，就有12只脚动物，即兔子数整个解题过程可以简单地写作：知识衔接知识衔接1辗转相除法与更相减损术(1)辗转相除法算法步骤：第一步，给定两个正整数m，n.第二步，计算m除以n所得的余数r.第三步，mn，nr.第四步，若r_，则m，n的最大公约数等于m；否则返回 第_步自主预习自主预习0二程序框图如图所示程序：INPUTm，nDOrmMODnmnnrLOOP UNTIL _PRINT_ENDr0m(2)更相减损术算法步骤：第一步，任意给定两个正整数，判断它们是否都是_若
3、是，用_约简；若不是，执行第二步第二步，以较大的数_去较小的数，接着把所得的差与较小的数比较，并以_数减_数继续这个操作，直到所得的差与减数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数偶数 2减大小2秦九韶算法(1)概念：求多项式f(x)anxnan1xn1a1xa0的值时，常用秦九韶算法，这种算法的运算次数较少，是多项式求值比较先进的算法，其实质是转化为求n个_多项式的值，共进行_次乘法运算和_次加法运算其过程是：改写多项式为：f(x)anxnan1xn1a1xa0(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1)xa0(anxan1)xan
4、2)xa1)xa0.设v1_，一次nnanxan1v2v1xan2，v3v2xan3，vn_.vn1xa0(2)算法步骤：第一步，输入多项式的次数n、最高次项的系数an和x的值第二步，将v的值初始化为an，将i的值初始化为n1.第三步，输入i次项的系数ai.第四步，vvxai，i_.第五步，判断i是否大于或等于_.若是，则返回第三步；否则，输出多项式的值_.i10v(3)程序框图如图所示(4)程序：INPUT“n”；nINPUT“an”；aINPUT“x”；xvain1WHILE_PRINT“i”；iINPUT“ai”；ai0v_ii1WENDPRINT _ENDv*xav1用辗转相除法求36
5、与134的最大公约数，第一步是()A1343698B13436326C先除以2，得到18与67D3626110答案B解析求36与134的最大公约数，第一步是13436326，第二步是3626110，故选D.预习自测预习自测2(2015河北省廊坊一中月考)用辗转相除法求294和84的最大公约数时，需要做除法的次数是()A1B2C3D4答案B解析本题考查辗转相除法的过程.29484342,84422，故选B.3设计程序框图，用秦九韶算法求多项式的值，所选用的结构是()A顺序结构B条件结构C循环结构D以上都有答案D4用更相减损术求294和84的最大公约数时，第一步是_答案用2约简解析由于294和84
6、都是偶数，先用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.
7、故80和36的最大公约数是4.用更相减损术检验：803644，44368，36828，28820，20812，1284，844.故80和36的最大公约数是4. 规律总结更相减损术与辗转相除法都能求两个数的最大公约数，二者的区别与联系如下表.名称辗转相除法更相减损术区别以除法为主两个整数差值较大时运算次数较少相除余数为零时得结果.以减法为主两个整数的差值较大时，运算次数较多相减，两数相等得结果相减前要做是否都是偶数的判断联系都是求最大公约数的方法二者的实质都是逆归的过程二者都要用循环结构来实现.(1)用辗转相除法求288与123的最大公约数(2)用更相减损术求57与93的最大公约数(3)求567
8、与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)5674051162405162281162812081是567与405的最大公约数，从而567与405的最小公倍数为567405812835.(1)(2015三明高一检测)用秦九韶算法计算多项式f(x)3x64x55x46x37x28x1，当x0.4时的值时，需要做乘法和加法的次数分别是()A6,6B5,6C5,5D6,5(2)
9、已知一个五次多项式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(
10、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
11、时，多项式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的最大公约数探究求三个数的最大公约数时，可以先求出其中两个数的最大公约数
12、，再求这个最大公约数与第三个数的最大公约数，所得的结果就是这三个数的最大公约数解析先求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)的值是正确的，但
13、是错解中没有抓住秦九韶算法原理的关键，正确改写多项式，并使每一次计算只含有一次项误区警示误区警示正解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
14、)8220，v5220(4)35845，v6845(4)123392.当当 堂堂 检检 测测1下列有关辗转相除法的说法正确的是()A它和更相减损术一样是求多项式值的一种方法B基本步骤是用较大的数m除以较小的数n得到除式mnqr，直至rn为止C基本步骤是用较大的数m除以较小的数n得到除式mqnr(0rn)反复进行，直到r0为止D以上说法均不正确答案C2更相减损术的理论依据是()A每次操作所得的两数和前两数具有相同的最小公倍数B每次操作所得的两数和前两数具有相同的最大公约数C每次操作所得的两数和前两数的最小公倍数不同D每次操作所得的两数和前两数的最大公约数不同答案B3用更相减损术求123与51的最
15、大公约数时，需做减法的次数是()A3B5C6D8答案D解析1235172，725121，512130，30219，21912，1293，936，633，所以共做了8次减法4(2015山西省太原五中月考)用秦九韶算法求多项式f(x)7x66x53x22当x4时的值时，先算的是()A4416B7428C44464D74634答案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.
