1.3算法案例

§1.回顾算法的三种表示方法：（1）、自然语言（2）、程序框图（3）、程序语言（三种逻辑结构）（五种基本语句）复习引入一、输入语句1、一般格式：INPUT“提示内容”；变量INPUT“x=”；x二、输出语句1、一般格式：PRINT“提示内容”；表达式三、赋值语句1、一般格式：变量=表达式程序框图条件语句的一般格式IF条件THEN语句体(步骤A)ENDIF步骤A满足条件？是否满足条件？步骤A步骤B是否程序框图条件语句的一般格式IF条件THEN语句体1(步骤A)ELSE语句体2(步骤B)ENDIF两种循环语句：循环体满足条件？是否（2）While（当型）循环WHILE条件循环体WENDDO循环体LOOPUNTIL条件（1）Until（直到型）循环循环体满足条件？否是2.思考：小学学过的求两个数的最大公约数的方法？先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.例：求下面两个正整数的最大公约数：（1）求25和35的最大公约数（2）求49和63的最大公约数25（1）5535749（2）77639所以，25和35的最大公约数为5所以，49和63的最大公约数为7例：如何算出8251和6105的最大公约数？新课讲解：一、辗转相除法（欧几里得算法）1、定义：所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。2、步骤:（以求8251和6105的最大公约数的过程为例）第一步用两数中较大的数除以较小的数，求得商和余数:8251=6105×1+2146结论：8251和6105的公约数就是6105和2146的公约数，求8251和6105的最大公约数，只要求出6105和2146的最大公约数就可以了。第二步对6105和2146重复第一步的做法6105=2146×2+1813同理6105和2146的最大公约数也是2146和1813的最大公约数。完整的过程8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0显然37是148和37的最大公约数，也就是8251和6105的最大公约数例：用辗转相除法求225和135的最大公约数225=135×1+90135=90×1+4590=45×2显然45是90和45的最大公约数，也就是225和135的最大公约数思考1：从上面的两个例子中可以看出计算的规律是什么？S1：用大数除以小数S2：除数变成被除数，余数变成除数S3：重复S1，直到余数为0辗转相除法是一个反复执行直到余数等于0才停止的步骤，这实际上是一个循环结构。8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0m=n×q＋r用程序框图表示出右边的过程r=mMODnm=nn=rr=0?是否思考：你能把辗转相除法编成一个计算机程序吗？(1)、算法步骤：第一步：输入两个正整数m,n(mn).第二步：计算m除以n所得的余数r.第三步：m=n,n=r.第四步：若r＝0,则m,n的最大公约数等于m；否则，返回第二步.第五步：输出最大公约数m.(2)、程序框图：开始输入m,nr=mMODnm=nr=0?是否n=r输出m结束(3)、程序：INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND二、更相减损术可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的数和差相等为止，则这个等数或这个数与约简的数的乘积就是所求的最大公约数。（1）、《九章算术》中的更相减损术：1、背景介绍：（2）、现代数学中的更相减损术：2、定义：所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。例:用更相减损术求98与63的最大公约数.解：由于63不是偶数，把98和63以大数减小数，并辗转相减98－63＝3563－35＝2835－28＝728－7＝2121－7＝1414－7＝7所以，98和63的最大公约数等于73、方法：1、用更相减损术求两个正数84与72的最大公约数．练习：思路分析：先约简，再求21与18的最大公约数,然后乘以两次约简的质因数4。2、求324、243、135这三个数的最大公约数。思路分析：求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大公约数的最大公约数即为所求。2、求324、243、135这三个数的最大公约数.27135243324.2713581,022754,2715481,54181135.812433240381243811243324的最大公约数为、、所以，三个数的最大公约数为与则又的最大公约数为与则2、求324、243、135这三个数的最大公约数.27135243324.2713581,272754,275481,5481135.81243324,8181162,16281243,81243324最大公约数为、、所以，三个数的最大公约数为与则的最大公约数为与则(1)、算法步骤第一步：输入两个正整数a,b(ab);第二步：若a不等于b,则执行第三步；否则转到第五步；第三步：把a-b的差赋予r;第四步：如果br,那么把b赋给a,把r赋给b;否则把r赋给a，执行第二步；第五步：输出最大公约数b.***思考：你能根据更相减损术设计程序，求两个正整数的最大公约数吗？(2)、程序框图是否是开始输入a,ba≠b?否输出b结束b=ra=br=a-brb?a=r(3)、程序INPUTa,b=;a,bWHILEabr=a-bIFbrTHENa=bb=rELSEa=rENDIFWENDPRINTbEND比较辗转相除法与更相减损术的区别（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。小结1、求两个数的最大公约数的两种方法分别是（）和（）。2、两个数21672，8127的最大公约数是（）A、2709B、2606C、2703D、2706怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢？计算多项式ｆ(ｘ)=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１当x=5的值算法1：因为ｆ(ｘ)=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１所以ｆ(5)=5５＋5４＋5３＋5２＋5＋１=3125＋625＋125＋25＋5＋１=3906算法2：ｆ(5)=5５＋5４＋5３＋5２＋5＋１=5×(5４＋5３＋5２＋5＋１)＋１=5×(5×(5３＋5２＋5＋１)＋１)＋１=5×(5×(5×(5２+5+１)+１)+１)+１=5×(5×(5×(5×(5+１)+１)+１)+１)+１算法1：因为ｆ(ｘ)=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１所以ｆ(5)=5５＋5４＋5３＋5２＋5＋１=3125＋625＋125＋25＋5＋１=3906算法2：ｆ(5)=5５＋5４＋5３＋5２＋5＋１=5×(5４＋5３＋5２＋5＋１)＋１=5×(5×(5３＋5２＋5＋１)＋１)＋１=5×(5×(5×(5２+5+１)+１)+１)+１=5×(5×(5×(5×(5+１)+１)+１)+１)+１共做了1+2+3+4=10次乘法运算，5次加法运算。共做了4次乘法运算，5次加法运算。《数书九章》——秦九韶算法0111)(axaxaxaxfnnnn设)(xf是一个n次的多项式对该多项式按下面的方式进行改写：0111)(axaxaxaxfnnnn01211)(axaxaxannnn012312))((axaxaxaxannnn0121)))((axaxaxaxannn这是怎样的一种改写方式？最后的结果是什么？0121)))(()(axaxaxaxaxfnnn要求多项式的值，应该先算最内层的一次多项式的值，即11nnaxav然后，由内到外逐层计算一次多项式的值，即212naxvv323naxvv01axvvnn最后的一项是什么？这种将求一个n次多项式f(x)的值转化成求n个一次多项式的值的方法，称为秦九韶算法。算法步骤：第一步：输入多项式次数n、最高次项的系数an和x的值.第二步：将v的值初始化为an，将i的值初始化为n-1.第三步：输入i次项的系数ai第四步：v=vx+ai,i=i-1.第五步：判断i是否小于或等于0，若是，则返回第三步；否则，输出多项式的值v。程序框图：这是一个在秦九韶算法中反复执行的步骤，因此可用循环结构来实现。),,,(nkaxvvavknkkn2110输入ai开始输入n,an,xi0?输出v结束v=vx+aii=i-1YNi=n-1V=an输入ai开始输入n,an,xi0?输出v结束v=vx+aii=i-1YNi=n-1V=anINPUTn=;nINPUTan=;aINPUTx=;xv=ai=n-1WHILEi=0PRINTi=;iINPUTai=;av=v*x+ai=i-1WENDPRINTvEND程序特点：通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，只需做n次乘法和n次加法即可。例1:用秦九韶算法求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.解法一:首先将原多项式改写成如下形式:f(x)=((((2x-5)x-4)x+3)x-6)x+7v0=2v1=v0x-5=2×5-5=5v2=v1x-4=5×5-4=21v3=v2x+3=21×5+3=108v4=v3x-6=108×5-6=534v5=v4x+7=534×5+7=2677所以,当x=5时,多项式的值是2677.然后由内向外逐层计算一次多项式的值,即2-5-43-67x=5105252110510854053426702677所以,当x=5时,多项式的值是2677.原多项式的系数多项式的值.例1:用秦九韶算法求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.解法二:列表22-50-43-60x=5105252512512160560830403034所以,当x=5时,多项式的值是15170.练一练:用秦九韶算法求多项式f(x)=2x6-5x5-4x3+3x2-6x当x=5时的值.解:原多项式先化为:f(x)=2x6-5x5+0×x4-4x3+3x2-6x+0列表21517015170注意:n次多项式有n+1项,因此缺少哪一项应将其系数补0.例2已知一个五次多项式为8.07.16.25.324)(2345xxxxxxf用秦九韶算法求这个多项式当x=5的值。解：将多项式变形：8.0)7.1)6.2)5.3)24(((()(xxxxxxf按由里到外的顺序，依此计算一次多项式当x=5时的值：222541v40v5.1135.35222v9.5646.255.1133v2.28267.159.5644v2.141308.052.28265v所以，当x=5时，多项式的值等于14130.2你从中看到了怎样