2019-2020学年高中数学 第一章 算法初步 1.3 算法与案例 第1课时 辗转相除法与更相减损

第一章算法初步1．3算法案例第1课时辗转相除法与更相减损术第一章算法初步考点学习目标核心素养辗转相除法与更相减损术理解辗转相除法与更相减损术的含义，了解其执行过程数学抽象、数学运算、逻辑推理问题导学(1)什么叫辗转相除法？(2)什么叫更相减损术？(3)辗转相除法与更相减损术的区别是什么？1．辗转相除法辗转相除法又叫__________算法，是一种求两个正整数的____________的古老而有效的算法．(1)算法思想对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数．欧几里得最大公约数(2)算法步骤用辗转相除法求两个正整数的最大公约数，其算法步骤如下：第一步，给定两个正整数m，n.第二步，计算m除以n所得的余数r.第三步，m＝n，n＝r.第四步，若r＝0，则m，n的最大公约数等于m，否则，返回第二步．(3)程序框图和相应程序程序框图如图所示，程序如下．2．更相减损术更相减损术是我国古代数学专著《九章算术》中介绍的一种求两个正整数的____________的算法．(1)算法思想任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．最大公约数(2)算法步骤根据上面的算法思想，我们可以整理出更相减损术的算法步骤如下：第一步，输入两个正整数a，b.第二步，判断a是否不等于b，若是，则执行第三步；否则执行第四步．第三步，判断a是否大于b，若是，则a＝a－b，返回第二步；否则执行b＝b－a，返回第二步．第四步，输出a的值．(3)程序框图和相应程序程序框图如图所示，程序如下．有关辗转相除法，下列说法正确的是()A．它和更相减损术一样是求多项式值的一种方法B．基本步骤是用较大的数m除以较小的数n得到除式m＝nq＋r，直到r＜n为止C．基本步骤是用较大的数m除以较小的数n得到除式m＝nq＋r(0≤r＜n)，若r≠0，则将n的值赋给m，r的值赋给n，继续前面步骤，直到r＝0为止D．以上说法皆错解析：选C.由辗转相除法的步骤可知，选项C正确．用更相减损术求294和84的最大公约数时，需做减法运算的次数是()A．2B．3C．4D．5解析：选C.294－84＝210，210－84＝126，126－84＝42，84－42＝42，共做4次减法运算．利用辗转相除法求3869与6497的最大公约数时，第二步是________．解析：第一步应为6497＝3869×1＋2628；第二步应为3869＝2628×1＋1241.答案：3869＝2628×1＋124125与35的最大公约数为________．答案：5用辗转相除法求612与468的最大公约数，并用更相减损术检验所得结果．辗转相除法与更相减损术(求最大公约数)【解】用辗转相除法：612＝468×1＋144，468＝144×3＋36，144＝36×4，即612和468的最大公约数是36.用更相减损术检验：612和468为偶数，两次用2约简得153和117，153－117＝36，117－36＝81，81－36＝45，45－36＝9，36－9＝27，27－9＝18，18－9＝9，所以612和468的最大公约数为9×2×2＝36.(1)辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止．这时的较小的数即为原来两个数的最大公约数．(2)更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数．分别用辗转相除法、更相减损术求204与85的最大公约数．解：(1)用辗转相除法求204与85的最大公约数．204＝85×2＋34，85＝34×2＋17，34＝17×2，因此，204与85的最大公约数是17.(2)用更相减损术求204与85的最大公约数．由于204和85不都是偶数，所以204－85＝119，119－85＝34，85－34＝51，51－34＝17，34－17＝17，因此，204与85的最大公约数是17.如图所示程序框图的算法思路源于我国古代数学名著《九章算术》中的“更相减损术”．执行该程序框图，若输入的a，b分别为8，12，则输出的a＝()数学文化与算法程序框图(辗转相除法与更相减损术的应用)A．4B．2C．0D．14【解析】由程序框图输入的a＝8，b＝12，按程序框图依次执行，可得b＝12－8＝4，a＝8；a＝8－4＝4，b＝4，a＝b.所以输出a＝4，故选A.【答案】A利用辗转相除法或更相减损术求最大公约数的算法思想设计算法程序与框图体现了数学文化与现代数学的高度融合．解决此类问题可以从算法本身出发，根据算法解决，若能够掌握辗转相除法与更相减损术的算法思想，读懂程序框图的含义，求解问题更准确，这是数学文化背景下的典型应用．1．如图所示的程序框图的算法思路来源于我国古代数学名著《九章算术》中的“更相减损术”．执行该程序框图，若输入a，b，i的值分别为6，8，0，则输出的a和i的值分别为()A．0，3B．0，4C．2，3D．2，4解析：选D.当a＝6，b＝8，i＝0时，执行程序框图，则i＝1，此时不满足a＞b，也不满足a＝b，b＝8－6＝2；i＝2，此时满足a＞b，a＝6－2＝4，b＝2；i＝3，此时满足a＞b，a＝4－2＝2，b＝2；i＝4，此时不满足a＞b，满足a＝b，输出a的值为2，i的值为4.故选D.2．设a是一个各位数字都不是0且没有重复数字的三位数，将组成a的3个数字按从小到大排成的三位数记为I(a)，按从大到小排成的三位数记为D(a)(例如a＝815，则I(a)＝158，D(a)＝851)．阅读如图所示的程序框图，运行相应的程序，任意输入一个a，输出的结果b＝________．解析：由题意假设a＝123.当a＝123时，b＝321－123＝198≠123；当a＝198时，b＝981－189＝792≠198；当a＝792时，b＝972－279＝693≠792；当a＝693时，b＝963－369＝594≠693；当a＝594时，b＝954－459＝495≠594；当a＝495时，b＝954－459＝495＝a，终止循环，输出b＝495.答案：4951．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.2．(2019·吉林省长春外国语学校月考)用辗转相除法计算56和264的最大公约数是()A．7B．8C．9D．6解析：选B.因为264＝56×4＋40，56＝40＋16，40＝16×2＋8，16＝8×2，所以最大公约数是8.故选B.3．用更相减损术求36与134的最大公约数，第一步应为________．解析：因为36与134都是偶数，所以第一步应为：先除以2，得到18与67.答案：先除以2，得到18与674．已知a＝333，b＝24，则使得a＝bq＋r(q，r均为自然数，且0≤r＜b)成立的q和r的值分别为________．解析：用333除以24，商即为q，余数就是r.333÷24＝13……21.答案：13，21