11.4算法案例_课件1-湘教版数学必修5（22张PPT）

算法案例
学习目标
1．通过案例，进一步体会算法的思想；
2．理解并能利用案例中的算法解决具体问题．

课堂互动讲练
　算法案例
课前自主学案
课前自主学案
温故夯基
1．编写算法常用的语句有输入语句、_________、赋值语句、_________、循环语句，对应着_____结构、条件结构、_____结构．
2．在两个正数的所有公约数中最大的一个公约数为它们的___________．
输出语句
条件语句
顺序
循环
最大公约数
知新益能
1．辗转相除法
伪代码如下：
a MOD b
2．秦九韶算法
伪代码如下：
问题探究
1．用秦九韶算法求x＝2时，f(x)＝x3＋3x2＋x＋1的值第一个一次多项式的值为多少？
提示：由秦九韶算法知f(x)＝[(x＋3)x＋1]x＋1.
∴由内到外第一个一次多项式的值为2＋3＝5.
2．“秦九韶算法”的实质是什么？
提示：其实质是通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，最多只需做n次乘法和n次加法即可．
课堂互动讲练
辗转相除法
考点突破
辗转相除法的操作过程是先用两个数中较大的数除以较小的数，得商和余数；再用除数除以余数，重复操作，直到出现余数为零，易出错的地方是用商除以余数，要特别注意．
利用辗转相除法求294和84的最大公约数．
【思路点拨】　利用辗转相除法，依据m＝nq＋r，反复执行，直到r＝0为止．
【解】　294＝84×3＋42,84＝42×2，即294与84的最大公约数为42.
例1
【名师点评】　利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．
变式训练1　利用辗转相除法求46,115和276的最大公约数的最大公约数．
解：求三个数的最大公约数，可以先求两个数的最大公约数，然后求第三个数与前两个数的最大公约数．
276＝2×115＋46,115＝2×46＋23,46＝23×2
所以276与115的最大公约数为23.
又46与23的最大公约数为23，所以46、115和276的最大公约数为23.
用二分法求方程的近似解或函数的零点可以设计程序用计算机来完成．
二分法
写出用二分法求方程x2－2＝0的一个正的近似解(误差不超过0.005)的算法．
例2
【思路点拨】　令f(x)＝x2－2，确定有解区间[1,2]，用二分法确定符合限制条件的解即可．
【名师点评】　用二分法求方程的近似解的步骤:
(1)画草图探索解所在的区间；(2)用二分法求符合限制条件的解；(3)编制程序用计算机完成．
变式训练2　写出用二分法求方程x3－2x－3＝0在区间[1,2]内的一个近似解(误差不超过0.001)的一个算法．
秦九韶算法
利用秦九韶算法将f(x)改写成如下形式f(x)＝(…
((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0，其计算步骤为：先计算v1＝an·x＋an－1，再计算v2＝v1·x＋an－2，每次都是把上一次的结果乘以x再与下一个系数相加，其计算量为乘法n次，加法n次．
例3
用秦九韶算法计算多项式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.
【名师点评】　利用秦九韶算法计算多项式的值关键是能正确地将所给多项式改写，然后由内向外逐次计算，由于后项计算需用到前项的结果，故应认真、细心，确保中间结果的准确性．
变式训练3　用秦九韶算法求多项式f(x)＝5x5－4x4＋3x2＋8x－6，当x＝3时的值．
解：f(x)＝5x5－4x4＋3x2＋8x－6
＝((((5x－4)x＋0)x＋3)x＋8)x－6，
当x＝3时，
v0＝5，
v1＝5×3－4＝11，
v2＝11×3＋0＝33，
v3＝33×3＋3＝102，
v4＝102×3＋8＝314，
v5＝314×3－6＝936.
∴f(3)＝936.
方法感悟
1．辗转相除法是当大数被小数除尽时，结束除法运算，较小的数就是最大公约数．
2．用秦九韶算法可大大降低乘法的运算次数，提高了运算速度．用此方法求值，关键是正确地将所给多项式改写，然后由内向外计算，由于后项计算需用到前项结果，故应认真、细心，确保结果的准确性．