《人教高中数学必修三课件131算法案例新知探求》由会员分享，可在线阅读，更多相关《人教高中数学必修三课件131算法案例新知探求（56页珍藏版）》请在金锄头文库上搜索。
1、1.3算法案例 第1课时辗转相除法与更相减损术、 秦九韶算法,1.理解辗转相除法与更相减损术的含义,了解执行过程. 2.掌握秦九韶算法的计算过程,了解它在数学计算中的应用. 3.进一步体会算法的基本思想.,1.辗转相除法 (1)作用:是用于求_的一种方法,这 种算法由欧几里得在公元前300年左右首先提出,因而又叫 _. (2)算法步骤: 第一步,给定两个正整数m,n. 第二步,计算m除以n所得的余数r. 第三步,m=n,n=r. 第四步,若_,则m,n的最大公约数等于m;否则,返回第二步.,两个正整数的最大公约数,欧几里得算法,r=0,2.更相减损术 (1)作用:是我国古代数学专著_中介绍的一
2、种求 两个数最大公约数的方法. (2)算法步骤: 第一步,任意给定两个正整数,判断它们是否都是_.若是, 用2约简;若不是,执行第二步. 第二步,以较大的数_较小的数,接着把所得的差与较小的 数比较,并以_减_.继续这个操作,直到所得的差与减 数_为止,则这个数(等数)或这个数与约简的数的乘积就 是所求的最大公约数.,九章算术,偶数,减去,大数,小数,相等,3.秦九韶算法 把一个n次多项式f(x)=anxn+an-1xn-1+a1x+a0改写成如下形 式:f(x)=(anx+an-1)x+an-2)x+a1)x+a0, 求多项式的值时,首先计算_一次多项式的值, 即v1=_,然后由内向外逐层计
3、算一次多项式的值,即v2=_, v3=_, vn=_, 这样,求n次多项式f(x)的值就转化为求_的值.,最内层括号内,anx+an-1,v1x+an-2,v2x+an-3,vn-1x+a0,n个一次多项式,1.辗转相除法可解决下列问题中的() A.求两个正整数的最大公约数 B.多项式求值 C.求两个正整数的最小公倍数 D.排序问题 【解析】选A.辗转相除法可以求两个正整数的最大公约数.,2.用更相减损术可求得78与36的最大公约数是() A.24B.18C.12D.6 【解析】选D.先用2约简得39,18;然后辗转相减得39-18=21, 21-18=3,18-3=15,15-3=12,12
4、-3=9,9-3=6,6-3=3.所以所求的最大公约数为32=6.,3.运算速度快是计算机一个很重要的特点,而算法好坏的一个重要标志是. 【解析】运算次数多少决定计算速度,故运算次数是算法好坏的重要标志. 答案:运算次数,4.求多项式的值时,首先计算最内层括号内一次多项式的值,然后由内向外逐层计算一次多项式的值.这样通过一次式的反复运算,逐步得出高次多项式的值的方法称作. 【解析】根据秦九韶算法的步骤,是秦九韶算法. 答案:秦九韶算法,5.用更相减损术求294和84的最大公约数时,第一步是. 【解析】由于294和84都是偶数,先用2约简. 答案:用2约简,一、辗转相除法与更相减损术 根据辗转相
5、除法与更相减损术求两个正整数最大公约数的步骤,探究下列问题: 探究1:(1)用辗转相除法可以求两个正整数m,n的最大公约数,那么用什么逻辑结构来设计算法?其算法步骤如何设计?,提示:用循环结构设计算法,算法如下: 第一步,给定两个正整数m,n(mn). 第二步,计算m除以n所得的余数r. 第三步,m=n,n=r. 第四步,若r=0,则m,n的最大公约数等于m;否则,返回第二步.,(2)该算法的程序框图如何表示?该程序框图对应的程序如何表述?,提示:程序框图:,程序: INPUTm,n DO r=m MOD n m=n n=r LOOP UNTILr=0 PRINTm END,(3)如果用当型循
6、环结构设计算法,正整数m,n的最大公约数的程序框图和程序分别如何表示?,提示:程序框图:,程序: INPUTm,n WHILE n0 r=m MOD n m=n n=r WEND PRINTm END,探究2:(1)用更相减损术可以求两个正整数m,n的最大公约数,那么用什么逻辑结构来构造算法?其算法步骤如何设计? 提示:用循环结构设计算法,算法如下: 第一步,任意给定两个正整数m,n(mn). 第二步,设计m-n所得的差k. 第三步,比较n与k的大小,其中大者用m表示,小者用n表示. 第四步,若m=n,则m,n的最大公约数等于m;否则,返回第二步.,(2)该算法的程序框图如何表示?该程序框图对
7、应的程序如何表述? 提示:程序框图:,程序: INPUT m,n WHILE mn k=m-n IF nk THEN m=n n=k ELSE m=k END IF WEND PRINT m END,【探究总结】辗转相除法与更相减损术概念的关注点 (1)辗转相除法与更相减损术有着相同的算法依据,但要注意运算过程的差别,辗转相除法的上一次运算的除数和余数分别作为下一次运算的被除数和除数,其结果直至余数为零得出.更相减损术在上一次运算结束后,比较减数和差的大小,将大的作为下一次运算的被减数,小的作为减数,直至出现相等数时得到结果.,(2)两者主要区别在于,辗转相除法进行的是除法运算,即辗转相除,更
8、相减损术进行的是减法运算,即辗转相减,但其实质都是一个不断的递推过程. (3)两者在算法设计上有一个重要的区别点,辗转相除法,下一次进行相除时,由上一次的除数和余数直接相除即可.而更相减损术下一次相减前必须有一个判断大小的过程,以区别谁做被减数. (4)用更相减损术求两正整数的最大公约数时,若两数为偶数,可先约去2,这时莫忘记求得的相等两数乘以约简的数才是所求最大公约数.,二、秦九韶算法 根据秦九韶算法的含义和步骤探究下列各题: 探究1:秦九韶算法的实质是什么? 提示:秦九韶算法的实质是:求多项式f(x)=anxn+an-1xn-1 +a1x+a0的值时,转化为求n个一次多项式的值,共进行n次
9、乘法运算和n次加法运算.这种算法的运算次数较少,是多项式求值比较先进的算法.,探究2:依据秦九韶算法的过程填空: 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=, v2=v1x+an-2, v3=v2x+an-3, vn=. 答案:anx+an-1vn-1x+a0,【探究总结】秦九韶算法的算法特点 秦九韶算法是多项式求值的优秀算法,其特点是: (1)化高次多项式求值为一次多项式求值. (2)减少了运算次数,提
10、高了效率. (3)步骤重复执行,容易用计算机实现.,类型一 辗转相除法和更相减损术的应用 1.下列对辗转相除法的说法错误的是() A.辗转相除法与欧几里得算法是两种不同的求最大公约数的方法 B.辗转相除法的基本步骤是用较大的数除以较小的数 C.在对两个数求最大公约数时,除辗转相除法之外还有更相减损术 D.在用辗转相除法时,需要用到循环语句编写程序,2.已知7 163=20934+57,209=573+38,57=381+19, 38=192.根据上述一系列等式,可确定7 163和209的最大公约数是() A.57B.3C.19D.34 3.用辗转相除法求80和36的最大公约数,并用更相减损术检
11、验所得结果.,【解题指南】1.结合辗转相除法的含义来判断. 2.根据算法过程,只需看最后一个算式38=192. 3.将80作为大数,36作为小数,执行辗转相除法和更相减损术的步骤即可.,【自主解答】1.选A.辗转相除法是由欧几里得在公元前300年左右首先提出的.B,C,D都正确. 2.选C.由38=192,则19是7 163和209的最大公约数. 3.用辗转相除法: 80=362+8, 36=84+4, 8=42+0. 故80和36的最大公约数是4.,用更相减损术检验:先用4约简得20和9, 20-9=11, 11-9=2, 9-2=7, 7-2=5, 5-2=3, 3-2=1, 2-1=1.
12、 故80和36的最大公约数是4.,【延伸探究】题3中条件不变,求这两个数的最小公倍数是多少? 【解析】已知最大公约数是4,从而80和36的最小公倍数是80364=720.,【规律总结】辗转相除法和更相减损术求最大公约数的注意点 (1)辗转相除法是当大数被小数除尽时,结束除法运算,较小的数就是最大公约数. (2)更相减损术是当大数减去小数的差等于小数时停止减法,较小的数就是最大公约数.,【变式训练】 (1)用辗转相除法求288与123的最大公约数. (2)用更相减损术求57与93的最大公约数. (3)求567与405的最小公倍数.,【解析】(1)288=1232+42,123=422+39, 4
13、2=391+3,39=313, 所以288和123的最大公约数是3. (2)(93,57)(36,57)(36,21)(15,21)(15,6)(9,6)(3,6)(3,3), 所以57与93的最大公约数是3. (3)567=4051+162 405=1622+81 162=812+0 所以81是567与405的最大公约数, 从而567与405的最小公倍数为56740581=2 835.,类型 二 用秦九韶算法求多项式的值 1.秦九韶算法与直接计算相比较,下列说法错误的是() A.秦九韶算法与直接计算相比,大大减少了做乘法的次数,使计算量减小,逻辑结构简单 B.秦九韶算法减少做乘法的次数,在计
14、算机上也就加快了计算的速度 C.秦九韶算法减少做乘法的次数,在计算机上也就降低了计算的速度 D.秦九韶算法避免对自变量x单独做幂的计算,而是与系数一起逐次增长幂次,从而可提高计算的速度,2.设计程序框图,用秦九韶算法求多项式的值,要选用的结构 是() A.顺序结构 B.条件结构 C.循环结构 D.以上都有 3.已知一个5次多项式为f(x)=4x5-3x3+2x2+5x+1,用秦九韶算法求这个多项式当x=2时的值.,【解题指南】1.根据秦九韶算法的过程特点可以得到答案. 2.设计程序框图,需要输入、计算和判断,然后多次循环,故三种结构都需要. 3.把所给的多项式写成关于x的一次函数的形式,依次写
15、出,得到最后结果,从里到外进行运算,得到要求的值.,【自主解答】1.选C.秦九韶算法减少做乘法的次数,在计算机上也就提高了计算的速度. 2.选D.设计程序框图需先输入相关量,中间判断计算次数,决定是否继续循环,故三种常用的结构都需要. 3.由f(x)=(4x+0)x-3)x+2)x+5)x+1,v0=4. v1=42+0=8 v2=82-3=13 v3=132+2=28 v4=282+5=61 v5=612+1=123 故这个多项式当x=2时的值为123.,【规律总结】利用秦九韶算法计算多项式的值的策略 (1)正确地将多项式改写,若在多项式中有几项不存在,可将这些项的系数看成0,即把这些项看做
16、0 xn. (2)由内向外逐次计算. (3)每一步计算结果准确.由于下一次计算用到上一次计算的结果,应认真、细致地计算每一步.,【变式训练】求多项式f(x)=x5+5x4+10 x3+10 x2+5x+1当x=-2时的值. 【解题指南】先改写多项式,再由内向外计算.,【解析】f(x)=x5+5x4+10 x3+10 x2+5x+1 =(x+5)x+10)x+10)x+5)x+1. 而x=-2,所以有: v0=1,v1=v0 x+a4=1(-2)+5=3, v2=v1x+a3=3(-2)+10=4, v3=v2x+a2=4(-2)+10=2, v4=v3x+a1=2(-2)+5=1, v5=v4x+a0=1(-2)+1=-1, 即f(-2)=-1.,【拓展类型】求三个数的最大公约数 1.三个正整数分别是a,b,c
