《福建省晋江市首峰中学高中数学 1.3算法案例课件 新人教A版必修3》由会员分享，可在线阅读，更多相关《福建省晋江市首峰中学高中数学 1.3算法案例课件 新人教A版必修3（34页珍藏版）》请在金锄头文库上搜索。
1、算算 法法 案案 例例（第一课时（第一课时）1、求两个正整数的最大公约数、求两个正整数的最大公约数（1）求）求25和和35的最大公约数的最大公约数（2）求）求225和和135的最大公约数的最大公约数2、求、求8251和和6105的最大公约数的最大公约数 25（1） 55357所以，所以，25和和35的最大公约数为的最大公约数为5所以，所以，225和和135的最大公约数为的最大公约数为45辗转相除法（欧几里得算法）辗转相除法（欧几里得算法）观察用辗转相除法求观察用辗转相除法求8251和和6105的最大公约数的过程的最大公约数的过程 第一步第一步 用两数中较大的数除以较小的数，求得用两数中较大的数
2、除以较小的数，求得商商和和余数余数8251=61051+2146结论：结论： 8251和和6105的公约数就是的公约数就是6105和和2146的公约数，求的公约数，求8251和和6105的最大公约数，只要求出的最大公约数，只要求出6105和和2146的公约数的公约数就可以了。就可以了。第二步第二步 对对6105和和2146重复第一步的做法重复第一步的做法6105=21462+1813同理同理6105和和2146的最大公约数也是的最大公约数也是2146和和1813的最大的最大公约数。公约数。 完整的过程完整的过程8251=61051+2146 6105=21462+1813 2146=18131
3、+3331813=3335+148333=1482+37148=374+0例例2 用辗转相除法求用辗转相除法求225和和135的最大公约数的最大公约数225=1351+90135=901+4590=452显然显然37是是148和和37的最大公约的最大公约数，也就是数，也就是8251和和6105的最的最大公约数大公约数 显然显然45是是90和和45的最大公约数，也就是的最大公约数，也就是225和和135的最大公约数的最大公约数 思考思考1：从上面的两个例子可以看出计：从上面的两个例子可以看出计算的规律是什么？算的规律是什么？ S1：用大数除以小数：用大数除以小数S2：除数变成被除数，余数变成除数
4、：除数变成被除数，余数变成除数S3：重复：重复S1，直到余数为，直到余数为0 辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0停止的步骤，停止的步骤，这实际上是一个循环结构。这实际上是一个循环结构。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m = n q r用程序框图表示出右边的过程用程序框图表示出右边的过程r=m MOD nm = nn = rr=0?是否INPUT m , nDO r=m mod n m=n n=rLOOP UNTIL r=0 PRI
5、NT mEnd九章算术九章算术更相减损术更相减损术 算理：算理：可半者半之，不可半者，副置分母、子之数，以少减可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。多，更相减损，求其等也，以等数约之。第一步：第一步：任意给定两个正整数；判断他们是否都是偶数。若任意给定两个正整数；判断他们是否都是偶数。若是，则用是，则用2约简；若不是，则执行第二步。约简；若不是，则执行第二步。第二步：第二步：以以较大的数减较小的数较大的数减较小的数，接着把所得的差与较小的数，接着把所得的差与较小的数比较，并以比较，并以大数减小数大数减小数。继续这个操作，直到所得的。继续这个操作，直到
6、所得的减数和差减数和差相等为止相等为止，则这个等数或这个等数与约简的数的乘积就是所求，则这个等数或这个等数与约简的数的乘积就是所求的最大公约数。的最大公约数。例例3 用更相减损术求用更相减损术求 225 与与 135 的最大公约数的最大公约数解：由于两数不是偶数，把解：由于两数不是偶数，把225和和135以大数减小数，以大数减小数， 并辗转相减并辗转相减 225135901359045904545所以，所以，225和和135的最大公约数等于的最大公约数等于45INPUT a,bWHILE ab IF ab THEN a=a-b ELSE b=b-a END IFWEND PRINT aEND九
7、章算术九章算术更相减损术的算法程序语句：更相减损术的算法程序语句： 练习：练习：用辗转相除法求用辗转相除法求 294 与与84的最大公约数，再的最大公约数，再用更相减损术验证。用更相减损术验证。思考：求三个数：思考：求三个数：168，54，264的最大公约数。的最大公约数。算算 法法 案案 例例（第二课时（第二课时）计算多项式计算多项式（） =当当x = 5的值的值算法算法1：（） =x xxx x x xx x x x x x x x 1所以所以（5）=55555=3125625125255= 3906算法算法2：（5）=55555=（ （5 ） 5 ） 5 ） 5 ） 5 （） = =(x
8、+1)x+1)x+1)x+1)x+1数书九章数书九章秦九韶算法秦九韶算法设设是一个是一个n次的多项式次的多项式对该多项式按下面的方式进行改写：对该多项式按下面的方式进行改写：这样改写的目的是什么？这样改写的目的是什么？简化计算的次数（尤其是乘法的次数）。简化计算的次数（尤其是乘法的次数）。设设是一个是一个n次的多项式次的多项式对该多项式按下面的方式进行改写：对该多项式按下面的方式进行改写：要求多项式的值，应该先算最内层的一次多项式的值，即要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即最后的一项是什么？这种将求一
9、个这种将求一个n次多项式次多项式f（x）的值转化成求）的值转化成求n个个一次多项式的值的方法，称为一次多项式的值的方法，称为秦九韶算法秦九韶算法。例例2 已知一个五次多项式为已知一个五次多项式为用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x = 5的值。的值。解：解：将多项式变形：将多项式变形：按由里到外的顺序，依此计算一次多项式当按由里到外的顺序，依此计算一次多项式当x = 5时的值：时的值：所以，当所以，当x = 5时，多项式的值等于时，多项式的值等于17255.2你从中看到了怎样的规律？怎么用程序框图来描述呢？练习：2、已知多项式、已知多项式f(x)=2x7-5x5+4x3+x2
10、-x-6用用秦九韶算法求这个多项式当秦九韶算法求这个多项式当x=2时的值。时的值。INPUT “n=“；nINPUT “an=“;aiINPUT “x=“; xV=ani=n-1DO PRINT “i=“;i INPUT “ai=“;ai v=v*x+ai i=i-1LOOP UNTIL inPRINT bEND2、十进制转换为二进制、十进制转换为二进制 (除除2取余法：用取余法：用2连续去除连续去除89或所得的商，或所得的商，然后取余数然后取余数)例例2 把把89化为二进制数化为二进制数解：解：根据根据“逢二进一逢二进一”的原则，有的原则，有892441 2 (2220)+1 2( 2( 2
11、110)+0)+1 2 (2 (2 (2 51)+0)+0)+15 2 212（2（2（2（221）1）0）0）189126025124123022021120所以：所以：89=1011001（2）2（2（2（2321）0）0）12（2（242220）0）12（2523+2200）12624+23002189244144 222022 211011 2 51 2 (2 (2 (2 (2 21)+1)+0)+0)+1所以所以892（2（2（2（2 2 1）1）0）0）12、十进制转换为二进制、十进制转换为二进制例例2 把把89化为二进制数化为二进制数522212010余数余数1122488922
12、2201101注意：注意：1.最后一步商为最后一步商为0，2.将上式各步所得的余数将上式各步所得的余数从下到上排列从下到上排列，得到：，得到：89=1011001（2）练习练习将下面的十进制数化为二进制数？将下面的十进制数化为二进制数？（1）10 （2）20 （3）128 （4）256例例3 把把89化为五进制数化为五进制数3、十进制转换为其它进制、十进制转换为其它进制解：解： 根据根据除除k取余法取余法以以5作为除数，相应的除法算式为：作为除数，相应的除法算式为：所以，所以，89=324（5）。895175350423余数余数设计一个程序，实现设计一个程序，实现“除除k取余法取余法”Input “a,k=”;a,kb=0i=0DO q=ak r=a MOD k b=b+r*10I i=i+1 a=qLOOP UNTIL q=0PRINT bEND开始开始输入输入a,k求求a除以除以k的商的商q求求a除以除以k的余数的余数r把得到的余数依次从右到左排列把得到的余数依次从右到左排列a=qq=0?输出全部余数输出全部余数r排列得到的排列得到的k进制数进制数结束结束思考题：思考题： 如何将如何将101（2） 化为五进制数？化为五进制数？
