高中数学专题1.3 基本案例-2018-2019学年人教版高一数学基础知识梳理（必修3）（解析版）

3.0 envi 2025-04-14 17 4 797KB 15 页 3知币

侵权投诉

1.3 算法案例

案例一辗转相除法

1.辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法. 它的算法思

想是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数

对，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数．

2.辗转相除法的算法步骤

第一步，给定两个正整数

，

第二步，计算

除以

所得的余数

第三步，

＝

，

＝

第四步，若

＝0，则

，

的最大公约数等于

；

否则，返回第二步 .

【例 1】试用辗转相除法求 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.

【例 2】运行下面的程序，当输入 168,72 时，输出的结果是(　　)

INPUT　m，n

　r＝m MOD n

　m＝n

　n＝r

LOOP UNTIL　r＝0

PRINT　m

END

A.12 B.24

C.36 D.72

【解答】分析程序可知，该程序是求 168 和 72 的最大公约数，故应输出的结果是 24，选 B.

【变式 1】用辗转相除法求 204 与 85 的最大公约数时，需要做除法的次数是 .

【解答】用辗转相除法可得 204÷85＝2……34,85÷34＝2……17,34÷17＝2，此时可以判断 204 与 85 的

最大公约数是 17，做了 3 次除法得出结果.

【变式 2】用辗转相除法求三个数 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.

案例二更相减损术

1.更相减损术是我国古代数学专著《九章算术》中介绍的一种求两个正整数的最大公约数的算法．它的算

法思想是任意给定两个正整数，判断它们是否都是偶数．若是，用 2 约简；若不是，以较大的数减去较小

的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这

个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．

2.运算步骤

第一步，任意给定两个正整数，判断它们是否都是偶数 . 若是，用 2

约简；若不是，执行第二步 .

第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，

直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.

3.程序框图与算法语句

【例 1】试用更相减损术求 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 的最大公约数.

【例 2】如图所示程序框图的算法思路源于我国古代数学名著《九章算术》中的“更相减损术”．执行该

程序框图，若输入的

，

分别为 8，12，则输出的

＝(　　)

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

3 知币 4人已下载

立即下载

高中数学专题1.3 基本案例-2018-2019学年人教版高一数学基础知识梳理（必修3）（解析版）.doc

共15页,预览5页

还剩页未读，继续阅读

高中数学专题1.3 基本案例-2018-2019学年人教版高一数学基础知识梳理（必修3）（解析版）

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: