依次计算直至rn=0，此时所得到的rn-1即为所求的最大公约数。

练习：利用辗转相除法求两数4081与20723的最大公约数(答案：53)

思考1：从上面的两个例子可以看出计算的规律是什么?

算法步骤：

S1：给定两个正整数m,n

S2：用大数除以小数，计算m除以n所得的余数;

S3：除数变成被除数，余数变成除数，即 m=n , n=r

S4：重复S2,直到余数为0，即 若r=0，则m, n的最大公约数为m，否则返回S2

思考2：辗转相除法中的关键步骤是哪种逻辑结构?

辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。

用程序框图表示出右边的过程

m = n×q+r

练习1：利用辗转相除法求两数4081与20723的最大公约数.

思考:你能用当型循环结构构造算法，求两个正整数的最大公约数吗?写出算法步骤、程序框图和程序。

2.更相减损术

我国早期也有解决求最大公约数问题的算法，就是更相减损术。

更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母·子之数，以少减多，更相减损，求其等也，以等数约之。

翻译出来为：

第一步：任意给出两个正数;判断它们是否都是偶数。若是，用2约简;若不是，执行第二步。

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

例2用更相减损术求98与63的最大公约数.

解：由于63不是偶数，把98和63以大数减小数，并辗转相减，即：98-63=35

63-35=28

35-28=7

28-7=21

21-7=14

14-7=7

所以，98与63的最大公约数是7。

练习：用更相减损术求两个正数84与72的最大公约数。(答案：12)

3.比较辗转相除法与更相减损术的区别

(1)都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。

(2)从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到

5.课堂练习

一.用辗转相除法求下列各组数的最大公约数，并在自己编写的BASIC程序中验证。

(1)225;135 (2)98;196 (3)72;168 (4)153;119

二.思考：用求质因数的方法可否求上述4组数的最大公约数?可否利用求质因数的算法设计出程序框图及程序?若能，在电脑上测试自己的程序;若不能说明无法实现的理由。

三.思考：利用辗转相除法是否可以求两数的最大公倍数?试设计程序框图并转换成程序在BASIC中实现。

6.小结：

辗转相除法与更相减损术求最大公约数的计算方法及完整算法程序的编写。

（6）评论设计

作业：P38 A(1)B(2)

课后思考：设计更相减损术求最大公约数的程序框图与算法程序。

（7）反思

精品小编为大家提供的高二数学上册算法与案例教学计划大家仔细阅读了吗?最后祝同学们学习进步。

相关推荐：

人教版高二数学下学期教学计划  

人教版高二数学《函数y=Asin（ωx+ψ》教学计划范文