2021学年1.3 算法与案例多媒体教学ppt课件

这是一份2021学年1.3 算法与案例多媒体教学ppt课件，文件包含13第1课时ppt、13第1课时doc等2份课件配套教学资源，其中PPT共45页， 欢迎下载使用。

第1课时　辗转相除法与更相减损术、秦九韶算法
在小学，我们已经学过求最大公约数的知识，你能求出18与30的最大公约数吗？先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来．∴18和30的最大公约数是2×3＝6.如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8 251与6 105的最大公约数？
1．辗转相除法(1)辗转相除法是用于求__________________________的一种算法，这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫________________.(2)所谓辗转相除法，就是对于给定的两个数，用____________除以____________.若余数不为零，则将__________________构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时____________就是原来两个数的最大公约数．
两个正整数的最大公约数　
(3)算法步骤：第一步，给定两个正整数m，n.第二步，计算m除以n所得的余数r.第三步，m＝n，n＝r.第四步，若r＝______，则m，n的最大公约数等于m；否则，返回第______步．(4)程序框图．
2．更相减损术(1)更相减损术是我国古代数学专著________________中介绍的一种求两数最大公约数的方法．(2)更相减损术的基本过程是：第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用______约简；若不是，执行第二步．第二步，以较大的数________较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数________为止，则这个数或这个数与约简的数的________就是所求的最大公约数．
3．秦九韶算法(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＝______________，v2＝v1x＋an－2，v3＝v2x＋an－3，…，vn＝_________________.
(2)算法步骤：第一步，输入多项式的次数n、最高次项的系数an和x的值．第二步，将v的值初始化为an，将i的值初始化为n－1.第三步，输入i次项的系数ai.第四步，v＝vx＋ai，i＝__________.第五步，判断i是否大于或等于______.若是，则返回第三步；否则，输出多项式的值______.
(3)程序框图如图所示．
1．辗转相除法可解决的问题是(　　)A．求两个正整数的最大公约数B．多项式求值C．求两个正整数的最小公倍数D．排序问题[解析]　辗转相除法可以求两个正整数的最大公约数．
2．在对16和12求最大公约数时，整个操作如下：(16,12)→(4,12)→ (4,8)→(4,4)，由此可以看出16和12的最大公约数是(　　)A．4　　　　　　　B．12C．16　　D．8[解析]　按更相减损术求最大公约数，到最后(4,4)相等，故最大公约数为4.
3．用更相减损术求225与30的最大公约数时，需要做减法运算的次数是(　　)A．9　　　　　B．8C．7　　　　　　D．6[解析]　225－30＝195,195－30＝165,165－30＝135,135－30＝105,105－30＝75,75－30＝45,45－30＝15,30－15＝15，故225与30的最大公约数是15，需要做8次减法运算．
4．用秦九韶算法计算f(x)＝6x5－4x4＋x3－2x2－9x，需要加法(或减法)与乘法运算的次数分别为(　　)A．5,4　　B．5,5C．4,4　　D．4,5[解析]　n次多项式，当最高次项的系数不为1时，需进行n次乘法；若各项均不为0，则需进行n次加法(或减法)，缺一项就减少一次加法(或减法)运算，而这个5次多项式的5次系数不为1，缺常数项，因而乘法次数为5，加法(或减法)次数为5－1＝4.故选D．
5．245与75两数的最小公倍数为______________.[解析]　先求245与75的最大公约数．(245,75)→(170,75)→(95,75)→ (20,75)→(55,20)→(35,20)→(15,20)→(5,15)→(10,5)→(5,5)．故245与75的最大公约数为5，∴245与75的最小公倍数为245×75÷5＝3 675.
6．分别用辗转相除法和更相减损术求357和105的最大公约数，并求最小公倍数．[解析]　辗转相除法：357＝105×3＋42，105＝42×2＋21，42＝21×2.故105与357的最大公约数为21.
更相减损术：357－105＝252，252－105＝147，147－105＝42，105－42＝63，63－42＝21，42－21＝21.故105与357的最大公约数为21.最小公倍数为105×357÷21＝1 785.
用辗转相除法求80和36的最大公约数，并用更相减损术检验所得结果．[思路分析]　1.辗转相除法与更相减损术的主要区别是什么？2．将80作为大数，36作为小数，执行辗转相除法和更相减损术的步骤即可．
命题方向1　⇨辗转相除法和更相减损术的应用
[解析]　用辗转相除法：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.利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．2．利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数．若是，用2约简．也可以不除以2，直接求最大公约数，这样不影响最后结果．3．当两个整数的差较大时，利用辗转相除法计算的次数较少．
〔跟踪练习1〕　(1)用辗转相除法求288与123的最大公约数．(2)用更相减损术求57与93的最大公约数．[解析]　(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.
用秦九韶算法求多项式f(x)＝8x7＋5x6＋3x4＋2x＋1在x＝2时的值．[思路分析]　利用秦九韶算法一步一步地代入运算，注意本题中有某几次项不存在；在计算时，应将这些项加上，比如缺少x3这一项，可看作0·x3加上．
命题方向2　⇨秦九韶算法的应用
[解析]　f(x)＝((((((8x＋5)x＋0)x＋3)x＋0)x＋0)x＋2)x＋1，依次用公式计算当x＝2时的值：v0＝8，v1＝8×2＋5＝21，v2＝21×2＋0＝42，v3＝42×2＋3＝87，v4＝87×2＋0＝174，v5＝174×2＋0＝348，v6＝348×2＋2＝698，v7＝698×2＋1＝1 397，故当x＝2时，多项式的值为1 397.
『规律总结』　(1)算法一方面具有具体化、程序化、机械化的特点，同时又有高度抽象性、概括性和精确性．对于一个具体算法而言，从算法分析到算法语言的实现，任何一个疏漏或错误都将导致算法的失败．算法是思维的条理化、逻辑化．(2)算法既重视“算则”，更重视“算理”．对于算法而言，一步一步地程序化步骤，即“算则”固然重要，但这些步骤的依据，即“算理”有着更基本的作用，“算理”是“算则”的基础，“算则”是“算理”的表现．(3)用秦九韶算法时要正确将多项式的形式进行改写，然后由内向外依次计算．当多项式函数中间出现空项时，要以系数为零的齐次项补充．
〔跟踪练习2〕　用秦九韶算法求多项式f(x)＝x5＋5x4＋10x3＋10x2＋5x＋1当x＝－2时的值．[解析]　f(x)＝x5＋5x4＋10x3＋10x2＋5x＋1＝((((x＋5)x＋10)x＋10)x＋5)x＋1，而x＝－2，所以有v0＝1，v1＝v0x＋a4＝1×(－2)＋5＝3，v2＝v1x＋a3＝3×(－2)＋10＝4，v3＝v2x＋a2＝4×(－2)＋10＝2，v4＝v3x＋a1＝2×(－2)＋5＝1，v5＝v4x＋a0＝1×(－2)＋1＝－1.故f(－2)＝－1.
求325,130,270三个数的最大公约数．[思路分析]　求三个数的最大公约数，可先求两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数．[解析]　解法一(辗转相除法)：因为325＝130×2＋65,130＝65×2，所以325和130的最大公约数为65.因为270＝65×4＋10,65＝10×6＋5,10＝5×2，所以65和270的最大公约数为5，故325,130,270三个数的最大公约数为5.
命题方向3　⇨求三个正整数的最大公约数
解法二(更相减损术)：325－130＝195,195－130＝65,130－65＝65.所以325和130的最大公约数是65.270－65＝205,205－65＝140,140－65＝75,75－65＝10,65－10＝55,55－10＝45,45－10＝35,35－10＝25,25－10＝15,15－10＝5,10－5＝5.所以270与65的最大公约数为5.所以325,130,270的最大公约数为5.
『规律总结』　理解辗转相除法的实质，从计算结果上看，辗转相除法是以相除余数为零而得到结果的．
〔跟踪练习3　求三个数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)＝x5＋x3＋x2＋x＋1，用秦九韶算法求f(3)的值．[错解]　因为f(x)＝(((x＋1)x＋1)x＋1)x＋1，所以当x＝3时，v0＝1，v1＝3＋1＝4，v2＝4×3＋1＝13，v3＝13×3＋1＝40，v4＝40×3＋1＝120＋1＝121，所以当x＝3时，f(3)＝121.
[辨析]　当多项式中间出现空项时，用秦九韶算法求函数值要补上系数为0的相应项，忽略了这一点，导致结果出现错误．[正解]　原多项式可化为：f(x)＝((((x＋0)x＋1)x＋1)x＋1)x＋1，当x＝3时，v0＝1，v1＝1×3＋0＝3，v2＝3×3＋1＝10，v3＝10×3＋1＝31，v4＝31×3＋1＝94，v5＝94×3＋1＝283，所以，当x＝3时， f(3)＝283.
通过算法案例的学习，知道算法的核心是一般意义上的解决问题的策略的具体化．对于一个实际问题，我们在分析、思考后可将之转化为数学问题，从而获得解决它的基本思路．
算法案例在实际生活中的应用
现有长度为2.4 m和5.6 m两种规格的钢筋若干，要焊接一批棱上无接点的正方体模型，问怎样设计才能保证正方体的体积最大且不浪费材料？[思路分析]　要焊接正方体，就是将两种规格的钢筋截成长度相等的钢筋条．为了保证不浪费材料，应使得每种规格的钢筋截取后没有剩余，因此截取的长度应为2.4与5.6的公约数；为使得正方体的体积最大，因此截取的长度应为2.4与5.6的最大公约数．
[解析]　用更相减损术来求2.4与5.6的最大公约数：5.6－2.4＝3.2，3.2－2.4＝0.8，2.4－0.8＝1.6，1.6－0.8＝0.8，因此2.4与5.6的最大公约数为0.8.所以使得正方体的棱长为0.8 m时，正方体的体积最大且不浪费材料．
1．用辗转相除法求36与134的最大公约数，第二步是(　　)A．134－36＝98B．134＝36×3＋26C．先除以2，得到18与67D．36＝26×1＋10[解析]　求36与134的最大公约数，第一步是134＝36×3＋26，第二步是36＝26×1＋10，故选D．
2．用更相减损术求123与51的最大公约数时，需做减法的次数是(　　)A．3B．5C．6D．8[解析]　(123,51)→(72,51)→(21,51)→(21,30)→(21,9)→(12,9)→(3,9)→(3,6) →(3,3)所以共做了8次减法．
3．已知f(x)＝x5＋2x3＋3x2＋x＋1，应用秦九韶算法计算x＝3时的值时，v3的值为(　　)A．27B．11C．109D．36[解析]　将函数式化成如下形式：f(x)＝((((x＋0)x＋2)x＋3)x＋1)x＋1，由内向外依次计算：v0＝1，v1＝1×3＋0＝3，v2＝3×3＋2＝11，v3＝11×3＋3＝36.
4．用辗转相除法求得数98与63的最大公约数是______.[解析]　98＝63×1＋35,63＝35×1＋28,35＝28×1＋7,28＝4×7＋0，∴最大公约数为7.
5．已知f(x)＝3x4＋2x2＋4x＋2，利用秦九韶算法求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.