1.3 算法案例 教学设计1

§1.3算法案例第三课时割圆术一、教学背景分析（一）教学内容解析本节课虽非普通高中课程标准实验教科书的内容，但人教A版必修3中的第一章《算法结构》的“阅读与思考”内容以刘徽的“割圆术”为载体，让学生通过了解“割圆术”的基本特点及其中蕴含的递推思想与迭代算法，体会“割圆术”是几何算法阶段计算圆周率的既有效又科学的方法，又让学生感受到计算工具的不断发展，为圆周率的计算乃至整个数学学科的发展带来前所未有的突破.在数学史上，简洁而精确的圆周率求法，曾经是数学家们不懈追求的目标，在不同历史阶段，各个国家的数学家们提出了形形色色的圆周率近似值求法，如经验实测方法，蒙特卡洛方法，刘徽割圆术，阿基米德割圆术，级数逼近等等.每一次方法的改进，都在严密性与精确性的角度上体现了重要的数学思想，因此在高中阶段，让学生了解和学习各种不同的圆周率近似值的求法，并对这些方法进行比较与分析，是十分必要的.（二）学生学情分析在深化课改的背景下，现阶段的学生并没有学过如何求圆周率，只有人教A版必修3 中的第一章《算法结构》的“阅读与思考”内容是以刘徽的“割圆术”为载体，通过算法知识来介绍求圆周率，但是，必修3中算法的相关知识，也没有学过，在算法的建构方面存在一定的困难，同时对圆周率π认知基本上停留在能背出小数点后多少位，却不知圆周率π是如何得到的.学生通过课前资料收集和阅读思考，对历史上几种不同的圆周率求法进行了初步的了解，同时以教材中的“阅读与思考”内容，同时也是历史上完备性最好，且具有算法思想的刘徽的“割圆术”作为重点介绍内容，让学生领悟刘徽的割圆术中所蕴含的递推思想及迭代算法.对于刘徽割圆术的掌握，对学生来说是一个挑战，圆内接正多边形的面积公式的递推关系的推导对学生来说是十分困难的．根据教学内容解析和学情分析，我确定本节课的教学重点和难点如下：重点：在学生通过课前阅读与课外查阅与研究所了解的有关求圆周率的方法的基础上，对各种不同的方法进行简要的介绍与对比，同时深入探究刘徽割圆术的思想方法，获得面积递推公式，同时体会其中蕴含的递推思想与迭代算法．难点：割圆术中“内外夹逼”的极限思想与算法实现过程中递推关系的建立．二、教学目标设置依据课程标准，基于上述分析，我确定本节课的教学目标如下：（一）让学生经历从直观感受到随机模拟，最后到严格推理，然后以计算机实现近似值求解的过程，既对相关数学史有所了解，同时又让学生体会了求解圆周率的历史实质是运算工具的发展史．（二）理解割圆术对于圆周率估计的完备性与精确性，以及求解过程中所蕴含的递推思想，体会计算机程序迭代算法和割圆术的应用价值．（三）了解求解圆周率的历史，感受数学的文化价值．三、教学策略分析本节课在教学材料的组织上选择了让学生课前探究求解圆周率π的方法，自主学习刘徽的割圆术，并以小组交流的形式汇报阅读成果.应用问题探究式教学方式，对课本介绍的刘徽的割圆术进行再思考，让学生自主探究如何方便地计算圆内接正多边形的面积．借助Ｅxcel软件的迭代功能实现算法，完成对圆周率π的近似值的初步估计. 因此本节课采用学生课前阅读与课内思考相结合的方式，让学生体会以阅读学习所获得的知识为基础，在经过再思考后，获得对问题的深刻理解的过程；同时采用公式的理论推导和信息技术相结合的手段，让学生体会到中国古代数学中所蕴含的算法思想，给学生提供了一次动手实践、还原历史的经历．四、教学过程为了达到以上教学目标，在具体教学中，我把这节课分为以下五个阶段：分别从数学史的发展角度，与方法的完备性角度来逐步递进探索并对比不同方法的优劣.下面我将对每一阶段教学中计划解决的主要问题和教学步骤作出说明.（一）呈现背景【学生活动】学生课前查阅圆周率π的相关知识，自主学习刘徽的割圆术，并相互交流对圆周率的认识.【教师总结】那圆周率的值到底是多少呢？又是如何得到的呢？在绵延的历史长河中，人们又是怎样“计算” 圆周率的呢？【设计意图】从数学史与数学文化的角度，来引起学生对于圆周率求解方法的兴趣，为后面各种方法的介绍做好铺垫.（二）探索方法【第一组：实测法】第一小组学生代表介绍：“用实测的方法求圆周率π”【学生活动】学生讨论实测法的不准确之处：1.圆周是曲线，用细绳去拟合时，存在误差.2.测量长度时，存在误差.【教师总结】尺子的精度越高，得到的测量值可能会越准确.精度再高的刻度尺也无法量得线段长的真实值.其实，早在明代就有一位名叫邢云路的数学家，他呈现背景探索方法完善方法实现算法归纳小结就用实测的方法求圆周率，后来茅以升这样评价他：“云路欲以度量所得，抹煞古人诸率，所见甚浅.”可见，实测的办法是比较粗糙的.【设计意图】通过实测与经验来估计圆周率的近似值，是人类历史上最早采用的方法，但这种方法在数学上既不严密，同时所求得的近似值的精确度也无法保证，在课前让学生通过实验，切身体会到用实测的方法求圆周率π是比较粗糙的.【第二组：布丰投针】第二小组学生代表介绍：“用布丰投针实验求圆周率π”【学生活动】求解任意给出3个正数，以这3个正数为边长可以围成一个钝角三角形的概率. 解：设这三个正数为c b a ，，，不妨设a b c ≤，，由以c b a ，，为边长可以围成一个钝角三角形得：222c b a c b a <+>+，，变形，得：1122<⎪⎭⎫ ⎝⎛+⎪⎭⎫ ⎝⎛>+c b c a c b c a ，，令c b y c a x ==,，则⎪⎪⎩⎪⎪⎨⎧<+>+≤<≤<11101022y x y x y x ， 由线性规划可知：满足题意的可行域为直线1+-=x y 与圆122=+y x 围成的弓形，总的区域是一个边长为1的正方形.则可以围成一个钝角三角形的概率1--24214S P S ππ===弓形正方形. 【教师总结】早在1904年，R 查特发现，两个随意写出的整数中，互素的概率为26π.然后，我们可以通过“像投针一样的操作实验”或者“让计算机产生随机数，进行计算机模拟实验”，从而得到实验频率，求出圆周率的近似值.【设计意图】布丰投针实验至少给了我们两大启示：1.可以利用概率原理来解释圆周率的计算，虽然实验结果具有随机性；2.投针实验拓宽了人们运用数学知识解决复杂问题的渠道，它已发展为一种新的数学方法——统计实验法，也就是著名的蒙特卡罗法.利用概率论的大数定律，可以保证用该方法求得的近似值在概率意义上是收敛于真实值的，但所得结果的精确度无法准确估计，因此相对于实测的方法，有所进步，但仍不够完善.【第三组：割圆术】第三小组学生代表介绍：“刘徽的割圆术”通过课前学习，让学生对刘徽的割圆术有了基本的认识，并得到了课本上的圆内接正多边形的面积递推公式21(1)2n n n n S S n x h =+⋅⋅-. 【学生活动】小组交流1：刘徽为什么不从圆内接正三角形的面积开始，而是从六边形开始？——好算，且精确度相对较高.小组交流2：如果以正四边形面积为起始可以吗？——以任意正n 边形面积为起始都可以，因为2n x 与n x 及2n S 与n x 之间的递推关系并不会因为初始值的不同而发生改变.随着正多边形边数的增加，最终的效果是一致的.【教师总结】回味刘徽的割圆术，他是以圆内接正六边形的面积为起始，借助6x 来求6S ，然后在6x ，6S 的基础上，求12x ，12S ，依次类推，……，要求2n S ，只需借助于n x ，n S ，得到了圆内接正多边形的面积的递推公式.【设计意图】让学生通过课外阅读与课前学习，以小组交流的形式汇报阅读成果. 为本节课内针对刘徽的割圆术的再思考奠定了必要的认知基础，同时也让学生认识到在数学学习中“阅读．．”的重要性． 【师生互动】在算完正六边形的面积后，为什么不算正七边形的面积，而是选择计算正十二边形的面积？【学生活动】分析与讨论在算完正六边形的面积后，不算正七边形面积的理由.【教师总结】正十二边形的面积容易计算，关键在于在正六边形的基础上，增加的顶点B 是CD 的中点，根据垂径定理，正十二边形的“特征三角形”的底就是半径1，高其实是正六边．．．．．．．形的边长的一半．．．．．．．． 【设计意图】正六边形的面积算完后，为什么直接跳到算正十二边形的面积？正是因为我们可以借助正六边形的边长，来求正十二边形的面积（及边长）. 而知道正六边形的边长和面积，却没有为算正七边形的面积带来任何帮助. 这样设问，是为了让学生在计算的过程中体会从正六边形过渡到正十二边形的合理性．同时让学生体会其中蕴含的递归思想，发现问题本质，为下面的递归关系的建立奠定基础．（三）完善方法问题1：是否有其他办法可以求圆内接正多边形的面积?能否把刚才的方法推广到一般情形？【学生活动】学生介绍不同于课本教材的圆内接正十二边形的面积的求法:把正十二边形分割成十二个特征三角形，容易算得它的面积为： 61211121212222COB x S S OB CA ==⨯⨯⨯=⨯⨯（）（） 【学生活动】那么正2n 边形的面积2n S 就等于：2COB 122222n n n x n S nS n x ==⨯⨯=（）【教师总结】从此式看出：只需借助正n 边形的边长n x 来求正2n 边形的面积2n S ．相比于之前介绍的递推公式))2(1-121(22）（n n n n x x n S S -⨯⨯⨯+=，表达式上更加简洁. 同时，也要注意到：这两个面积递推公式，都是借助于2n x 与n x 之间的递推关系，其本质是一样的.【师生互动】这两种递推公式，哪一种在计算机里运行速度更快？效率更高？【学生活动】后者在表达式上更加简洁，减少了开方运算的次数，效率更高.【教师总结】在1800年前，刘徽只计算到了圆内接正192边形的面积，相当于只迈开了六步.现在，我们已拥有具有强大计算能力的计算机.这个递推公式，恰好符合计算机的迭代算法.我们可以借助计算机来实现算法.【设计意图】割圆术作为历史上第一个出现的完备性最好的求圆周率的方法，也并非在各个方面尽善尽美，因此引导学生在知识的获得之后，但作为课内针对学生课前阅读的“第一次思考”，引导学生成功建立正n 边形的边长与正2n 边形的面积之间的递归关系，而且此面积递推公式比课本介绍的递推公式更加简洁，为后续计算边数更多的正多边形面积提供了一个可行、高效的方法，也为后续的程序的实现提供了算法依据，让学生体会到“阅读”之后“思．考．”的重要性与必要性． （四）实现算法回味此递推公式：2224n n x x =--，已知6x ，求得12x 后，再由12x ，代入此式，求得24x ，……，依此类推，这是一种迭代的算法，而Excel 软件刚好有迭代的功能，我们就借助Excel 来实现算法.nx n S 2n 6 1.0000000 3.0000000120.5176381 3.1058285240.2610524 3.1326286480.1308063 3.1393502960.0654382 3.14103201920.0327235 3.14145253840.0163623 3.14155767680.0081812 3.141583915360.0040906 3.1415905通过表格，我们看到：随着n 的增大，2n S 的面积越来越大，越来越趋近于π真实值. 运用Excel 软件实现的算法，可以用程序框图来表示，再翻译成程序语言，利用计算机实现算法.【数学史介绍】数学家祖冲之在此基础上，把圆周率π精确到小数点后第七位. 在西方，这个成绩由法国数学家韦达于1593年取得, 比祖冲之晚了一千多年.【设计意图】揭示递推公式与迭代算法之间的关系，借助计算机来实现圆周率π的近似值的估计，既是对刘徽割圆术的方法的有效验证，又体现了中国古代数学的算法特征．同时让学生体会用程序框图来表示算法，能使算法的逻辑结构更清楚、步骤更直观．同时了解求解圆周率π的历史，感受数学的文化价值．问题2：已知圆内接正四边形的面积42S =，在此基础上往下算，会选择计算圆内接正几边形的面积？理由是什么？（请看视频）【学生活动】计算圆内接正八边形的面积8S ，再计算圆内接正十六边形的面积16S ，依此类推. 可以借助正n 边形的边长与正2n 边形的面积.【教师总结】2n x 与n x 及2n S 与n x 之间的递推关系并没有因为初始值的不同而发生改变.即使初始值的误差比较大，随着正多边形边数的增加，最终的效果会是一致的.【设计意图】作为课内针对学生课前阅读的“第二次思考”，让学生牢牢把握刘徽的割圆术的本质——递推关系的应用与迭代算法的实现，与迭代过程的初始值无关．我们刚才都是用圆内接正多边形的面积2n S 来近似代替圆的面积，这样得到的π的近似值肯定要比π的真实值小.也就是说，我们得到的是（圆面积）的下限.出于考虑问题的严谨性，还要对圆面积的上限加以估计.问题3：选择哪个几何图形的面积作为圆面积的上限？【学生活动】设圆外切正n 边形的边长为n y ,外切正n 边形的面积为n T . 利用相似比：212n n n x x y ⎛⎫- ⎪⎝⎭=得：24n n ny x =-所以21124nn n n T n y x =⨯⨯⨯=-问题4：是否有更合适的几何图形的面积可以做为圆面积的上限？【学生活动】思考是否有更佳的上限估计方式，并提出自己的看法：这些圆内接正多边形每边外有一余径，用边长乘以余径，加到正多边形的面积上，则大于圆的面积，即数学家刘徽的想法. 此时，此几何图形的面积为：()()2222n n n n n n S S S S S S +-=+-.【设计意图】通过圆面积的上限的讨论，进一步完善割圆术的思想，作为课内针对学生课前阅读的“第三次思考”，通过计算、对比，让学生深刻体会刘徽的割圆术的精明之处：1、已有的成果2,n n S S 来表示圆的面积的上限，成功的将计算量减半；2、刘徽的割圆术的完备性与数学研究过程中所要求的严密性相符．让学生感受在“阅读”的基础上“思考”所带来的成果．我们也借助Excel 软件来实现算法:n x S 3.2945078 n 2n S 2n +ΔS 4 1.4142136 2.8284271 80.7653669 3.0614675 160.3901806 3.1214452 3.1814228 320.1960343 3.1365485 3.1516518 640.0981353 3.1403312 3.1441138 1280.0490825 3.1412773 3.1422233 2560.0245431 3.1415138 3.1417504 5120.0122718 3.1415729 3.1416321 10240.0061359 3.1415877 3.1416025 20480.0030680 3.1415914 3.1415951 40960.0015340 3.1415923 3.1415933【设计意图】再次通过Excel 软件实现上限的估计，验证了运用割圆术求解π的近似值的可行性与有效性，实现了学生课前的“阅读成果”．问题5：同学们还有什么感触吗？【学生活动】学生介绍利用三角函数来求圆内接正多边形的的面积：把正十二边形分割成十二个特征三角形，利用三角函数算得它的面积为：2012COB 112121sin 302S S ∆==⋅⋅⋅ 【学生活动】那么正2n 边形的面积2n S 就等于：222sin n n S nS n θ==特征三角形【教师总结】利用三角函数求解圆内接正多边形的面积，在历史上，直到文艺复兴时期，哥白尼（1473--1543）和开普勒（1571-1630）研制了相当精确地三角函数表，这个问题才得以解决.看来同学们都能学以致用！【数学史介绍】事实上，历史上还出现了很多求圆周率的方法，比如：韦达的无穷乘积法，欧拉的无穷级数法，1844年，达赛利用π的反正切函数表达式把π值计算到了小数点后200位.【设计意图】在详细介绍了“实测方法”、“蒙特卡洛方法”与“割圆术”之后，又对如何用高等方法求解圆周率进行了简要的介绍，让学生增加了对近代数学求解π的历史，使得数学史上对于π的求解历程有了更加完整的认识，再次感受数学的文化价值．（五）归纳小结从实测的直觉与粗糙，到割圆术的以直代曲、无限逼近、内外夹逼的严谨，再到三角函数加入割圆术，π的计算精度越来越高，但方法上没有本质改变.直到1665年牛顿等人发明微积分，才使π的计算走到了历史转折点，然而追溯建立微积分的先驱人物又当数阿基米德和刘徽，他们提出的割圆术中已相当自觉地运用了“无穷”和“愈来愈接近”等属于微积分的基本概念.同时，1777年，布丰的投针实验则另辟蹊径，充满创新.纵观几千年来，为了得到更精确地圆周率的值，数学家们千方百计，花费了很多时间和精力，进行着不懈的探索.这个过程不仅仅是“从公元前2000年的几位小数，到公元后2000年的2061亿位小数”的变化，而是在其背后的运算工具的不断发展，昭示了人类在数学领域的卓越追求.高中数学-打印版1761年，当人们还在狂热于计算π值的时候，兰伯特(H·Lambert)证明了π是一个无理数；1882年，林德曼F·vonLindermann于又证明了它是超越数，圆周率的神秘面纱就被揭开了.这一结论解答了公元前434年提出的“化圆为方”的问题是无法实现的.可见，数学越向前发展，人们对事物的认识就越加清晰、深刻.所以说，数学是有用的.愿今天的圆周率之旅，能让你领略到一些数学的魅力，触发起你心中的探索欲望.五、教学特点及反思（1）课前阅读与课内思考紧密结合本节课采用学生课前阅读与课内思考相结合的方式，课前组织学生自主查阅并学习历史上有关圆周率π的各种不同的求法，是为“阅读”；而后在课内引导学生在通过对各种不同的圆周率求法的介绍，对比，以及相关问题进行更加深入的探究，是为“思考”，紧密结合阅读与思考，突破传统的新授课课堂教学模式．通过“阅读”带动“思考”，再经过“思考”加深“阅读”所获得的知识的理解，既给学生创设了自主探究、小组合作交流等平台，又充分挖掘了思维的深度和广度.（2）历史发展与数学进步有效契合本节课既介绍了有关圆周率求解的数学历史，又渗透了各种求解方法所蕴含的数学思想与方法，在方法的介绍与探讨过程中，成功地将历史发展过程，与不同方法的逻辑严密性与精确性的提高过程这两条线索有效契合，贯穿整节课堂，做到数学中有历史，历史中有数学. （3）信息技术与课程内容有机整合通过揭示递推公式与迭代算法之间的关系，用程序框图来表示算法，借助计算机中的Excel软件来实现算法，完成对圆周率π的近似值的初步估计，既验证了运用割圆术求解π的近似值的可行性与有效性，又体现了中国古代数学的算法特征．精心校对完整版。

318=265×1+53; 265=53×5+0.
案例2
秦九韶算法
计算多项式ｆ(ｘ) =ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１ 当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 +１) +１ )+１)+１) +１
辗转相除法求最大公约数算法：
• • • •
第一步,给定两个正数m,n 第二步,计算m除以n所得到余数r 第三步,m=n,n=r 第四步,若r=0,则m,n的最大公约数等于m; 否则返回第二步
练习2：利用辗转相除法求两数4081与 20723的最大公约数. 20723=4081×5+318;
4081=318×12+265;
按由里到外的顺序，依此计算一次多项式当x = 5时的值：
v0 5 v1 5 5 2 27 v2 27 5 3.5 138.5 v3 138.5 5 2.6 689.9 v4 689.9 5 1.7 3451.2 v5 3451.2 5 0.8 17255.2
练： 已知一个五次多项式为
5 4 3
f ( x) 5x 2 x 3.5x 2.6 x 1.7 x 0.8
2
用秦九韶算法求这个多项式当x = 5的值。 解： 将多项式变形：

