马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。
您需要 登录 才可以下载或查看,没有账号?注册
x
在Python中实现更相减损术非常简单。以下是一个简单的函数,它接受两个整数作为参数,并返回它们的最大公约数(GCD):
python
def gcd_subtraction(a, b):
while a != b:
if a > b:
a -= b
else:
b -= a
return a # 当a和b相等时,返回任意一个作为GCD
# 示例
num1 = 84
num2 = 56
result = gcd_subtraction(num1, num2)
print(f"The greatest common divisor of {num1} and {num2} is: {result}")
这个函数gcd_subtraction通过重复减去较小的数,直到两个数相等为止。当两个数相等时,这个数就是它们的最大公约数。
注意:虽然更相减损术是一种有效的求最大公约数的方法,但在实际应用中,更常见的是使用欧几里得算法(辗转相除法),因为它通常比更相减损术效率更高。以下是使用欧几里得算法实现的函数:
python
def gcd_euclidean(a, b):
while b != 0:
a, b = b, a % b
return a
# 示例
num1 = 84
num2 = 56
result = gcd_euclidean(num1, num2)
print(f"The greatest common divisor of {num1} and {num2} is: {result}")
欧几里得算法通过不断地用较大的数除以较小的数,并将余数替换较小的数,直到余数为0为止。此时,除数就是最大公约数。这种方法比更相减损术更快,因为它减少了每次迭代的步骤数。
|