2020版高中数学第一章算法初步1.3算法案例第1课时辗转相除法与更相减损术学案（含解析）新人教A版必修3.docx

第1课时辗转相除法与更相减损术学习目标1.了解辗转相除法与更相减损术中的数学原理.2.会求两个数的最大公约数.3.体会案例中的数学素养知识点一辗转相除法1辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法2辗转相除法的算法步骤第一步，给定两个正整数m，n(mn)第二步，计算m除以n所得的余数r.第三步，mn，nr.第四步，若r0，则m，n的最大公约数等于m；否则，返回第二步思考注意到8251610512146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？答案显然8251与6105的公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数知识点二更相减损术更相减损术的运算步骤第一步，任意给定两个正整数，判断它们是否都是偶数若是，用2约简；若不是，执行第二步第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数1辗转相除法的基本步骤是用较大的数除以较小的数()2求最大公约数的方法除辗转相除法之外，没有其他方法()3编写辗转相除法的程序时，要用到循环语句()题型一辗转相除法例1试用辗转相除法求228与1995的最大公约数解19958228171，228117157，171357，所以228与1995的最大公约数为57.反思感悟辗转相除法的实质：对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到大数被小数除尽，则这时的小数就是原来两个正整数的最大公约数跟踪训练1用辗转相除法求204与85的最大公约数时，需要做除法的次数是_答案3解析用辗转相除法可得20485234，8534217，34172，此时可以判断204与85的最大公约数是17，做了3次除法得出结果题型二更相减损术例2试用更相减损术求612,396的最大公约数解方法一6122306,3962198,3062153,198299，1539954,995445,54459,45936，36927,27918,1899.612,396的最大公约数为92236.方法二612396216,396216180,21618036,18036144,14436108,1083672,723636.故36为612,396的最大公约数反思感悟更相减损术的算法步骤第一步，给定两个正整数m，n，不妨设mn.第二步，若m，n都是偶数，则不断用2约简，使它们不同时是偶数，约简后的两个数仍记为m，n.第三步，dmn.第四步，判断“dn”是否成立，若是，则将n，d中的较大者记为m，较小者记为n，返回第三步；否则，2kd(k是约简整数2的个数)为所求的最大公约数跟踪训练2用更相减损术求261和319的最大公约数解31926158，26158203，20358145，1455887，875829，582929，319与261的最大公约数为29.求三个正整数的最大公约数典例用辗转相除法和更相减损术两种方法，求三个数72,120,168的最大公约数解(辗转相除法)：先求120,168的最大公约数因为168120148,12048224,48242，所以120,168的最大公约数是24.再求72,24的最大公约数因为72243，所以72,24的最大公约数为24，即72,120,168的最大公约数为24.(更相减损术)：先求120,168的最大公约数16812048,1204872,724824,482424，所以120,168的最大公约数为24.再求72,24的最大公约数722448,482424，所以72,24的最大公约数为24，即72,120,168的最大公约数为24.素养评析(1)求多个正整数的最大公约数，先求两个数的最大公约数，再求这个最大公约数与另一个数的最大公约数，依次类推(2)求最大公约数，首先要设计运算方案，选择运算方法，求得运算结果，所以说，这类题目是培养学生数学核心素养的重要内容.11337与382的最大公约数是()A3B382C191D201答案C解3821912，所以1337与382的最大公约数是191.2下列各组关于最大公约数的说法中不正确的是()A16和12的最大公约数是4B102和84的最大公约数是6C85和357的最大公约数是34D105和315的最大公约数是105答案C解析85和357的最大公约数是17.3用更相减损术求36与134的最大公约数，第一步应为_答案先除以2，得到18与67解析36与134都是偶数，第一步应为先除以2，得到18与67.4已知a333，b24，则使得abqr(q，r均为自然数，且0rb)成立的q和r的值分别为_答案13,21解析用333除以24，商即为q，余数就是r.333241321.5用辗转相除法求85与51的最大公约数.解8551134，5134117，341720，所以8与51的最大公约数为17.1辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数2更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数一、选择题11037和425的最大公约数是()A51B17C9D3答案B解析10374252187，425187251，18751334，5134117，34172，即1037和425的最大公约数是17.2用更相减损术求得78和36的最大公约数是()A24B18C12D6答案D3用辗转相除法求87与27的最大公约数时，需要进行除法运算的次数是()A3B4C5D6答案A445和150的最大公约数和最小公倍数分别是()A5,150B15,450C450,15D15,150答案B解析利用辗转相除法求45和150的最大公约数：15045315,45153，所以45和150的最大公约数为15.所以45和150的最小公倍数为15(4515)(15015)450，故选B.5运行下面的程序，当输入168,72时，输出的结果是()INPUTm，nDOrmMODnmnnrLOOPUNTILr0PRINTmENDA12B24C36D72答案B解析分析程序可知，该程序是求168和72的最大公约数，故应输出的结果是24.6用辗转相除法求得238和306的最大公约数是()A3B9C17D34答案D7三个数4557,1953,5115的最大公约数是()A31B93C217D651答案B8若mod(m,3)2，则m的取值可以是()A2005B2006C2007D2008答案B二、填空题9用辗转相除法计算60和48的最大公约数，需要做的除法次数是_答案2解析6048112,48124，故需做2次除法10用更相减损术求459和357的最大公约数，需进行减法的次数为_答案5解析利用更相减损术，有459357102,357102255,255102153,15310251,1025151，共进行了5次减法11930与868的最大公约数是_答案62三、解答题12试用辗转相除法求325,130,270的最大公约数解325130265,130652，325与130的最大公约数是65.27065410,651065,1052，65与270的最大公约数是5，故325,130,270这三个数的最大公约数为5.13阅读程序：INPUT“m，n”；m，nIFnmTHENtmmnntENDIFDOrmMODnmnnrLOOPUNTILr0PRINTmEND若输入m，n的值分别是161,368，则输出的结果为_答案23解析该程序的功能是用辗转相除法求两个数的最大公约数输入161,368