1.3.1算法案例(一)

必修1,3 第一章 集合与函数概念 第一章 算法初步

2 8251

算法案例(一) 算法案例(案例1 案例 辗转相除法与更相减损术

必修1,3 第一章 集合与函数概念 第一章 算法初步

创设情景， 〖创设情景，揭示课题〗 [问题1]:在小学，我们已经学过求最大公约数的知 问题1]:在小学， 1]识，你能求出18与30的最大公约数吗？ 你能求出18与30的最大公约数吗？ 18 的最大公约数吗

2 18 30 3 9 15 3 5 ∴18和30的最大公约 ∴18和30的最大公约 数是2 数是2×3=6.(1) 5 ) 25 5 35 7

方法：先用两个数公有的质 方法：先用两个数公有的质 因数连续去除 连续去除, 因数连续去除,一直除到所得 的商是互质数为止, 的商是互质数为止,然后把所 有的除数连乘起来. 有的除数连乘起来.

练习1(1)求25和35的最大公约数 求49和63的最大公约数 求 和 的最大公约数 的最大公约数,(2)求 和 的最大公约数 的最大公约数. 练习(2) 7 ) 49 7 63 9

所以， 和 的最大公约数为 的最大公约数为5 所以，25和35的最大公约数为

所以， 和 的最大公约数为 的最大公约数为7 所以，49和63的最大公约数为

必修1,3 第一章 集合与函数概念 第一章 算法初步

创设情景， 〖创设情景，揭示课题〗 [问题2]:我们都是利用找公约数的方法来求最 问题2]:我们都是利用找公约数的方法来求最 2]: 大公约数， 大公约数，如果公约数比较大而且根据我们的 观察又不能得到一些公约数， 观察又不能得到一些公约数，我们又应该怎样 求它们的最大公约数？比如求8251 6105的最 8251与 求它们的最大公约数？比如求8251与6105的最 大公约数? 大公约数? 思路1:试值？! 思路 ：试值？!2 8251 2 6150 3 8251 3 6150 4 8251 4 6150 5 8251 5 6150 6 8251 6 6150

何时结束？有何好的方法？ 何时结束？有何好的方法？

必修1,3 第一章 集合与函数概念 第一章 算法初步

案例一：辗转相除法(欧几里得算法) 案例一：辗转相除法(欧几里得算法)观察用辗转相除法求8251和6105的最大公约数的过程 观察用辗转相除法求 和 的最大公约数的过程 第一步 用两数中较大的数除以较小的数，求得商和余数 用两数中较大的数除以较小的数， 8251=6105×1+2146 ×

结论： 的公约数就是6105和2146 结论： 8251和6105的公约数就是 和 的公约数就是 和 的公约数， 的最大公约数， 的公约数，求8251和6105的最大公约数，只要 和 的最大公约数 求出6105和2146的公约数就可以了 的公约数就可以了. 求出6105和2146的公约数就可以了. 第二步 对6105和2146重复第一步的做法 和 重复第一步的做法 6105=2146×2+1813 × 同理6105和2146的最大公约数也是 的最大公约数也是2146和1813 同理 和 的最大公约数也是 和 的最大公约数. 的最大公约数

必修1,3 第一章 集合与函数概念 第一章 算法初步

完整的过程8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 148=37×4+0

例如，用辗转相除法求 例如，用辗转相除法求225和135的最大公约数 和 的

最大公约数 225=135×1+90 135=90×1+45 90=45×2 显然45是 和 的最大公约数 的最大公约数， 显然 是90和45的最大公约数，也就是 225和135的最大公约数 和 的最大公约数

思考： 思考：从上面的两个例子可 以看出计算的规律是什么？ 以看出计算的规律是什么？S1:用大数除以小数 ： S2:除数变成被除数，余数变成除数 ：除数变成被除数， S3:重复S1,直到余数为 ：重复 ，直到余数为0

显然37是 显然 是148和37的最大公约 和 的最大公约 也就是8251和6105的最 数，也就是 和 的最 大公约数

必修1,3 第一章 集合与函数概念 第一章 算法初步

