§1.3算法案例第一课时辗转相除法与更相减损术秦九韶算､法自学导引1.理解辗转相除法与更相减损术的含义,了解执行过程.2.掌握秦九韶算法的计算过程,了解它在数学计算中的应用.3.进一步体会算法的基本思想.课前热身1.辗转相除法是用于求_____________________的一种方法,这种算法由欧几里得在公元前300年左右首先提出,因而又叫________.2.所谓辗转相除法,就是对于给定的两个数,用________除以________,若余数不为零,则将___________构成新的一对数,继续上面的除法,直到大数被小数除尽,则这时________就是原来两个数的最大公约数.两个正整数的最大公约数欧几里得算法较大的数较小的数除数与余数除数3.更相减损术是我国古代数学专著__________中介绍的一种求两数最大公约数的方法.其基本过程是:对于给定的两数,用___________,接着把所得的________与________比较,并以大数减小数,继续这个操作,直到所得的数________为止,则这个数就是所求的最大公约数.4.秦九韶算法是我国南宋数学家________在他的代表作___________中提出的一种用于计算一元n次多项式的值的方法.《九章算术》大数减小数差减数相等秦九韶《数书九章》名师讲解1.辗转相除法(1)辗转相除的原理.设m,n是两个整数(不妨设m>n),用m除以n,若商为q1,余数为r1(0≤r1n>r1>r2>…,所以到某一步必然有ri=ri+1·qi+2,即ri恰能被ri+1整除,这时ri+1是ri和ri+1的公约数,它也必然是ri-1和ri,ri-2和ri-1,…,r1与r2,n和r1,m和n的最大公约数.(2)辗转相除法的算法分析.由以上辗转相除法的原理可以发现,辗转相除法的基本步骤是用较大的数除以较小的数,考虑到算法中的赋值语句可以对同一变量多次赋值,我们可以把较大的数用变量m表示,把较小的数用变量n表示,这样式子m=n·q+r(0≤r0a=bb=rr=aMODbWENDPRINTbEND2.更相减损术(1)更相减损术求两数最大公约数的过程与算法设计:对于给定的两个数,用较大的数减去较小的数,接着把得到的差与较小的数比较,用这时两个数中的较大的数减去较小的数,继续这样的操作(大数减小数),直到所得的数相等为止,那么这个数(等数)就是所求的最大公约数.显然,上述过程中大数减去小数是一个重复执行的过程,因此只需将大数赋给变量m,小数赋给变量n,那么m-n就可以通过循环结构实现算法.(2)更相减损术求最大公约数的程序设计:INPUT“a,b”;a,bWHILEa<>bIFa>bTHENa=a-bELSEb=b-aENDIFWENDPRINTaEND3.秦九韶算法(1)秦九韶算法过程分析:设Pn(x)=anxn+an-1xn-1+…+a1x+a0,将其改写为Pn(x)=(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令vk=(…((anx+an-1)x+an-2)x+…+an-(k-1))x+an-k,01,k1,2,,,n.nkknkvavvxa则有其中这样我们便可由a0依次求出v1,v2,…,vn:v1=v0x+an-1,v2=v1x+an-2,v3=v2x+an-3,…,vn=vn-1x+a0.显然,用秦九韶算法求n次多项式的值时只需做n次乘法和n次加法运算.(2)秦九韶算法程序框图:以5次多项式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0当x=x0时为例,如下图:典例剖析题型一求两个数的最大公约数例1:分别用辗转相除法和更相减损术逐步列出求(1)98和63;(2)8251和6105的最大公约数的步骤,你有什么发现?对优劣作出评判.分析:辗转相除法是做两个数的带余除法,更相减损术是做两个数的减法.解:(1)98和63辗转相除法S198=63×1+35,S263=35×1+28,S335=28×1+7,S428=4×7,最大公约数为7.更相减损术S198-63=35,S263-35=28,S335-28...
