湘教版高中数学必修5算法案例.ppt

课前探究学习 课堂讲练互动 【课标要求】 1．理解辗转相除法与二分法及中国剩余定理的含义，了解其执行过程． 2．掌握秦九韶算法的计算过程，并了解它提高计算效率的实质． 算法案例 自学导引 1．辗转相除法是用于求　　　　　　　　　的一种方法． 所谓辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数．若余数　　　　，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数　　　　，则这时的小数就是原来两个数的最大公约数． 两个数的最大公约数 不为零 除尽 x0 x0 (a，x0) 4．秦九韶算法是我国南宋数学家 在他的代表作 中提出的一种用于计算 的方法． 对于任意一元n次多项式，秦九韶算法的步骤是： 首先将多项式改写为 P(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. 令vk＝(…(anx＋an－1)x＋…＋an－(k－1))x＋an－k， 秦九韶 《数学九章》 一元n次多项式的值 an vk－1x＋ a n－k 说明：①计算时，首先计算最内层的括号，然后由内向外逐层计算，直到最外层的一个括号，然后加上常数项． ②利用上面方法求一元n次多项式值的计算量仅需n次乘法和n次加法． 自主探究 1．任意给定两个正整数，用辗转相除法和更相减损术是否都可以求它们的最大公约数？ 答案　是．更相减损术与辗转相除法都能在有限步内结束，故均可以用来求两个正整数的最大公约数． 2．秦九韶算法与直接计算相比有什么优缺点？ (2)秦九韶算法：利用秦九韶算法求上述f(5)时只需要进行4次乘法运算和5次加减运算即可．与直接计算相比大大节省了乘法运算的次数，还避免了对自变量x单独做幂的计算，而与系数一起逐步增长幂次，从而提高计算的精度．又如利用秦九韶算法求多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0的值时，通过转化把乘法运算的次数减少到最多n次，加减运算最多n次． 预习测评 1．用辗转相除法求36与134的最大公约数，第一步是(　　)． A．134－36＝98 B．134＝3×36＋26 C．先除以2，得到18与67 D．134÷36＝3(余26) 答案　B 2．求数320和2 400的最大公约数为________． 答案　160 答案　an－k　循环 要点阐释 1．辗转相除法 (1)所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数．若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时的较小的数就是原来两个数的最大公约数． (2)算法步骤：(以求两正整数a，b的最大公约数为例) S1：输入两个正整数a，b(ab)； S2：把a÷b的余数赋予r； S3：如果r≠0，那么把b赋予a，把r赋予b，转到第二步，否则转到第四步； S4：输出最大公约数b. (3)程序框图如图所示：　　　　　(4)程序： 程序框图如图 伪代码： 程序框图，如图 伪代码： 4．秦九韶算法 (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. S1：计算最内层anx＋an－1的值，将anx＋an－1的值赋给一个变量v1(为方便将an赋予变量v0)； S2：计算(anx＋an－1)x＋an－2的值，可以改写为v1x＋an－2，将v1x＋an－2的值赋给一个变量v2； 依次类推，即每一步的计算之后都赋予一个新值vk，即从最内层的括号到最外层括号的值依次赋予变量v1，v2，…，vk，…，vn，第n步所求值vn＝vn－1x＋a0即为所求多项式的值． 典例剖析 题型一　最大公约数的求法 【例1】 用辗转相除法求下列两组数的最大公约数，并用更相减损术检验你的结果． (1)80,36；(2)294,84. 解　(1)80＝36×2＋8， 36＝8×4＋4,8＝4×2＋0， 即80与36的最大公约数是4. 验证： 80÷2＝40　36÷2＝18 40÷2＝20　18÷2＝9 20—9＝11　11－9＝2 9－2＝7　7－2＝5 5－2＝3　3－2＝1 2－1＝1　1×2×2＝4 所以80与36的最大公约数