利用辗转相除法求最大公约数的步骤如下： 利用辗转相除法求最大公约数的步骤如下：第一步：用较大的数m除以较小的数n 第一步：用较大的数m除以较小的数n得到一 个商q 和一个余数r (m=n× 个商q0和一个余数r0;(m=n×q0+r0) 第二步： 为最大公约数； 第二步：若r0=0,则n为m,n为最大公约数； ≠0,则用除数n除以余数r 得到一个商q 若r0≠0,则用除数n除以余数r0得到一个商q1和一 个余数r 个余数r1;(n=r0×q1+r1) 第三步： r0为最大公约 第三步：若r1=0,则r0为m, r0为最大公约 ≠0,则用除数r 除以余数r 数；若r1≠0,则用除数r0除以余数r1得到一个商 和一个余数r q2和一个余数r2;(r0=r1×q2+r2) …… 此时所得到的r 依次计算直至r 依次计算直至rn=0,此时所得到的rn-1 ,即 为所求的最大公约数. 为所求的最大公约数.

必修1,3 第一章 集合与函数概念 第一章 算法初步

辗转相除法是一个反复执行 直到余数等于0停止的步骤， 直到余数等于0停止的步骤， 这实际上是一个循环结构. 这实际上是一个循环结构. 用程序框图表示出右边的过程

m=n×q+r8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333

r=m MOD n m=n n=r r=0? 是 否

1813=333×5+148 333=148×2+37 148=37×4+0

必修1,3 第一章 集合与函数概念 第一章 算法初步

思考：画出辗转相除法的程序框图并设计其程序 思考：开始输入两个正数m,n 输入两个正数

r=m MOD nm=n n=r r=0?

否

是输出n 输出

INPUT m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT n END

结束

必修1,3 第一章 集合与函数概念 第一章 算法初步

思考：画出辗转相除法的程序框图并设计其程序 思考：开始输入两个正数m,n 输入两个正数 m<n?

是x=n n=m m=x n=r m=n

否

r=m MOD nr≠0?

是

否输出n 输出

结束

INPUT m,n IF m<n THEN x=n n=m m=x END IF r=m MOD n WHILE r<>0 m=n n=r r=m MOD n WEND PRINT n END

必修1,3 第一章 集合与函数概念 第一章 算法初步

练习2 利用辗转相除法求两数4081与 练习2:利用辗转相除法求两数4081与 4081 20723的最大公约数 的最大公约数. 20723的最大公约数. (53) 20723=4081×5+318; × 4081=318×12+265; × 318=265×1+53; × 265=53×5+0. ×

必修1,3 第一章 集合与函数概念 第一章 算法初步

知识探究( 知识探究(二):更相减损术

1:设两个正整数m n n=k, 1:设两个正整数m>n,若m-n=k,则m与n 设两个正整数 的最大公约数和n 的最大公约数相等. 的最大公约数和n与k的最大公约数相等. 反复利

用这个原理，可求得98 63的最 98与 反复利用这个原理，可求得98与63的最 大公约数为多少？ 大公约数为多少？ 98-63=35, 98-63=35, 63-35=28, 63-35=28, 35-28=7, 35-28=7, 28-7=21, 28-7=21, 21-7=14, 21-7=14, 14-7=7. 14-

必修1,3 第一章 集合与函数概念 第一章 算法初步

《九章算术》——更相减损术 九章算术》 更相减损术 算理：可半者半之，不可半者，副置分母、子之数， 算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之 以少减多，更相减损，求其等也，以等数约之.

第一步：任意给顶两个正整数；判断他们是否都是偶数。 第一步：任意给顶两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步. 若是，则用2约简；若不是则执行第二步.

第二步：以较大的数减较小的数， 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作， 的数比较，并以大数减小数。继续这个操作，直到所得的 减数和差相等为止，则这个等数就是所求的最大公约数. 减数和差相等为止，则这个等数就是所求的最大公约数

必修1,3 第一章 集合与函数概念 第一章 算法初步

2:上述求两个正整数的最大公约数的方 2:上述求两个正整数的最大公约数的方 法称为更相减损术 一般地， 更相减损术. 法称为更相减损术.一般地，用更相减损 术求两个正整数m 的最大公约数， 术求两个正整数m,n的最大公约数，可 以用什么逻辑结构来构造算法？ 以用什么逻辑结构来构造算法？其算法 步骤如何设计？ 步骤如何设计？第一步，给定两个正整数m,n(m>n). 第一步，给定两个正整数m 第二步，计算m 所得的差k. 第二步，计算m-n所得的差k. 第三步，比较n与k的大小，其中大者用m表 第三步，比较n 的大小，其中大者用m 小者用n表示. 示，小者用n表示. 第四步， m=n, 第四步，若m=n,则m,n的最大公约数等于 否则，返回第二步. m;否则，返回第二步.

必修1,3 第一章 集合与函数概念 第一章 算法初步

3:该算法的程序框图如何表示？ 3:该算法的程序框图如何表示？ 该算法的程序框图如何表示开始 输入m, 输入 ，n m≠n? ? m=k否

否

是 k=m-n n>k? ? 是 m=n n=k 输出m 输出 结束

必修1,3 第一章 集合与函数概念 第一章 算法初步

4:该程序框图对应的程序如何表述？ 4:该程序框图对应的程序如何表述？ 该程序框图对应的程序如何表述 开始 m, INPUT m,n WHILE m<>n n 输入m, 输入 ，n k=mk=m-n n>k IF n k THEN 否 m≠n? ? m=n 是 n=k k=m-n m=k ELSE m=k 否 输出m 输出 n>k? ? END IF 是 WEND 结束 m=n PRINT m n=k END

必修1,3 第一章 集合与函数概念 第一章 算法初步

“更相减损术”在中国古代数学专著 更相减损术” 九章算术》中记述为： 《九章算术》中记述为： 可半者半之，不可半者，副置分母、 可半者半之，不可半者，副置分母、子 之数，以少减多，更相减

损，求其等也， 之数，以少减多，更相减损，求其等也， 以等数约之. 以等数约之.

必修1,3 第一章 集合与函数概念 第一章 算法初步

INPUT “m,n=“;m,n IF m<n THEN a=m m=n n=a END IF K=0 WHILE m MOD 2=0 AND n MOD 2=0 m=m/2 n=n/2 k=k+1 WEND d=m- n

While d<>n IF d>n then m=d ELSE m=n n=d End if d=m-n Wend d=2^k*d PRINT d End

必修1,3 第一章 集合与函数概念 第一章 算法初步

理论迁移

例1 分别用辗转相除法和更相减损 术求168 93的最大公约数 168与 的最大公约数. 术求168与93的最大公约数. 辗转相除法：168=93×1+75, 辗转相除法：168=93×1+75, 93=75×1+18, 93=75×1+18, 75=18×4+3, 75=18×4+3, 18=3× 18=3×6.

必修1,3 第一章 集合与函数概念 第一章 算法初步

更相减损术:168-93=75, 更相减损术:168-93=75, :168 93-75=18, 93-75=18, 75-18=57, 75-18=57, 57-18=39, 57-18=39, 39-18=21, 39-18=21, 21-18=3, 21-18=3, 18-3=15, 18-3=15, 15-3=12, 15-3=12, 12-3=9, 12-3=9, 3=6, 9-3=6, 6-3=3.

必修1,3 第一章 集合与函数概念 第一章 算法初步

325,130,270三个数的最大 例2 求325,130,270三个数的最大 公约数. 公约数. 325=130× 因为325=130 2+65,130=65× 因为325=130×2+65,130=65×2, 所以325 130的最大公约数是65. 325与 的最大公约数是65 所以325与130的最大公约数是65. 因为270=65×4+10,65=10×6+5, 因为270=65×4+10,65=10×6+5, 270=65 10=5× 所以65 270最大公约数是 65与 最大公约数是5 10=5×2,所以65与270最大公约数是5. 故325,130,270三个数的最大公约 325,130,270三个数的最大公约 数是5. 数是5.

必修1,3 第一章 集合与函数概念 第一章 算法初步

小结作业 1.辗转相除法 辗转相除法， 1.辗转相除法，就是对于给定的两个正整 用较大的数除以较小的数， 数，用较大的数除以较小的数，若余数不为 则将余数和较小的数构成新的一对数， 零，则将余数和较小的数构成新的一对数， 继续上面的除法，直到大数被小数除尽为止， 继续上面的除法，直到大数被小数除尽为止， 这时的较小的数即为原来两个数的最大公约 数. 更相减损术， 2. 更相减损术，就是对于给定的两个正 整数，用较大的数减去较小的数， 整数，用较大的数减去较小的数，然后将差 和较小的数构成新的一对数， 和较小的数构成新的一对数，继续上面的减 直到差和较小的数相等， 法，直到差和较小的数相等，此时相等的两 数即为原来两个数的最大公约数. 数即为原来两个数的最大公约数.

本文来源：https://www.bwwdw.com/article/iwv1.html