《辗转相除法与更相减损术》说课稿
- 格式：docx
- 大小：11.85 KB
- 文档页数：3
辗转相除法与更相减损术说课稿
一、前言
数学中，除法是一个基本的操作，但是在处理一些具体的问题时，我们常常会遇到需要对两个数进行除法运算并求取其最大公因数的情况。而传统的直接调用计算机内置函数进行求解显然是不太实际的，因为不管是调用的时间复杂度还是空间复杂度都相对较高。为此，我们需要研究一些更为高效的求解方法，其中最常见的有辗转相除法和更相减损术两种。
二、辗转相除法
辗转相除法，也叫欧几里得算法(Euclidean algorithm)，是求两个正整数a、b最大公约数的一种方法。基本思想是：用较小的数除较大的数，再用出现的余数去除较小的数，如此反复，直到余数为零为止。其中，每一次用较小的数去除较大的数的操作即为一次“辗转”。而“相除”也就说明了运算过程中的“除法”操作。
以下是辗转相除法的推导过程：
假设有两个正整数a、b（a>b），我们要求它们的最大公约数。
• 首先将a÷b的余数记为r1。
• 若r1=0，则最大公约数为b。
• 若r1≠0，则继续计算b÷r1的余数r2。
• 若r2=0，则最大公约数为r1。
• 若r2≠0，则继续计算r1÷r2的余数r3。
• 以此类推，直到第n次得到余数rn为0，此时最大公约数即为rn-1。
以下为辗转相除法的Python代码实现：
def gcd(a, b):
if a % b == 0:
return b
else:
return gcd(b, a % b)
时间复杂度：O(logn)，空间复杂度：O(logn)。 三、更相减损术
更相减损术，是一种古老的求两个正整数a、b最大公约数的方法。它的基本思想是：每次较大的数减去较小的数，然后继续用较小数去减差值，如此反复，直到减数和差相等为止。而“减”则说明了运算过程中的“减法”操作。
以下是更相减损术的推导过程：
假设有两个正整数a、b（a>b），我们要求它们的最大公约数。
• 首先将a和b中的较大者记为A，较小者记为B。
• 计算A - B的差值C，并将C和B中的较大者记为A，较小者记为B。
• 以此类推，直到减数和差相等为止，此时最大公约数为这个等数。
以下为更相减损术的Python代码实现：
def gcd(a, b):
if a == b:
return a
elif a < b:
return gcd(b, a)
else:
return gcd(a-b, b)
时间复杂度：O(𝑛2)，空间复杂度：O(1)。
四、辗转相除法与更相减损术比较
辗转相除法和更相减损术都是求最大公约数的算法，其中辗转相除法是更为常用的一种。这是因为，传统的更相减损术算法时间复杂度相对较高，在较大的数值范围内运算时间会指数级增长，空间复杂度也相对较高；而辗转相除法则可以在更短的时间内运算出结果，且空间复杂度也比更相减损术要低。
但是在实际的不同情况下，辗转相除法和更相减损术的选择也可能不同，比如：在a和b非常接近的情况下，更相减损术会比辗转相除法效率高；在边界值情况下，例如当a或者b等于1时，更相减损术是一种更好的选择。
五、总结
综上所述，辗转相除法与更相减损术都是求最大公约数的算法，它们各自具有特点，我们可以根据具体情况进行选择。在处理一些较小的数据（例如小于1e7）时，两种算法的运算速度都可以达到我们的要求；但是当数据范围增大时，我们需要选择更优秀的算法来提升程序运行效率，例如更相减损术的优化算法，Knuth写过一篇类似大数据情况下的优化文章。
本文主要通过简述辗转相除法和更相减损术的算法思路，通过Python代码实现进行简单的说明，希望能够帮助大家对这些算法有更深的理解。
