2019_2020学年高中数学第一章算法初步1.3算法案例课件新人教A版必修3.pptx

《2019_2020学年高中数学第一章算法初步1.3算法案例课件新人教A版必修3.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.3　算法案例[目标导航]课标要求1.理解辗转相除法与更相减损术的含义,理解其算法的执行过程.2.理解秦九韶算法的计算过程及程序设计.3.理解进位制的概念,能进行不同进位制之间的转换,了解进位制的程序设计.素养达成通过算法案例的学习,进一步理解算法的基本思想,提高使用算法解决问题的能力.新知导学·素养养成1.求两个正整数的最大公约数的算法(1)辗转相除法(欧几里得算法)的算法步骤:第一步,给定.第二步,计算.第三步,.第四步,若r=0,则m,n的最大公约数等于;否则返回.(2)更相减损术的算法步骤第一步,任意给定两个正整数,判断它们是否都是.若是,;若不

2、是,执行.第二步,以的数减去的数,接着把所得的差与的数比较,并以大数减小数,继续这个操作,直到所得的数为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.两个正整数m,nm除以n所得的余数rm=n,n=rm第二步偶数用2约简第二步较大较小较小相等思考1:辗转相除法与更相减损术有何异同?答案:两种方法辗转相除法更相减损术计算法则除法减法终止条件余数为0减数与差相等最大公约数的选取最后一步中的除数最后一步中的减数计算次数步骤较少,运算复杂步骤较多,运算简单相同点同为求两个正整数最大公约数的方法,都是递归过程2.秦九韶算法把一个n次多项式f(x)

3、=anxn+an-1xn-1+…+a1x+a0改写成如下形式:f(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.求多项式的值时,首先计算最内层括号内一次多项式的值,即v1=anx+an-1,然后由内向外逐层计算一次多项式的值,即v2=v1x+an-2,v3=v2x+an-3,…vn=vn-1x+a0.这样,求n次多项式f(x)的值就转化为求n个一次多项式的值.思考2

4、:秦九韶算法的步骤是什么?答案:3.进位制(1)概念:进位制是为了而约定的记数系统,“满几进一”就是几进制,几进制的基数就是.(2)不同进位制之间的互化:①k进制化为十进制的方法:anan-1…a1a0(k)=(an,an-1,…,a1,a0∈N,0

5、满二进一,如1+1=10.(2)八进制:①使用0,1,2,3,4,5,6,7八个不同的数字;②满八进一,如7+1=10.(3)十六进制:①使用0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F这十六个不同的数码,其中A,B,C,D,E,F分别代表十进制中的10,11,12,13,14,15;②满十六进一,如F+1=2+E=10.课堂探究·素养提升题型一　求最大公约数[例1]分别用辗转相除法和更相减损术求779与209的最大公约数.解:法一辗转相除法:779=209×3+152,209=152×1+57,152=57×2+38,57=38×1+1

6、9,38=19×2.所以,779与209的最大公约数为19.法二更相减损术法:779-209=570,570-209=361,361-209=152,209-152=57,152-57=95,95-57=38,57-38=19,38-19=19.所以779和209的最大公约数为19.方法技巧求两个正整数的最大公约数的问题,可以用辗转相除法,也可以用更相减损术.即时训练1-1:(2019·安徽省屯溪第一中学月考)数612和486的最大公约数是(　　)(A)12(B)14(C)16(D)18解析:612-486=126,486-126=360,360-126=

7、234,234-126=108,126-108=18,108-18=90,90-18=72,72-18=54,54-18=36,36-18=18.因此612与486的最大公约数是18.故选D.解:f(x)=(((((6x+5)x+4)x+3)x+2)x+1)x,当x=2时,有v0=6,v1=6×2+5=17,v2=17×2+4=38,v3=38×2+3=79,v4=79×2+2=160,v5=160×2+1=321,v6=321×2=642,故当x=2时,多项式f(x)=6x6+5x5+4x4+3x3+2x2+x的值为642.题型二　秦九韶算法[例2]用秦

8、九韶算法求多项式f(x)=6x6+5x5+4x4+3x3+2x2+