2019-2020学年北师大版必修三 算法的基本思想 学案
2019-2020学年北师大版必修三    算法的基本思想  学案第2页

  228-171=57,171-57=114,

  114-57=57.

  所以228与1 995的最大公约数为57.

  

  求最大公约数的两种方法

  (1)利用辗转相除法求给定的两个数的最大公约数,即利用带余除法,用数对中较大的数除以较小的数,若余数不为零,则将余数和较小的数构成新的数对,再利用带余除法,直到大数被小数除尽,则这时的较小数就是原来两个数的最大公约数.

  (2)利用更相减损术求两个正整数的最大公约数的一般步骤是:第一步判断两个正整数是否都是偶数,若是,用2约简,也可以不除以2,直接求最大公约数,这样不影响最后结果.第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减小数,继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.

  

  

  1.用辗转相除法和更相减损术求1 515与600的最大公约数,需要运算的次数分别为(  )

  A.4,15    B.5,14

  C.5,13 D.4,12

  B [辗转相除法:1 515=600×2+315;600=315×1+285,315=285×1+30,285=30×9+15,30=15×2,故最大公约数为15,且需计算5次.

  用更相减损术:1 515-600=915,915-600=315,600-315=285,315-285=30,285-30=255,255-30=225,225-30=195,195-30=165,165-30=135,135-30=105,105-30=75,75-30=45,45-30=15,30-15=15.故最大公约数为15,且需计算14次.]

  

秦九韶算法   

  【例2】 已知一个5次多项式为f(x)=4x5+2x4+3.5x3-2.6x2+1.7x-0.8,用秦九韶算法求这个多项式当x=5时的值.

  思路点拨:可根据秦九韶算法的原理,将所给的多项式改写,然后由内到外逐次计算.

  [解] 将f(x)改写为f(x)=((((4x+2)x+3.5)x-2.6)x+1.7)x-0.8,

  由内向外依次计算一次多项式,当x=5时的值:

v0=4;