知识点一1、欧几里德算法最大公约数
2、两个正整数 ， 除以 所得的余数 第二步
知识点二
1、两个数的最大公约数
2、用2约减执行第二步较大的数较小的数较小的数相等
例1、解：用两数中较大的数除以较小的数，求得商和余数：8 251=6 105×1+2 146.
由此可得，6 105与2 146的公约数也是8 251与6 105的公约数，反过来，8 251与6 105的公约数也是6 105与2 146的公约数，所以它们的最大公约数相等.
第三步，m=n，n=r.
第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步.
程序框图如下图：
程序：
INPUTm,n
DO
r=m MOD n
m=n
n=r
LOOP UNTIL r=0
PRINT m
END
点评：从教学实践看，有些学生不能理解算法中的转化过程，例如：求8 251与6 105的最大公约数,为什么可以转化为求6 105与2 146的公约数.因为8 251=6 105×1+2 146，
疑难点播：辗转相除法与更相减损术的区别和联系？
1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数.
2.更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数
对6 105与2 146重复上述步骤：6 105=2 146×2+1 813.
同理，2 146与1 813的最大公约数也是6 105与2 146的最大公约数.继续重复上述步骤：

§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约简；若不是，执行第二步．第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．3．秦九韶算法把一个n次多项式f(x)＝a n x n＋a n－1x n－1＋…＋a1x＋a0改写成如下形式：(…((a n x＋a n－1)x＋a n－2)x＋…＋a1)x＋a0，求多项式的值时，首先计算最内层括号内一次多项式的值，即v1＝a n x＋a n－1，然后由内向外逐层计算一次多项式的值，即v2＝v1x＋a n－2，v3＝v2x＋a n－3，…v n＝v n－1x＋a0这样，求n次多项式f(x)的值就转化为求n个一次多项式的值．【探要点、究所然】[情境导学]在小学，我们已经学过求最大公约数的知识，利用找公约数的方法来求最大公约数．如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8 251与6 105的最大公约数？这就是我们这一堂课所要探讨的内容．探究点一辗转相除法思考118与30的最大公约数是多少？你是怎样得到的？答先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数．由于，所以，18与30的最大公约数是2×3＝6.问题如何求两个正数8 251和6 105的最大公约数？思考2对于8 251与6 105这两个数，由于其公有的质因数较大，利用小学的方法求最大公约数就比较困难．注意到8 251＝6 105×1＋2 146，那么8 251与6 105这两个数的公约数和6 105与2 146的公约数有什么关系？答显然8 251的最大公约数也必是2 146的约数，同样6 105与2 146的公约数也必是8 251的约数，所以8 251与6 105的最大公约数也是6 105与2 146的最大公约数．思考3又6 105＝2 146×2＋1 813，同理，6 105与2 146的公约数和2 146与1 813的公约数相等．重复上述操作，你能得到8 251与6 105这两个数的最大公约数吗？答8 251＝6 105×1＋2 146，6 105＝2 146×2＋1 813，2 146＝1 813×1＋333，1 813＝333×5＋148，333＝148×2＋37，148＝37×4＋0.最后的除数37是148和37的最大公约数，也是8 251与6 105的最大公约数．反思与感悟上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法．思考4(1)用辗转相除法可以求两个正整数m，n的最大公约数，那么用什么逻辑结构来设计算法？其算法步骤如何设计？(2)该算法的程序框图如何表示？该程序框图对应的程序如何表述？(3)如果用当型循环结构设计算法，正整数m，n的最大公约数的程序框图和程序分别如何表示？答(1)用循环结构设计算法，算法如下：第一步，给定两个正整数m，n(m>n)．第二步，计算m除以n所得的余数r.第三步，m＝n，n＝r.第四步，若r＝0，则m，n的最大公约数等于m；否则，返回第二步．(2)程序框图：程序：INPUT m,nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND探究点二更相减损术思考1设两个正整数m>n，若m－n＝k，则m与n的最大公约数和n与k的最大公约数相等．反复利用这个原理，可求得98与63的最大公约数为多少？答由于63不是偶数，把98和63以大数减小数，并辗转相减，得98－63＝35，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的最大公约数等于m；否则，返回第二步．(2)该算法的程序框图如何表示？该程序框图对应的程序如何表述？答程序框图：程序：INPUT m,nWHILE m<>nk=m-nIF n>k THENm=nn=kELSEm=kEND IFWENDPRINT mEND例1分别用辗转相除法和更相减损术求261和319的最大公约数．解辗转相除法：319÷261＝1(余58)，261÷58＝4(余29)，58÷29＝2(余0)，所以319与261的最大公约数为29.更相减损术：319－261＝58，261－58＝203，203－58＝145，145－58＝87，87－58＝29，58－29＝29，29－29＝0，所以319与261的最大公约数是29.反思与感悟 1.利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．2．利用更相减损术求两个正整数的最大公约数的一般步骤是首先判断两个正整数是否都是偶数．若是，用2约简．也可以不除以2，直接求最大公约数，这样不影响最后结果．跟踪训练1用辗转相除法求80与36的最大公约数，并用更相减损术检验你的结果．解80＝36×2＋8，36＝8×4＋4,8＝4×2＋0，即80与36的最大公约数是4.验证：80÷2＝4036÷2＝1840÷2＝2018÷2＝920－9＝1111－9＝29－2＝77－2＝55－2＝33－2＝12－1＝11×2×2＝4所以80与36的最大公约数为4.探究点三秦九韶算法的基本思想思考1怎样计算多项式f(x)＝x5＋x4＋x3＋x2＋x＋1当x＝5时的值呢？统计所做的计算的种类及计算次数分别是什么？答f(5)＝55＋54＋53＋52＋5＋1＝3 906.根据我们的计算统计可以得出我们共需要10次乘法运算，5次加法运算．思考2我们把多项式变形为f(x)＝((((x＋1)x＋1)x＋1)x＋1)x＋1，再统计一下计算当x＝5时的计算的种类及计算次数分别是什么？答从里往外计算仅需4次乘法和5次加法运算即可得出结果．小结思考2中的计算比问题1中的计算显然少了6次乘法运算．这种算法就叫秦九韶算法．一般地，f(x)＝a n x n＋a n－1x n－1＋a n－2x n－2＋…＋a1x＋a0＝(a n x n－1＋a n－1x n－2＋a n－2x n－3＋…＋a1)x＋a0＝((a n x n－2＋a n－1x n－3＋…＋a2)x＋a1)x＋a0＝…＝(…((a n x＋a n－1)x＋a n－2)x＋…＋a1)x＋a0.求多项式的值时，首先计算最内层括号内一次多项式的值，即v1＝a n x＋a n－1，然后由内向外逐层计算一次多项式的值，即v2＝v1x＋a n－2，v3＝v2x＋a n－3，…，v n＝v n－1x＋a0，这样，求n次多项式f(x)的值就转化为求n个一次多项式的值．例2已知一个5次多项式为f(x)＝4x5＋2x4＋3.5x3－2.6x2＋1.7x－0.8，用秦九韶算法求这个多项式当x＝5时的值．解将f(x)改写为f(x)＝((((4x＋2)x＋3.5)x－2.6)x＋1.7)x－0.8，由内向外依次计算一次多项式当x＝5时的值：v0＝4；v1＝4×5＋2＝22；v2＝22×5＋3.5＝113.5；v3＝113.5×5－2.6＝564.9；v4＝564.9×5＋1.7＝2 826.2；v5＝2 826.2×5－0.8＝14 130.2.∴当x＝5时，多项式的值等于14 130.2.反思与感悟秦九韶算法步骤：跟踪训练2用秦九韶算法求多项式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x当x＝3时的值．解f(x)＝((((((7x＋6)x＋5)x＋4)x＋3)x＋2)x＋1)x所以有v0＝7，v1＝7×3＋6＝27，v2＝27×3＋5＝86，v3＝86×3＋4＝262，v4＝262×3＋3＝789，v5＝789×3＋2＝2 369，v6＝2 369×3＋1＝7 108，v7＝7 108×3＝21 324.故当x＝3时，多项式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x的值为21 324.【当堂测、查疑缺】1．辗转相除法与更相减损术是求最大公约数的常用方法，从计算结果形式上看，辗转相除法以________________得到结果，更相减损术则以________________而得到结果．答案相除余数为零减数与差相等2．用辗转相除法求85与51的最大公约数时，需要做除法的次数为________．答案3解析85＝51×1＋34，51＝34×1＋17，34＝17×2＋0.3．已知f(x)＝2x3＋x－3，用秦九韶算法求当x＝3时v2的值．解f(x)＝2x3＋x－3＝2x3＋0·x2＋x－3＝((2x＋0)x＋1)x－3，v0＝2，v1＝2×3＋0＝6，v2＝6×3＋1＝19.【呈重点、现规律】1．辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数．2．更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数．3．用秦九韶算法求多项式f (x )当x ＝x 0的值的思路为①改写；②计算⎩⎪⎨⎪⎧ v 0＝a n v k ＝v k －1x 0＋a n －k (k ＝1，2，…，n )；③结论f (x 0)＝v n .课。