资源描述：
《2017学年数学必修三：1.3算法案例1.3.1.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1.3算法案例第1课时 辗转相除法与更相减损术、秦九韶算法1.理解辗转相除法与更相减损术的含义,了解执行过程.2.掌握秦九韶算法的计算过程,了解它在数学计算中的应用.3.进一步体会算法的基本思想.1.辗转相除法(1)作用:是用于求_______________________的一种方法,这种算法由欧几里得在公元前300年左右首先提出,因而又叫_____________.(2)算法步骤:第一步,给定两个正整数m,n.第二步,计算m除以n所得的余数r.第三步,m=n,n=r.第四步,若____,则m,n的最大公约数等于m;否则,返回
2、第二步.两个正整数的最大公约数欧几里得算法r=02.更相减损术(1)作用:是我国古代数学专著_____________中介绍的一种求两个数最大公约数的方法.(2)算法步骤:第一步,任意给定两个正整数,判断它们是否都是_____.若是,用2约简;若不是,执行第二步.第二步,以较大的数_____较小的数,接着把所得的差与较小的数比较,并以_____减_____.继续这个操作,直到所得的差与减数_____为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.《九章算术》偶数减去大数小数相等3.秦九韶算法把一个n次多项式f
3、(x)=anxn+an-1xn-1+…+a1x+a0改写成如下形式:f(x)=(…((anx+an-1)x+an-2)x+…+a1)x+a0,求多项式的值时,首先计算_____________一次多项式的值,即v1=_______,然后由内向外逐层计算一次多项式的值,即v2=_______,v3=_______,…vn=_______,这样,求n次多项式f(x)的值就转化为求______________的值.最内层括号内anx+an-1v1x+an-2v2x+an-3vn-1x+a0n个一次多项式1.辗转相除法可解决下列问题中的
4、()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-3=9,9-3=6,6-3=3.所以所求的最大公约数为3×2=6.3.运算速度快是计算机一个很重要的特点,而算法好坏的一个重要标志是.【解析】运算次数多少决定计算速度,故运算次数是算法好坏的
5、重要标志.答案:运算次数4.求多项式的值时,首先计算最内层括号内一次多项式的值,然后由内向外逐层计算一次多项式的值.这样通过一次式的反复运算,逐步得出高次多项式的值的方法称作.【解析】根据秦九韶算法的步骤,是秦九韶算法.答案:秦九韶算法5.用更相减损术求294和84的最大公约数时,第一步是.【解析】由于294和84都是偶数,先用2约简.答案:用2约简一、辗转相除法与更相减损术根据辗转相除法与更相减损术求两个正整数最大公约数的步骤,探究下列问题:探究1:(1)用辗转相除法可以求两个正整数m,n的最大公约数,那么用什么逻辑结构来设计
6、算法?其算法步骤如何设计?提示:用循环结构设计算法,算法如下:第一步,给定两个正整数m,n(m>n).第二步,计算m除以n所得的余数r.第三步,m=n,n=r.第四步,若r=0,则m,n的最大公约数等于m;否则,返回第二步.(2)该算法的程序框图如何表示?该程序框图对应的程序如何表述?提示:程序框图:程序:INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND(3)如果用当型循环结构设计算法,正整数m,n的最大公约数的程序框图和程序分别如何表示?提示:程序框图:程序:INPUTm,nWHILEn
7、>0r=mMODnm=nn=rWENDPRINTmEND探究2:(1)用更相减损术可以求两个正整数m,n的最大公约数,那么用什么逻辑结构来构造算法?其算法步骤如何设计?提示:用循环结构设计算法,算法如下:第一步,任意给定两个正整数m,n(m>n).第二步,设计m-n所得的差k.第三步,比较n与k的大小,其中大者用m表示,小者用n表示.第四步,若m=n,则m,n的最大公约数等于m;否则,返回第二步.(2)该算法的程序框图如何表示?该程序框图对应的程序如何表述?提示:程序框图:程序:INPUTm,nWHILEm<>nk=m-nIFn
8、>kTHENm=nn=kELSEm=kENDIFWENDPRINTmEND【探究总结】辗转相除法与更相减损术概念的关注点(1)辗转相除法与更相减损术有着相同的算法依据,但要注意运算过程的差别,辗转相除法的上一次运算的除数和余数分别作为下一次运算的被除数和除数,其
