2020版高中数学 第一章 算法初步 1.3 算法案例 第1课时 2 辗转相除法与更相减损术、秦九韶

§1.3第1课时辗转相除法与更相减损术、秦九韶算法课标解读1.通过案例，进一步体会算法的思想．2.理解辗转相除法、更相减损术、秦九韶算法的原理．(重点)3.三种算法的框图及程序应用．(难点)知识一辗转相除法【问题导思】1．36与60的最大公约数是多少？你是如何得到的？【提示】先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数．由于，故36与60的最大公约数为2×2×3＝12.2．观察下列等式8251＝6105×1＋2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？【提示】8251的最大约数是2146的约数，同样6105与2146的公约数也是8251的约数，故8251与6105的最大公约数也是6105与2146的最大公约数．辗转相除法的算法步骤第一步，给定两个正整数m、n.第二步，计算m除以n所得的余数r.第三步，m＝n，n＝r.第四步，若r＝，则m、n的最大公约数等于，否则返回第步.0m二知识二更相减损术【问题导思】设两个正整数mn(mn)，若m－n＝k，则m与n的最大公约数和n与k的最大公约数相等，反复利用这个原理，可求得98与63的最大公约数是多少？【提示】98－63＝35,63－35＝28,35－28＝7,28－7＝21,21－7＝14,14－7＝7，∴98与63的最大公约数为7.更相减损术的算法步骤第一步，任意给定两个正整数，判断它们是否都是．若是，用约简；若不是，执行第二步．第二步，以较大的数去较小的数，接着把所得的差与较小的数比较，并以数减数．继续这个操作，直到所得的差与减数为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.偶数2减大小相等将f(x)改写成如下形式：f(x)＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0.具体算法如下：(1)计算最内层括号内一次多项式的值，即v1＝.(2)由内向外逐层计算多项式的值，即v2＝v1x＋an－2，v3＝v2x＋an－3，…vn＝.anx＋an－1vn－1x＋a0知识三秦九韶算法类型一程序框图的认识和理解例1用辗转相除法求228与1995的最大公约数．解：1995＝8×228＋171，228＝1×171＋57，171＝3×57，∴228与1995的最大公约数为57.变式训练用辗转相除法求779和209的最大公约数．解：∵779＝209×3＋152，209＝152×1＋57，152＝57×2＋38，57＝38×1＋19，38＝19×2，∴779与209的最大公约数为19.类型二用更相减损术求最大公约数例2用更相减损术求154,484的最大公约数．解：154÷2＝77,484÷2＝242，下面用更相减损术，求77与242的最大公约数．242－77＝165,165－77＝88,88－77＝11,77－11＝66,66－11＝55,55－11＝44,44－11＝33,33－11＝22,22－11＝11，故77与242的最大公约数为11，则154与484的最大公约数为11×2＝22.变式训练用更相减损术求576与246的最大公约数．解：用2约简576和246得288与123.288－123＝165,165－123＝42，123－42＝81,81－42＝39，42－39＝3,39－3＝36,36－3＝33，33－3＝30,30－3＝27，27－3＝24,24－3＝21，21－3＝18,18－3＝15，15－3＝12,12－3＝9，9－3＝6,6－3＝3.∴576与246的最大公约数为3×2＝6.类型三秦九韶算法的应用例3用秦九韶算法求多项式f(x)＝7x7－6x6＋4x4＋3x3－2x2＋x－5，当x＝3时的值．解：f(x)＝((((((7x－6)x＋0)x＋4)x＋3)x－2)x＋1)x－5，v0＝7，v1＝7×3－6＝15；v2＝15×3＋0＝45；v3＝45×3＋4＝139；v4＝139×3＋3＝420；v5＝420×3－2＝1258；v6＝1258×3＋1＝3775；v7＝3775×3－5＝11320.∴当x＝3时，多项式的值为11320.变式训练用秦九韶算法计算多项式f(x)＝x6－12x5＋60x4－160x3＋240x2－192x＋64，当x＝2时的值．解：将f(x)改写为f(x)＝(((((x－12)x＋60)x－160)x＋240)x－192)x＋64，由内向外依次计算一次多项式当x＝2时的值，v0＝1，v1＝1×2－12＝－10，v2＝－10×2＋60＝40，v3＝40×2－160＝－80，v4＝－80×2＋240＝80，v5＝80×2－192＝－32，v6＝－32×2＋64＝0.∴f(2)＝0，即x＝2时，原多项式的值为0.课堂小结1．辗转相除法与更相减损术都是求两数最大公约数的方法．辗转相除法计算次数少，步骤简捷，更相减损术计算次数多，步骤复杂，但是更相减损术每一步的计算都是减法，比做除法运算要简单一些，一般当数较小时可以考虑用更相减损术，当数较大时可以考虑用辗转相除法．2．用秦九韶算法可大大降低乘法的运算次数，提高了运算速度．用此方法求值，关键是正确地将所给多项式改写，然后由内向外计算，由于后项计算需用到前项结果，故应认真、细心，确保结果的准确性．1．辗转相除法与更相减损术的区别和联系名称辗转相除法更相减损术区别①以除法为主．②两个整数差值较大时运算次数较少．③相除余数为零时得结果.①以减法为主．②两个整数的差值较大时，运算次数较多．③相减，两数相等得结果．④相减前要做是否都是偶数的判断．联系①都是求两个正整数的最大公约数的方法．②二者的实质都是递推的过程．③二者都要用循环结构来实现.2.辗转相除法的程序框图及程序表示程序框图：程序：INPUTm，nDOr＝mMODnm＝nn＝rLOOPUNTILr＝0PRINTmEND当堂检测1．490和910的最大公约数为()A．2B．10C．30D．70【解析】910＝490×1＋420,490＝420×1＋70,420＝70×6，故最大公约数为70.【答案】D2．用更相减损术求294和84的最大公约数为()A．21B．42C．32D．16【解析】294÷2＝147,84÷2＝42,147－42＝105,105－42＝63,63－42＝21,42－21＝21,21×2＝42，所以最大公约数为42.【答案】B3．用秦九韶算法求f(x)＝2x3＋x－3当x＝3时的值v2＝________.【解析】f(x)＝((2x＋0)x＋1)x－3，v0＝2；v1＝2×3＋0＝6；v2＝6×3＋1＝19.【答案】194．用更相减损术求288与153的最大公约数．解：288－153＝135,153－135＝18,135－18＝117,117－18＝99,99－18＝81,81－18＝63,63－18＝45,45－18＝27,27－18＝9,18－9＝9.∴288与153的最大公约数为9.