1.3　算法案例(1) 学案（人教A版必修三）

《1.3　算法案例(1) 学案（人教A版必修三）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§1.3　算法案例(一)【明目标、知重点】1．理解辗转相除法与更相减损术中的数学原理，并能根据这些原理进行算法分析．2．了解秦九韶算法及利用它计算提高计算效率的本质．3．对简单的案例能设计程序框图并写出算法程序．【填要点、记疑点】1．辗转相除法(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法．(2)辗转相除法的算法步骤第一步，给定两个正整数m，n(m>n)．第二步，计算m除以n所得的余数r.第三步，m＝n，n＝r.第四步，若r＝0，则m，n的最大公约数等于m；否则，返回第二步．2．更相减损术的运算步骤第一步，任意给定两个正整数，判断它们是否都

2、是偶数．若是，用2约简；若不是，执行第二步．第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．3．秦九韶算法把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如下形式：(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0，求多项式的值时，首先计算最内层括号内一次多项式的值，即v1＝anx＋an－1，然后由内向外逐层计算一次多项式的值，即v2＝v1x＋an－2，v3＝v2x＋an－3，…vn＝vn－1x＋a0这样，求n次

3、多项式f(x)的值就转化为求n个一次多项式的值．【探要点、究所然】[情境导学]　在小学，我们已经学过求最大公约数的知识，利用找公约数的方法来求最大公约数．如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数？这就是我们这一堂课所要探讨的内容．探究点一　辗转相除法思考1　18与30的最大公约数是多少？你是怎样得到的？答　先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数．由于，所以，18与30的最大公约数是2×3＝6.问题　如何求两个正数8251和6105的

4、最大公约数？思考2　对于8251与6105这两个数，由于其公有的质因数较大，利用小学的方法求最大公约数就比较困难．注意到8251＝6105×1＋2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？答　显然8251的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数．思考3　又6105＝2146×2＋1813，同理，6105与2146的公约数和2146与1813的公约数相等．重复上述操作，你能得到8251与6105这两个数的最大公约数吗？答　8

5、251＝6105×1＋2146，6105＝2146×2＋1813，2146＝1813×1＋333，1813＝333×5＋148，333＝148×2＋37，148＝37×4＋0.最后的除数37是148和37的最大公约数，也是8251与6105的最大公约数．反思与感悟　上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法．思考4　(1)用辗转相除法可以求两个正整数m，n的最大公约数，那么用什么逻辑结构来设计算法？其算法步骤如何设计？(2)该算法的程序框图如何表示？该程序框图对应的程序如何表述？(3)如果用当型循环结构设计算法，正整数m，n的最大公约数的程序框图和程序分别如

6、何表示？答　(1)用循环结构设计算法，算法如下：第一步，给定两个正整数m，n(m>n)．第二步，计算m除以n所得的余数r.第三步，m＝n，n＝r.第四步，若r＝0，则m，n的最大公约数等于m；否则，返回第二步．(2)　　　程序框图：　　程序：INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND探究点二　更相减损术思考1　设两个正整数m>n，若m－n＝k，则m与n的最大公约数和n与k的最大公约数相等．反复利用这个原理，可求得98与63的最大公约数为多少？答　由于63不是偶数，把98和63以大数减小数，并辗转相减，得98－63＝3

7、5，63－35＝28，35－28＝7，28－7＝21，21－7＝14，14－7＝7.可知98与63的最大公约数为7.小结　上述求两个正整数的最大公约数的方法称为更相减损术．思考2　(1)用更相减损术可以求两个正整数m，n的最大公约数，那么用什么逻辑结构来构造算法？其算法步骤如何设计？答　(1)用循环结构设计算法，算法如下：第一步，任意给定两个正整数m，n(m>n)．第二步，计算m－n所得的差k.第三步，比较n与k的大小，其中大者用m表示，小者用n表示．第四步，若m＝n，则m，n的最大公约数等