搜索
算法初步第一章1.3算法案例第一章第1课时辗转相除法与更相减损术、秦九韶算法高效课堂2课时作业4优效预习1当堂检测3优效预习•鸡兔同笼问题是中国古代数学名著《孙子算法》中的一道名题，题目是这样的：“今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？”书中给出的解法是：鸡有两只脚，兔有四只脚，把脚数除以2，共有47对脚．由于鸡有1对脚，兔有2对脚，所以从47中减去25，得12即为兔子数．因为如要笼子里的动物每只都只有1对脚，就会多出12对脚来，把这12对脚分别加到有2对脚的动物身上，就有12只脚动物，即兔子数．整个解题过程可以简单地写作：•●知识衔接(头35脚94)―→(头35脚47对)――→以下减上(3512)――→以上减下(2312)．上为鸡数，下为兔数．当然也可以假设笼子里的返回物都是鸡(兔)，那么多(少)出的脚数除以2即为兔子(鸡)数，这就是“寓理于算”的方法．如果用二元一次方程组求解，也会非常方便地解决．•1．辗转相除法与更相减损术•(1)辗转相除法．•①算法步骤：•第一步，给定两个正整数m，n.•第二步，计算m除以n所得的余数r.•第三步，m＝n，n＝r.•第四步，若r＝___，则m，n的最大公约数等于m；否则返回第___步．•●自主预习0二•②程序框图如图所示．•③程序：•INPUTm，n•DO•r＝mMODn•m＝n•n＝r•LOOPUNTIL_______•PRINT___•ENDr＝0m•(2)更相减损术．•算法步骤：•第一步，任意给定两个正整数，判断它们是否都是______．若是，用___约简；若不是，执行第二步．•第二步，以较大的数___去较小的数，接着把所得的差与较小的数比较，并以___数减___数．继续这个操作，直到所得的差与减数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．偶数2减大小•2．秦九韶算法•(1)概念：求多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0的值时，常用秦九韶算法，这种算法的运算次数较少，是多项式求值比较先进的算法，其实质是转化为求n个______多项式的值，共进行___次乘法运算和___次加法运算．其过程是：•改写多项式为：•f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0•＝(anxn－1＋an－1xn－2＋…＋a1)x＋a0•＝((anxn－2＋an－1xn－3＋…＋a2)x＋a1)x＋a0＝…•＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0.•设v1＝____________，一次nnanx＋an－1•v2＝v1x＋an－2，•v3＝v2x＋an－3，•…，•vn＝___________.vn－1x＋a0•(2)算法步骤：•第一步，输入多项式的次数n、最高次项的系数an和x的值．•第二步，将v的值初始化为an，将i的值初始化为n－1.•第三步，输入i次项的系数ai.•第四步，v＝vx＋ai，i＝________.•第五步，判断i是否大于或等于___.若是，则返回第三步；否则，输出多项式的值___.i－10v•(3)程序框图如图所示．•(4)程序：•INPUT“n＝”；n•INPUT“an＝”；a•INPUT“x＝”；x•v＝a•i＝n－1•WHILE___________•PRINT“i＝”；i•INPUT“ai＝”；ai＝0•v＝_________•i＝i－1•WEND•PRINT___•ENDv*x＋av•1．用辗转相除法求36与134的最大公约数，第一步是()•A．134－36＝98•B．134＝36×3＋26•C．先除以2，得到18与67•D．36＝26×1＋10•[答案]B•[解析]求36与134的最大公约数，第一步是134＝36×3＋26，第二步是36＝26×1＋10，故选D.•●预习自测•2．(2015·河北省廊坊一中月考)用辗转相除法求294和84的最大公约数时，需要做除法的次数是()•A．1B．2•C．3D．4•[答案]B•[解析]本题考查辗转相除法的过程.294＝84×3＋42,84＝42×2，故选B.•3．设计程序框图，用秦九韶算法求多项式的值，所选用的结构是()•A．顺序结构B．条件结构•C．循环结构D．以上都有•[答案]D•4．用更相减损术求294和84的最大公约数时，第一步是________．•[答案]用2约简•[解析]由于294和84都是偶数，先用2约简．•5．(2015·云南省景洪一中月考)用秦九韶算法计算多项式f(x)＝3x6＋2x5＋4x4＋5x3＋7x2＋8x＋1在x＝0.5时的值，需做乘法和加法的次数分别是________．•[答案]6次乘法，6次加法•[解析]将多项式改写为f(x)＝(((((3x＋2)x＋4)x＋5)x＋7)x＋8)x＋1，化为6个一次因式求解，故只做了6次乘法和6次加法．高效课堂•用辗转相除法求80和36的最大公约数，并用更相减损术检验所得结果．•[探究]1.辗转相除法与更相减损术的主要区别是什么？•2．将80作为大数，36作为小数，执行辗转相除法和更相减损术的步骤即可．•辗转相除法和更相减损术的应用•●互动探究•[解析]用辗转相除法：•80＝36×2＋8，•36＝8×4＋4，•8＝4×2＋0.•故80和36的最大公约数是4.•用更相减损术检验：•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)用辗转相除法求288与123的最大公约数．•(2)用更相减损术求57与93的最大公约数．•(3)求567与405的最小公倍数．•[解析](1)288＝123×2＋42,123＝42×2＋39，•42＝39×1＋3,39＝3×13，•∴288和123的最大公约数是3.•(2)(93,57)―→(36,57)―→(36,21)―→(15,21)―→(15,6)―→(9,6)―→(3,6)―→(3,3)，•∴93与57的最大公约数是3.•(3)567＝405×1＋162•405＝162×2＋81•162＝81×2＋0•∴81是567与405的最大公约数，从而567与405的最小公倍数为567×405÷81＝2835.•(1)(2015·三明高一检测)用秦九韶算法计算多项式f(x)＝3x6＋4x5＋5x4＋6x3＋7x2＋8x＋1，当x＝0.4时的值时，需要做乘法和加法的次数分别是()•A．6,6B．5,6•C．5,5D．6,5•(2)已知一个五次多项式f(x)＝2x5－4x3＋3x2－5x＋1，用秦九韶算法求这个多项式当x＝3是的值．•用秦九韶算法求多项式的值•[探究]1.用秦九韶算法求多项式的值时，几次多项式就做几次乘法运算，对吗？•2．用秦九韶算法求多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0在x＝x0时的值时，v0是什么？v1呢？•[解析](1)将多项式改写成如下形式f(x)＝(((((3x＋4)x＋5)x＋6)x＋7)x＋8)x＋1，显然，把x＝0.4代入计算其值时，共做了6次乘法，6次加法．•(2)因为f(x)＝((((2x＋0)x－4)x＋3)x－5)x＋1，•v0＝2，•v1＝2×3＋0＝6，•v2＝6×3－4＝14，•v3＝14×3＋3＝45，•v4＝45×3－5＝130，•v5＝130×3＋1＝391，•所以f(3)＝391.•[答案](1)A(2)391•[规律总结]用秦九韶算法时要正确将多项式的形式进行改写，然后由内向外依次计算．当多项式函数中间出现空项时，要以系数为零的齐次项补充．•用秦九韶算法求多项式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x当x＝3时的值．•[探究]解决本题首先需要将原多项式化成f(x)＝((((((7x＋6)x＋5)x＋4)x＋3)x＋2)x＋1)x的形式，其次再弄清v0，v1，v2，…，v7分别是多少，再针对这些式子进行计算．•[解析]f(x)＝((((((7x＋6)x＋5)x＋4)x＋3)x＋2)x＋1)x，所以有•v0＝7；•v1＝7×3＋6＝27；•v2＝27×3＋5＝86；•v3＝86×3＋4＝262；•v4＝262×3＋3＝789；•v5＝789×3＋2＝2369；•v6＝2369×3＋1＝7108；•v7＝7108×3＝21324.•故当x＝3时，多项式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x的值为21324.•试用辗转相除法求325、130、270的最大公约数．•[探究]应用辗转相除法去除，即依据m＝nq＋r反复执行，直到r＝0为止．•求多个数的最大公约数•●探索延拓•[解析]∵325＝130×2＋65,130＝65×2，•∴325与130的最大公约数是65.•∵270＝65×4＋10,65＝10×6＋5,10＝65×2，•∴65与270的最大公约数是5，•故325、130、270三个数的最大公约数为5.•[规律总结]理解辗转相除法的实质，从计算结果上看，辗转相除法是以相除余数为零而得到结果的．•求三个数175,100,75的最大公约数．•[探究]求三个数的最大公约数时，可以先求出其中两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，所得的结果就是这三个数的最大公约数．•[解析]先求175与100的最大公约数：•175＝100×1＋75,100＝75×1＋25，•75＝25×3，•∴175与100的最大公约数是25.•再求25与75的最大公约数：•75－25＝50,50－25＝25，•∴75和25的最大公约数是25.•∴175,100,75的最大公约数是25.•[点评]本题的解法可以推广到求多个数的最大公约数，只需依次计算即可．•已知f(x)＝3x4＋2x2＋4x＋2，利用秦九韶算法求f(－2)的值．•[错解]f(x)＝((3x2＋2)x＋4)x＋2，•v1＝3×(－2)2＋2＝14；•v2＝14×(－2)＋4＝－24；•v3＝－24×(－2)＋2＝50.•故f(－2)＝50.•[错因分析]所求f(－2)的值是正确的，但是错解中没有抓住秦九韶算法原理的关键，正确改写多项式，并使每一次计算只含有一次项．•●误区警示•[正解]f(x)＝3x4＋0·x3＋2x2＋4x＋2＝(((3x＋0)x＋2)x＋4)x＋2，•v0＝3，•v1＝3×(－2)＋0＝－6；•v2＝－6×(－2)＋2＝14；•v3＝14×(－2)＋4＝－24；•v4＝－24×(－2)＋2＝50.•故f(－2)＝50.•(2015·贵阳高一检测)用秦九韶算法计算多项式f(x)＝12＋35x－8x2＋79x3＋6x4＋5x5＋3x6在x＝－4的值时，v3的值为________．•[答案]－57•[解析]多项式变形为f(x)＝3x6＋5x5＋6x4＋79x3－8x2＋35x＋12＝(((((3x＋5)x＋6)x＋79)x－8)x＋35)x＋12，•当x＝－4时，•v0＝3，•v1＝3×(－4)＋5＝－7，•v2＝－7×(－4)＋6＝34，•v3＝34×(－4)＋79＝－57，•v4＝－57×(－4)－8＝220，•v5＝220×(－4)＋35＝－845，•v6＝－845×(－4)＋12＝3392.当堂检测•1．下列有关辗转相除法的说法正确的是()•A．它和更相减损术一样是求多项式值的一种方法•B．基本步骤是用较大的数m除以较小的数n得到除式m＝nq＋r，直至rn为止•C．基本步骤是用较大的数m除以较小的数n得到除式m＝qn＋r(0≤rn)反复进行，直到r＝0为止•D．以上说