求两个数最大公约数微课教案

求两个数最大公约数（微课简案）
您好，本次微课，重点讲解“求两个数最大公约数“的编程实现方法。
微课的内容由5个环节组成：
第一个环节：读程序写结果—分析程序的功能。
第二个环节：展示本程序的题目描述，分析本程序的缺陷，引出“辗转相减法”与“辗转相除法”两种高效求解“最大公约数“的算法
第三个环节：展示两种高效的“求解最大公约数”的算法
第四个环节，剖析各要素，展示用“辗转相除法”编程的过程
第五个环节：布置任务，编程实现“求两个数的最小公倍数”。
下面我们首先进入
第一环节，读程序写结果。请你通读一下程序，然后根据输入，看输出应该是多少？
下面我们一起来分析一下本程序，
可以看出本程序就是要求出m，n的最大公约数。
本程序的题目表述是
我们刚才看到程序实际上用了穷举算法，在长整范围内，循环体被执行的次数有可能超过10^8方，也就是部分合法的数据无法在规定时间内得出结果，是不是有更高效的算法呢？
我们进入第三个环节，展示两种高效的求解最大公约数的方法
第一种，辗转相减法，用实例来讲解这种方法是如何求出最大公约数的
第二种，辗转相除法，思路相近，但更高效。还是用实例来演示。
对于这两种方法，我们本次微课选择用辗转相除法来实现。下
面我们一起来剖析题目要素。找一下刚才的讲解中我们反复要去做的事情，也就是循环体的内容。那么这个循环何时结束，是r=0 这个是结束条件，具体多少次我们不知道，在这样的情况下，我们选择用while循环或者是repeat循环，这两种循环是可以替代的。我们选择用while循环来编写，那么条件是r<>0 去循环，r是多少，因此r的值在循环前要先算出来，其它就是输入与输出，程序就算完成了。你看一下完整的程序同你想的是否一致。
最后一个环节，你的任务--求两个数的最小公倍数，建议首先是用概念来穷举。然后思考是否能利用刚才的高效的算法来求出最小公倍数。
本部分内容就到这，谢谢你的观看。

› 求两个数最大公约数微课教案