2020版高中数学 第一章 算法初步 1.3 算法案例 第1课时 辗转相除法与更相减损术学案（含解析

1第1课时辗转相除法与更相减损术学习目标1.了解辗转相除法与更相减损术中的数学原理.2.会求两个数的最大公约数.3.体会案例中的数学素养．知识点一辗转相除法1．辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法．2．辗转相除法的算法步骤第一步，给定两个正整数m，n(mn)．第二步，计算m除以n所得的余数r.第三步，m＝n，n＝r.第四步，若r＝0，则m，n的最大公约数等于m；否则，返回第二步．思考注意到8251＝6105×1＋2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？答案显然8251与6105的公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数．知识点二更相减损术更相减损术的运算步骤第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．1．辗转相除法的基本步骤是用较大的数除以较小的数．(√)2．求最大公约数的方法除辗转相除法之外，没有其他方法．(×)3．编写辗转相除法的程序时，要用到循环语句．(√)2题型一辗转相除法例1试用辗转相除法求228与1995的最大公约数．解1995＝8×228＋171，228＝1×171＋57，171＝3×57，所以228与1995的最大公约数为57.反思感悟辗转相除法的实质：对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到大数被小数除尽，则这时的小数就是原来两个正整数的最大公约数．跟踪训练1用辗转相除法求204与85的最大公约数时，需要做除法的次数是________．答案3解析用辗转相除法可得204÷85＝2……34，85÷34＝2……17，34÷17＝2，此时可以判断204与85的最大公约数是17，做了3次除法得出结果．题型二更相减损术例2试用更相减损术求612,396的最大公约数．解方法一612÷2＝306,396÷2＝198,306÷2＝153,198÷2＝99，∴153－99＝54,99－54＝45,54－45＝9,45－9＝36，36－9＝27,27－9＝18,18－9＝9.∴612,396的最大公约数为9×22＝36.方法二612－396＝216,396－216＝180,216－180＝36,180－36＝144,144－36＝108,108－36＝72,72－36＝36.故36为612,396的最大公约数．反思感悟更相减损术的算法步骤第一步，给定两个正整数m，n，不妨设m＞n.第二步，若m，n都是偶数，则不断用2约简，使它们不同时是偶数，约简后的两个数仍记为m，n.第三步，d＝m－n.第四步，判断“d≠n”是否成立，若是，则将n，d中的较大者记为m，较小者记为n，返回第三步；否则，2kd(k是约简整数2的个数)为所求的最大公约数．3跟踪训练2用更相减损术求261和319的最大公约数．解∵319－261＝58，261－58＝203，203－58＝145，145－58＝87，87－58＝29，58－29＝29，∴319与261的最大公约数为29.求三个正整数的最大公约数典例用辗转相除法和更相减损术两种方法，求三个数72,120,168的最大公约数．解(辗转相除法)：先求120,168的最大公约数．因为168＝120×1＋48,120＝48×2＋24,48＝24×2，所以120,168的最大公约数是24.再求72,24的最大公约数．因为72＝24×3，所以72,24的最大公约数为24，即72,120,168的最大公约数为24.(更相减损术)：先求120,168的最大公约数．168－120＝48,120－48＝72,72－48＝24,48－24＝24，所以120,168的最大公约数为24.再求72,24的最大公约数．72－24＝48,48－24＝24，所以72,24的最大公约数为24，即72,120,168的最大公约数为24.[素养评析](1)求多个正整数的最大公约数，先求两个数的最大公约数，再求这个最大公约数与另一个数的最大公约数，依次类推．(2)求最大公约数，首先要设计运算方案，选择运算方法，求得运算结果，所以说，这类题目是培养学生数学核心素养的重要内容.41．1337与382的最大公约数是()A．3B．382C．191D．201答案C解析1337＝382×3＋191,382＝191×2，所以1337与382的最大公约数是191.2．下列各组关于最大公约数的说法中不正确的是()A．16和12的最大公约数是4B．102和84的最大公约数是6C．85和357的最大公约数是34D．105和315的最大公约数是105答案C解析85和357的最大公约数是17.3．用更相减损术求36与134的最大公约数，第一步应为________．答案先除以2，得到18与67解析∵36与134都是偶数，∴第一步应为先除以2，得到18与67.4．已知a＝333，b＝24，则使得a＝bq＋r(q，r均为自然数，且0≤r＜b)成立的q和r的值分别为________．答案13,21解析用333除以24，商即为q，余数就是r.333÷24＝13……21.5．用辗转相除法求85与51的最大公约数.解85＝51×1＋34，51＝34×1＋17，34＝17×2＋0，所以8与51的最大公约数为17.1．辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数．2．更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数．5一、选择题1．1037和425的最大公约数是()A．51B．17C．9D．3答案B解析∵1037＝425×2＋187，425＝187×2＋51，187＝51×3＋34，51＝34×1＋17，34＝17×2，即1037和425的最大公约数是17.2．用更相减损术求得78和36的最大公约数是()A．24B．18C．12D．6答案D3．用辗转相除法求87与27的最大公约数时，需要进行除法运算的次数是()A．3B．4C．5D．6答案A4．45和150的最大公约数和最小公倍数分别是()A．5,150B．15,450C．450,15D．15,150答案B解析利用辗转相除法求45和150的最大公约数：150＝45×3＋15,45＝15×3，所以45和150的最大公约数为15.所以45和150的最小公倍数为15×(45÷15)×(150÷15)＝450，故选B.5．运行下面的程序，当输入168,72时，输出的结果是()INPUTm，nDOr＝mMODnm＝nn＝rLOOPUNTILr＝0PRINTm6ENDA．12B．24C．36D．72答案B解析分析程序可知，该程序是求168和72的最大公约数，故应输出的结果是24.6．用辗转相除法求得238和306的最大公约数是()A．3B．9C．17D．34答案D7．三个数4557,1953,5115的最大公约数是()A．31B．93C．217D．651答案B8．若mod(m,3)＝2，则m的取值可以是()A．2005B．2006C．2007D．2008答案B二、填空题9．用辗转相除法计算60和48的最大公约数，需要做的除法次数是________．答案2解析60＝48×1＋12,48＝12×4，故需做2次除法．10．用更相减损术求459和357的最大公约数，需进行减法的次数为________．答案5解析利用更相减损术，有459－357＝102,357－102＝255,255－102＝153,153－102＝51,102－51＝51，共进行了5次减法．11．930与868的最大公约数是________．答案62三、解答题12．试用辗转相除法求325,130,270的最大公约数．解∵325＝130×2＋65,130＝65×2，∴325与130的最大公约数是65.∵270＝65×4＋10,65＝10×6＋5,10＝5×2，∴65与270的最大公约数是5，故325,130,270这三个数的最大公约数为5.713．阅读程序：INPUT“m，n＝”；m，nIFn＞mTHENt＝mm＝nn＝tENDIFDOr＝mMODnm＝nn＝rLOOPUNTILr＝0PRINTmEND若输入m，n的值分别是161,368，则输出的结果为________．答案23解析该程序的功能是用辗转相除法求两个数的最大公约数．输入161,368，可求出它们的最大公约数为23.14．我国古代名著《九章算术》用“更相减损术”求两个正整数的最大公约数是一个伟大的创举，这个伟大创举与“辗转相除法”的实质一样．如图所示的程序框图源于“辗转相除法”．当输入a＝6102，b＝2016时，输出的a＝________.答案18解析由程序框图和辗转相除法的计算特点可知6102＝2016×3＋54,2016＝54×37＋18,54＝18×3，由此可得a＝18.8