人教A版高中数学必修3第一章 算法初步1.3 算法案例教案(6).doc

第一章 算法初步1.3 算法案例第1课时一、教学目标1核心素养在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能力，在利用算法解决数学问题的过程中培养理性的精神和动手实践的能力2学习目标（1）通过求较大的两个数的最大公约数感知其中蕴含的数学原理（2）理解辗转相除法与更相减损术并进行算法分析3学习重点掌握辗转相除法与更相减损术求最大公约数的方法，理解二者的区别与联系4学习难点认识并把握辗转相除法程序框图与程序语言二、教学设计（一）课前设计1预习任务任务1阅读教材P34P37，思考：你会求两个较为简单数的最大公约数吗？任务2辗转相除法与更相减损术中蕴含的数学原理是什么？2预习自测1有关辗转相除法，下列说法正确的是( )A它和更相减损术一样是求多项式值的一种方法B基本步骤是用较大的数m除以较小的数n得到除式mnqr，直至rn为止C基本步骤是用较大的数m除以较小的数n得到除式mqnr(0rn)，反复进行，直到r0为止D以上说法都错误【解析】：C 由辗转相除法的含义可得，故选C.2用更相减损术求36与134的最大公约数，第一步为( )A1343698B13433626C先除以2，得到18与67D134363(余26)【解析】：C 利用更相减损术求两个数的最大公约数时，若两个数都是偶数，则首先将两个数都除以2之后再作减法，故选C（二）课堂设计1知识回顾（1）最大公因数：两个数的所有公因数中最大的一个数（2）本课的辗转相除法与更相减损术对于求两数的最大公约数有什么意义？2问题探究问题探究一 如何求两个较大的数的最大公约数？活动一 回顾旧知在初中，我们已经学过求两数的最大公约数，你能求出18与30的最大公约数吗？易知18与30的公约数有：2、3、6，所以18与30的最大公约数是6.我们都是利用找公约数的方法来求最大公约数，如果两个数数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数？活动二 突破探索方法分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数.8251610512146显然8251的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数.以此类推：步骤：82516105121466105214621813214618131333181333351483331482371483740则37为8251与6105的最大公约数.问题探究二 什么是辗转相除法与更相减损术，其算法是什么？将上述求两个较大的数的最大公约数的方法推广至一般，以上求最大公约数的方法就是辗转相除法.利用辗转相除法求最大公约数的步骤如下：第一步：用较大的数除以较小的数得到一个商和一个余数；第二步：若0，则为，的最大公约数；若0，则用除数除以余数得到一个商和一个余数；第三步：若0，则为，的最大公约数；若0，则用除数除以余数得到一个商和一个余数；依次计算直至0，此时所得到的即为所求的最大公约数.例1 求下列两个数的最大公约数378和90；225和135.解：37890418，901850，378与90的最大公约数是18.225135190，13590145，90452.45是225和135的最大公约数我国早期也有解决求最大公约数问题的算法，就是更相减损术.更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母子之数，以少减多，更相减损，求其等也，以等数约之.翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数.若是，用2约简；若不是，执行第二步.第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数.例2 分析下列解法错因，并用更相减损术正确写出求36和20的最大公约数的解法.错解：用更相减损术步骤如下：362016，20164，16412，1248，844，故36与20的最大公约数为4.解：错因：本题结果虽正确，但解题过程是错误的错误的根源在于没有完全掌握更相减损术的规则更相减损术要求若两数均为偶数则要用2约简本题出错正是忽略这一过程所致正确解法：36和20都是偶数，两次用2约简得9和5.用更相减损的步骤如下：954，541，413，312，211，36和20的最大公约数为4.3课堂总结【知识梳理】(1)辗转相除法的算法步骤：第一步：给定的两个正整数，第二步：用较大的数除以较小的数，若余数为零，则较小的数即这时的除数就是两个数的最大公约数；若余数不为零，则将较小的数和余数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时的除数就是原来两个数的最大公约数.(2)更相减损术是另一种求两数最大公约数的方法.其算法步骤是：第一步：任意给出两个正数；判断它们是否都是偶数.若是，用2约简；若不是，执行第二步.第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数.【重难点突破】(1)辗转相除法与更相减损术的区别与联系都是求最大公约数的方法计算上辗转相除法以除法为主，更相减损术以减法为主；计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显.从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.(2)辗转相除法的程序框图与程序语言程序：INPUT “m=”;mINPUT “n=”;nIF mn THEN x=mm=n n=xEND IFr=m MOD nWHILE r0 r=m MOD n m=nn=rWENDPRINT mEND4随堂检测1用辗转相除法求得168与486的最大公约数是( )A3 B4 C6 D16【解析】：C 4861682150，168150118，1501886，1863，所以168与486的最大公约数是6，故选C.2用更相减损术求459和357的最大公约数.【解析】：51 459357102，357102255，255102153，15310251，1025151，51是459与357的最大公约数.（三）课后作业基础型自主突破1用更相减损术求36与134的最大公约数，第一步为( )A1343698 B13433626C先除以2，得到18与67 D134363(余26)【解析】：C 更相减损术的算法第一步要求若两数均为偶数则要用2约简，故选C2用“辗转相除法”求得459和357的最大公约数是( )A3 B9 C17 D51【解析】：D 4593571102，357102351，1025120，故选D.3用辗转相除法求294和84的最大公约数时，需要做除法的次数是( )A1 B2 C3 D4【解析】：B 29484342，84422，至此最大公约数便已求出，故选B.4在mnqr(0rm THENtmmnntEND IFDOrm MOD nmnnrLOOP UNTIL r0PRINT mEND若INPUT语句中输入m、n的数据分别是72、168，则程序运行的结果为_.【解析】：24 该程序是用辗转相除法求两个数的最大公约数的算法程序，输入72、168，即求它们的最大公约数，可求出它们的最大公约数为24.5若INT(x)表示不超过x的最大整数(如INT(4.3)4，INT(4)4)，则下列程序的目的是( )INPUT x，ymxnyWHILE m/nINT(m/n)cmINT(m/n)*nmnncWENDPRINT nENDA求x，y的最小公倍数 B求x，y的最大公约数C求x被y除的商 D求y除以x的余数【解析】：B这个程序实质上就是辗转相除法，主要用于求两个正整数的最大公约数.6分别用辗转相除法和更相减损术求1734和816的最大公约数.【解析】：辗转相除法：1734816210