1.3
算法案例
第一课时 辗转相除法 与更相减损术、秦九韶算法
知识能力目标引航 1.理解辗转相除法与更相减损术的含义,了解其执行过程,并会求最 大公约数. 2.掌握秦九韶算法的计算过程,了解它提高计算效率的实质,并会求 多项式的值. 3.进一步体会算法的基本思想.
1.辗转相除法与更相减损术 (1)辗转相除法. ①算法步骤: 第一步,给定两个正整数 m,n. 第二步,计算 m 除以 n 所得的余数 r. 第三步,m=n,n=r. 第四步,若 r=0,则 m,n 的最大公约数等于 m;否则返回第二步. ②程序框图如图所示.
求两个正整数的最大公约数的问题,可以用辗转相除法,也可以 用更相减损术.用辗转相除法,即根据 a=nb+r 这个式子,反复相除,直 到 r=0 为止;用更相减损术,即根据 r=|a-b|这个式子,反复相减,直到 r=0 为止.
题型二 求多项式的值 【例题 2】 用秦九韶算法求多项式 f(x)=7x7+6x6+5x5+4x4+3x3+2x2+x 当 x=3 时的值. 分析:解决本题首先需要将原多项式化成 f(x)=((((((7x+6)x+5)x+4)x+3)x+2)x+1)x 的形式,其次再弄清 v0,v1,v2,…,v7 分别是多少,再针对这些式子进行计算.
秦九韶算法的关键在于把 n 次多项式转化为一次多项式,注意 体会递推的实现过程,实施运算时要由内向外,一步一步执行.
题型三
易错辨析
【例题 3】已知 f(x)=3x4+2x2+4x+2,利用秦九韶算法求 f(-2)的值. 错解:f(x)=((3x2+2)x+4)x+2, v1=3×(-2)2+2=14; v2=14×(-2)+4=-24; v3=-24×(-2)+2=50. 故 f(-2)=50. 错因分析:所求 f(-2)的值是正确的,但是错解中没有抓住秦九韶 算法原理的关键,正确改写多项式,并使每一次计算只含有 x 的一次 项. 正解:f(x)=3x4+0·x3+2x2+4x+2=(((3x+0)x+2)x+4)x+2, v1=3×(-2)+0=-6; v2=-6×(-2)+2=14; v3=14×(-2)+4=-24; v4=-24×(-2)+2=50. 故 f(-2)=50.
