§1.3算法案例（一）

第一章算法初步,1.3算法案例（一）,1.理解辗转相除法与更相减损术中的数学原理，并能根据这些原理进行算法分析；2.了解秦九韶算法及利用它提高计算效率的本质；3.对简单的案例能设计程序框图并写出算法程序.,问题导学,题型探究,达标检测,学习目标,知识点一求两个数的最大公约数的算法,答案,问题导学新知探究点点落实,思考注意到8251610512146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？,答案显然8251与6105的公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数.,一般地，求两个数的最大公约数有2种算法：1.辗转相除法(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的的古老而有效的算法.(2)辗转相除法的算法步骤第一步，给定.第二步，计算.第三步，.第四步，若r0，则m，n的最大公约数等于；否则，返回.,答案,最大公约数,两个正整数m，n(mn),m除以n所得的余数r,mn，nr,m,第二步,2.更相减损术的运算步骤第一步，任意给定两个正整数，判断它们是否都是.若是，用约简；若不是，执行.第二步，以的数减去的数，接着把所得的差与的数比较，并以大数减小数，继续这个操作，直到所得的数为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.,答案,偶数,2,第二步,较大,较小,较小,相等,答案,知识点二求n次多项式f(x)anxnan1xn1a1xa0的值的算法,思考衡量一个算法是否优秀的重要参数是速度.把多项式f(x)x5x4x3x2x1变形为f(x)(x1)x1)x1)x1)x1，然后求当x5时的值，为什么比常规逐项计算省时？,答案从里往外计算，充分利用已有成果，可减少重复计算.,秦九韶算法的一般步骤：把一个n次多项式f(x)anxnan1xn1a1xa0改写成如下形式：(anxan1)xan2)xa1)xa0，求多项式的值时，首先计算一次多项式的值，即v1，然后由内向外逐层计算一次多项式的值，即,最内层括号内,anxan1,v2，v3，vn，这样，求n次多项式f(x)的值就转化为求的值.,答案,返回,v1xan2,v2xan3,vn1xa0,n个一次多项式,类型一辗转相除法的现代实现,解析答案,反思与感悟,例1试设计用辗转相除法可以求两个正整数m，n的最大公约数的程序框图和程序.,题型探究重点难点个个击破,解析答案,解(1)算法：第一步，给定两个正整数m，n(mn).第二步，计算m除以n所得的余数r.第三步，mn，nr.第四步，若r0，则m，n的最大公约数等于m；否则，返回第二步.(2)程序框图：,反思与感悟,(3)程序：,INPUTm，nDOrmMODnmnnrLOOPUNTILr0PRINTmEND,反思与感悟,利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数.,反思与感悟,跟踪训练1用辗转相除法求261和319的最大公约数.,解析答案,解辗转相除法：3192611(余58)，261584(余29)，58292(余0)，所以319与261的最大公约数为29.,类型二更相减损术,解析答案,反思与感悟,例2试用程序框图和程序表述更相减损术.,解程序框图：,程序：,INPUTm，nWHILEmnkmnIFnkTHENmnnkELSEmkENDIFWENDPRINTmEND,反思与感悟,利用更相减损术求两个正整数的最大公约数的一般步骤是首先判断两个正整数是否都是偶数.若是，用2约简，也可以不除以2，直接求最大公约数，这样不影响最后结果.,跟踪训练2用更相减损术求261和319的最大公约数.,解31926158,26158203，20358145,1455887，875829,582929，29290，所以319与261的最大公约数是29.,解析答案,类型三秦九韶算法的基本思想,解析答案,反思与感悟,例3已知一个5次多项式为f(x)4x52x43.5x32.6x21.7x0.8，用秦九韶算法求这个多项式当x5时的值.,解将f(x)改写为f(x)(4x2)x3.5)x2.6)x1.7)x0.8，由内向外依次计算一次多项式当x5时的值：v04；v145222；v22253.5113.5；v3113.552.6564.9；v4564.951.72826.2；v52826.250.814130.2.当x5时，多项式的值等于14130.2.,反思与感悟,反思与感悟,秦九韶算法之所以优秀，一是其对所有多项式求值都适用，二是充分利用已有计算成果，效率更高.,跟踪训练3用秦九韶算法求多项式f(x)7x76x65x54x43x32x2x当x3时的值.,解f(x)(7x6)x5)x4)x3)x2)x1)x，所以有v07，v173627，v2273586，v38634262，v426233789，v5789322369，v62369317108，v77108321324.故当x3时，多项式f(x)7x76x65x54x43x32x2x的值为21324.,解析答案,返回,1.下列说法中正确的个数为()辗转相除法也叫欧几里得算法；辗转相除法的基本步骤是用较大的数除以较小的数；求最大公约数的方法，除辗转相除法之外，没有其他方法；编写辗转相除法的程序时，要用到循环语句.A.1B.2C.3D.4,C,达标检测,1,2,3,4,5,解析、正确，错误.,解析答案,2.关于利用更相减损术求156和72的最大公约数，下列说法正确的是()A.都是偶数必须约简B.可以约简，也可以不约简C.第一步作差为1567284，第二步作差为728412D.以上皆不正确,1,2,3,4,5,B,答案,3.用辗转相除法求210与98的最大公约数需作除法的次数为()A.1B.2C.3D.4,1,2,3,4,5,B,答案,4.用更相减损术求147和42的最大公约数是()A.6B.7C.21D.42,C,1,2,3,4,5,答案,1,2,3,4,5,5.用秦九韶算法计算多项式f(x)6x65x54x43x32x2x7在x0.4时的值时，需做加法和乘法的次数的和为()A.10B.9C.12D.8,C,解析f(x)(6x5)x4)x3)x2)x1)x7，加法6次，乘法6次，6612次，故选C.,解析答案,规律与方法,1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的