1.3 算法案例 课件1
图片预览
文档简介
课件14张PPT。1.3 算法案例【学习目标】
1．理解辗转相除法与更相减损术的含义，了解其执行过程．
2．理解秦九韶算法的计算过程，并了解它提高计算效率的实质．
【核心扫描】
1．两种算法的原理及应用．(重难点)
2．秦九韶算法中多项式的改写．(易错点)
【课前导学】 辗转相除法
(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的___________的古老而有效的算法．
(2)辗转相除法的算法步骤
第一步，给定________________.
第二步，计算___________________.
第三步， ____________.
第四步，若r＝0，则m、n的最大公约数等于___；否则，返回________.1．最大公约数两个正整数m，nm除以n所得的余数rm＝n，n＝rm第二步更相减损术
第一步，任意给定两个正整数，判断它们是否都是_____．若是，用_______；若不是，执行_______ ．
第二步，以_____的数减去_____的数，接着把所得的差与_____的数比较，并以大数减小数，继续这个操作，直到所得的数_____为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．
2．偶数2约简第二步较小较小相等较大1．辗转相除法与更相减损术的区别和联系
名师点睛秦九韶算法
(1)特点：通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，只需做n次乘法和n次加法即可．
(2)算法步骤：
设Pn(x)＝anxn＋an－1xn－1＋…＋a1x＋a0，将其改写为
Pn(x)＝(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.
第一步：计算最内层anx＋an－1的值，将anx＋an－1的值赋给一个变量v1(为方便将an赋予变量v0)；
第二步：计算(anx＋an－1)x＋an－2的值，可以改写为v1x＋an－2，将v1x＋an－2的值赋给一个变量v2；2.秦九韶算法
把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如下形式：
(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0，
求多项式的值时，首先计算_____________一次多项式的值，即v1＝__________，然后由内向外逐层计算一次多项式的值，即
v2＝__________，
v3＝__________，
…
vn＝__________.
这样，求n次多项式f(x)的值就转化为求________________的值．3．最内层括号内anx＋an－1v1x＋an－2v2x＋an－3vn－1x＋a0n个一次多项式依次类推，即每一步的计算之后都赋予一个新值vk，即从最内层的括号到最外层．
括号的值依次赋予变量v1，v2，…，vk，…，vn，第n步所求值vn＝vn－1x＋a0即为所求多项式的值．
(3)秦九韶算法有以下几个优点：
①大大减少了乘法的次数，使计算量减小．在计算机上做一次乘法所需要的时间是做加法、减法的几倍到十几倍，减少做乘法的次数也就加快了计算的速度；
②规律性强，便于利用循环语句来实现算法；
③避免了对自变量x单独做幂的计算，每次都是计算一个一次多项式的值，从而可以提高计算的精度．
课内探究 分别用辗转相除法和更相减损术求261和319的最大公约数．【例1】法二 (更相减损术)
319－261＝58，
261－58＝203，
203－58＝145，
145－58＝87，
87－58＝29，
58－29＝29，
29－29＝0，
所以319与261的最大公约数是29.[思路探索] 使用辗转相除法可依据m＝nq＋r，反复执行直到余数为0；更相减损术则是根据m－n＝r，反复执行，直到n＝r为止．解法一 (辗转相除法)
319=1×261+58，
261＝4×58+29，
58＝2×29，
所以319与261的最大公约数为29.规律方法 (1)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．
(2)利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数．若是，用2约简．也可以不除以2，直接求最大公约数，这样不影响最后结果． 用辗转相除法求80与36的最大公约数，并用更相减损术检验你的结果．
解：80＝36×2＋8，
36＝8×4＋4，
8＝4×2＋0，
即80与36的最大公约数是4.【变式1】7－2＝5
5－2＝3
3－2＝1
2－1＝1
1×2×2＝4
所以80与36的最大公约数为4.验证：
80÷2＝40，36÷2＝18
40÷2＝20 ， 18÷2＝920—9＝11
11－9＝2
9－2＝7 用秦九韶算法求f(x)＝3x5＋8x4－3x3＋5x2＋12x－6，当x＝2的值．【例2】[规范解答] 根据秦九韶算法，把多项式改写成如下形式：
f(x)＝((((3x＋8)x－3)x＋5)x＋12)x－6，按照从内到外的顺序，依次计算一次多项式当x＝2时的值．
v0＝3， v1＝v0×2＋8＝3×2＋8＝14，所以当x＝2时，多项式的值为238.v2＝v1×2－3＝14×2－3＝25， v3＝v2×2＋5＝25×2＋5＝55，v4＝v3×2＋12＝55×2＋12＝122，v5＝v4×2－6＝122×2－6＝238，【题后反思】 (1)先将多项式写成一次多项式的形式，然后运算时从里到外，一步一步地做乘法和加法即可．这样比直接将x＝2代入原式大大减少了计算量．若用计算机计算，则可提高运算效率．
(2)注意：当多项式中n次项不存在时，可将第n次项看作0·xn.
用秦九韶算法计算f(x)＝6x5－4x4＋x3－2x2－9x，需要加法(或减法)与乘法运算的次数分别为( )．
A．5，4 B．5，5
C．4，4 D．4，5
解析 n次多项式需进行n次乘法；若各项均不为零，则需进行n次加法，缺一项就减少一次加法运算．f(x)中无常数项，故加法次数要减少一次，为5－1＝4.故选D.
答案 D【变式3】 已知f(x)＝x5＋2x4＋3x3＋4x2＋5x＋6，用秦九韶算法求这个多项式当x＝2时的值时，做了几次乘法？几次加法？
[错解] 根据秦九韶算法，把多项式改写成如下形式f(x)＝((((x＋2)x＋3)x＋4)x＋5)x＋6.
按照从内到外的顺序，依次计算一次多项式当x＝2时的值：v1＝2＋2＝4；v2＝2v1＋3＝11；v3＝2v2＋4＝26；v4＝2v3＋5＝57；v5＝2v4＋6＝120.
显然，在v1中未做乘法，只做了1次加法；在v2，v3，v4，v5中各做了1次加法，1次乘法．因此，共做了4次乘法，5次加法．误区警示 对秦九韶算法中的运算次数理解错误【示例】在v1中虽然“v1＝2＋2＝4”，而计算机还是做了1次乘法“v1＝2×1＋2＝4”．因为用秦九韶算法计算多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0当x＝x0时的值时，首先将多项式改写成f(x)＝(…(anx＋an－1)x＋…＋a1)x＋a0，然后再计算v1＝anx＋an－1，v2＝v1x＋an－2，v3＝v2x＋an－3，…，vn＝vn－1x＋a0.无论an是不是1，这次的乘法都是要进行的．
[正解] 由上分析可知，共做了5次乘法，5次加法．
1．理解辗转相除法与更相减损术的含义，了解其执行过程．
2．理解秦九韶算法的计算过程，并了解它提高计算效率的实质．
【核心扫描】
1．两种算法的原理及应用．(重难点)
2．秦九韶算法中多项式的改写．(易错点)
【课前导学】 辗转相除法
(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的___________的古老而有效的算法．
(2)辗转相除法的算法步骤
第一步，给定________________.
第二步，计算___________________.
第三步， ____________.
第四步，若r＝0，则m、n的最大公约数等于___；否则，返回________.1．最大公约数两个正整数m，nm除以n所得的余数rm＝n，n＝rm第二步更相减损术
第一步，任意给定两个正整数，判断它们是否都是_____．若是，用_______；若不是，执行_______ ．
第二步，以_____的数减去_____的数，接着把所得的差与_____的数比较，并以大数减小数，继续这个操作，直到所得的数_____为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．
2．偶数2约简第二步较小较小相等较大1．辗转相除法与更相减损术的区别和联系
名师点睛秦九韶算法
(1)特点：通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，只需做n次乘法和n次加法即可．
(2)算法步骤：
设Pn(x)＝anxn＋an－1xn－1＋…＋a1x＋a0，将其改写为
Pn(x)＝(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.
第一步：计算最内层anx＋an－1的值，将anx＋an－1的值赋给一个变量v1(为方便将an赋予变量v0)；
第二步：计算(anx＋an－1)x＋an－2的值，可以改写为v1x＋an－2，将v1x＋an－2的值赋给一个变量v2；2.秦九韶算法
把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如下形式：
(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0，
求多项式的值时，首先计算_____________一次多项式的值，即v1＝__________，然后由内向外逐层计算一次多项式的值，即
v2＝__________，
v3＝__________，
…
vn＝__________.
这样，求n次多项式f(x)的值就转化为求________________的值．3．最内层括号内anx＋an－1v1x＋an－2v2x＋an－3vn－1x＋a0n个一次多项式依次类推，即每一步的计算之后都赋予一个新值vk，即从最内层的括号到最外层．
括号的值依次赋予变量v1，v2，…，vk，…，vn，第n步所求值vn＝vn－1x＋a0即为所求多项式的值．
(3)秦九韶算法有以下几个优点：
①大大减少了乘法的次数，使计算量减小．在计算机上做一次乘法所需要的时间是做加法、减法的几倍到十几倍，减少做乘法的次数也就加快了计算的速度；
②规律性强，便于利用循环语句来实现算法；
③避免了对自变量x单独做幂的计算，每次都是计算一个一次多项式的值，从而可以提高计算的精度．
课内探究 分别用辗转相除法和更相减损术求261和319的最大公约数．【例1】法二 (更相减损术)
319－261＝58，
261－58＝203，
203－58＝145，
145－58＝87，
87－58＝29，
58－29＝29，
29－29＝0，
所以319与261的最大公约数是29.[思路探索] 使用辗转相除法可依据m＝nq＋r，反复执行直到余数为0；更相减损术则是根据m－n＝r，反复执行，直到n＝r为止．解法一 (辗转相除法)
319=1×261+58，
261＝4×58+29，
58＝2×29，
所以319与261的最大公约数为29.规律方法 (1)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．
(2)利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数．若是，用2约简．也可以不除以2，直接求最大公约数，这样不影响最后结果． 用辗转相除法求80与36的最大公约数，并用更相减损术检验你的结果．
解：80＝36×2＋8，
36＝8×4＋4，
8＝4×2＋0，
即80与36的最大公约数是4.【变式1】7－2＝5
5－2＝3
3－2＝1
2－1＝1
1×2×2＝4
所以80与36的最大公约数为4.验证：
80÷2＝40，36÷2＝18
40÷2＝20 ， 18÷2＝920—9＝11
11－9＝2
9－2＝7 用秦九韶算法求f(x)＝3x5＋8x4－3x3＋5x2＋12x－6，当x＝2的值．【例2】[规范解答] 根据秦九韶算法，把多项式改写成如下形式：
f(x)＝((((3x＋8)x－3)x＋5)x＋12)x－6，按照从内到外的顺序，依次计算一次多项式当x＝2时的值．
v0＝3， v1＝v0×2＋8＝3×2＋8＝14，所以当x＝2时，多项式的值为238.v2＝v1×2－3＝14×2－3＝25， v3＝v2×2＋5＝25×2＋5＝55，v4＝v3×2＋12＝55×2＋12＝122，v5＝v4×2－6＝122×2－6＝238，【题后反思】 (1)先将多项式写成一次多项式的形式，然后运算时从里到外，一步一步地做乘法和加法即可．这样比直接将x＝2代入原式大大减少了计算量．若用计算机计算，则可提高运算效率．
(2)注意：当多项式中n次项不存在时，可将第n次项看作0·xn.
用秦九韶算法计算f(x)＝6x5－4x4＋x3－2x2－9x，需要加法(或减法)与乘法运算的次数分别为( )．
A．5，4 B．5，5
C．4，4 D．4，5
解析 n次多项式需进行n次乘法；若各项均不为零，则需进行n次加法，缺一项就减少一次加法运算．f(x)中无常数项，故加法次数要减少一次，为5－1＝4.故选D.
答案 D【变式3】 已知f(x)＝x5＋2x4＋3x3＋4x2＋5x＋6，用秦九韶算法求这个多项式当x＝2时的值时，做了几次乘法？几次加法？
[错解] 根据秦九韶算法，把多项式改写成如下形式f(x)＝((((x＋2)x＋3)x＋4)x＋5)x＋6.
按照从内到外的顺序，依次计算一次多项式当x＝2时的值：v1＝2＋2＝4；v2＝2v1＋3＝11；v3＝2v2＋4＝26；v4＝2v3＋5＝57；v5＝2v4＋6＝120.
显然，在v1中未做乘法，只做了1次加法；在v2，v3，v4，v5中各做了1次加法，1次乘法．因此，共做了4次乘法，5次加法．误区警示 对秦九韶算法中的运算次数理解错误【示例】在v1中虽然“v1＝2＋2＝4”，而计算机还是做了1次乘法“v1＝2×1＋2＝4”．因为用秦九韶算法计算多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0当x＝x0时的值时，首先将多项式改写成f(x)＝(…(anx＋an－1)x＋…＋a1)x＋a0，然后再计算v1＝anx＋an－1，v2＝v1x＋an－2，v3＝v2x＋an－3，…，vn＝vn－1x＋a0.无论an是不是1，这次的乘法都是要进行的．
[正解] 由上分析可知，共做了5次乘法，5次加法．