1、第一章 算法初步13 算法案例 第一章 算法初步 1.理解辗转相除法与更相减损术的含义，了解其执行过程 2.理解秦九韶算法的计算过程 3理解进位制的概念，能进行不同进位制间的转化第1课时 辗转相除法与更相减损术 第一章 算法初步第一章 算法初步第1课时 辗转相除法与更相减损术1辗转相除法辗转相除法又叫_算法，是一种求两个正整数的_的古老而有效的算法(1)算法思想对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数欧几里得最大公约数(2)算法步骤用辗转相除法求两个正整数的最大公约数
2、，其算法步骤如下：第一步，给定两个正整数 m，n.第二步，计算 m 除以 n 所得的余数 r.第三步，mn，nr.第四步，若 r0，则 m，n 的最大公约数等于 m，否则，返回第二步(3)程序框图和相应程序程序框图如图所示，程序如下：2更相减损术更相减损术是我国古代数学专著九章算术中介绍的一种求两个正整数的_的算法(1)算法思想任意给定两个正整数，判断它们是否都是偶数若是，用 2 约简；若不是，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数最大公约数(2)算法步骤根据上面的算
3、法思想，我们可以整理出更相减损术的算法步骤如下：第一步，输入两个正整数 a，b.第二步，判断 a 是否不等于 b，若是，则执行第三步；否则执行第四步第三步，判断 a 是否大于 b，若是，则 aab，返回第二步；否则执行 bba，返回第二步第四步，输出 a 的值(3)程序框图和相应程序程序框图如图所示，程序如下：有关辗转相除法，下列说法正确的是()A它和更相减损术一样是求多项式值的一种方法B基本步骤是用较大的数 m 除以较小的数 n 得到除式 mnqr，直到 rn 为止C基本步骤是用较大的数 m 除以较小的数 n 得到除式 mnqr(0rn)，若 r0，则将 n 的值赋给 m，r 的值赋给 n，
4、继续前面步骤，直到 r0 为止D以上说法皆错解析：选 C.由辗转相除法的步骤可知，选项 C 正确用更相减损术求 294 和 84 的最大公约数时，需做减法运算的次数是()A2B3 C4D5解析：选 C.29484210，21084126，1268442，844242，共做 4 次减法运算 利用辗转相除法求 3 869 与 6 497 的最大公约数时，第二步是_解析：第一步应为 6 4973 86912 628；第二步应为 3 8692 62811 241.答案：3 8692 62811 24125 与 35 的最大公约数为_答案：5探究点 1 辗转相除法与更相减损术(求最大公约数)用辗转相除法
5、求 612 与 468 的最大公约数，并用更相减损术检验所得结果【解】用辗转相除法：6124681144，468144336，144364，即 612 和 468 的最大公约数是 36.用更相减损术检验：612 和 468 为偶数，两次用 2 约简得 153 和 117，15311736，1173681，813645，45369，36927，27918，1899，所以 612 和 468 的最大公约数为 92236.(1)辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止这时的较小的数即为原来两个
6、数的最大公约数(2)更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数 分别用辗转相除法、更相减损术求 204 与 85的最大公约数解：(1)用辗转相除法求 204 与 85 的最大公约数 20485234，8534217，34172，因此，204 与 85 的最大公约数是 17.(2)用更相减损术求 204 与 85 的最大公约数 由于 204 和 85 不都是偶数，所以 20485119，1198534，853451，513417，341717，因此，204 与 85
7、 的最大公约数是 17.探究点 2 数学文化与算法程序框图(辗转相除法与更相减损术的应用)如图所示程序框图的算法思路源于我国古代数学名著九章算术中的“更相减损术”执行该程序框图，若输入的 a，b 分别为 8，12，则输出的 a()A4B2C0D14【解析】由程序框图输入的 a8，b12，按程序框图依次执行，可得 b1284，a8；a844，b4，ab.所以输出 a4，故选 A.【答案】A利用辗转相除法或更相减损术求最大公约数的算法思想设计算法程序与框图体现了数学文化与现代数学的高度融合解决此类问题可以从算法本身出发，根据算法解决，若能够掌握辗转相除法与更相减损术的算法思想，读懂程序框图的含义，
8、求解问题更准确，这是数学文化背景下的典型应用 1.如图所示的程序框图的算法思路来源于我国古代数学名著九章算术中的“更相减损术”执行该程序框图，若输入 a，b，i 的值分别为 6，8，0，则输出的 a 和i 的值分别为()A0，3B0，4C2，3D2，4解析：选 D.当 a6，b8，i0 时，执行程序框图，则 i1，此时不满足 ab，也不满足 ab，b862；i2，此时满足 ab，a624，b2；i3，此时满足 ab，a422，b2；i4，此时不满足 ab，满足 ab，输出 a 的值为 2，i 的值为 4.故选 D.2设 a 是一个各位数字都不是 0 且没有重复数字的三位数，将组成 a 的 3
9、个数字按从小到大排成的三位数记为 I(a)，按从大到小排成的三位数记为 D(a)(例如 a815，则 I(a)158，D(a)851)阅读如图所示的程序框图，运行相应的程序，任意输入一个 a，输出的结果 b_解析：由题意假设 a123.当 a123 时，b321123198123；当 a198 时，b981189792198；当 a792 时，b972279693792；当 a693 时，b963369594693；当 a594 时，b954459495594；当 a495 时，b954459495a，终止循环，输出 b495.答案：495145 和 150 的最大公约数和最小公倍数分别是()
10、A5，150B15，450C450，15D15，150解析：选 B.利用辗转相除法求 45 和 150 的最大公约数：15045315，45153，45 和 150 的最大公约数为 15.45 和150 的最小公倍数为 15(4515)(15015)450，故选 B.2用更相减损术可求得 78 与 36 的最大公约数是()A24B18C12D6解析：选 D.先用 2 约简得 39，18，391821，21183，18315，15312，1239，936，633.所以所求的最大公约数为 326.3用更相减损术求 36 与 134 的最大公约数，第一步应为_解析：因为 36 与 134 都是偶数，
11、所以第一步应为：先除以 2，得到 18 与 67.答案：先除以 2，得到 18 与 674已知 a333，b24，则使得 abqr(q，r 均为自然数，且 0rb)成立的 q 和 r 的值分别为_解析：用 333 除以 24，商即为 q，余数就是 r.333241321.答案：13，21知识结构深化拓展 辗转相除法与更相减损术的联系和区别(1)联系：都是求最大公约数的方法；二者的实质都是递归的过程；二者都要用循环结构来实现(2)区别：计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显；从结果体现形式来看，辗转相除法体现结果是以相除余数为 0 而得到，而更相减损术则以减数与差相等而得到.本部分内容讲解结束 按ESC键退出全屏播放