标题：Python 实现欧几里得算法与分数运算
正文：
欧几里得算法，又称辗转相除法，是一种用于计算两个非负整数的最大公约数的算法。在这篇文章中，我们将介绍 Python 中的欧几里得算法的递归和非递归写法，并将其应用于分数运算。
欧几里得算法的递归写法
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
上述代码定义了一个递归函数
欧几里得算法的非递归写法
def gcd_no_rec(a, b):
while b > 0:
r = a % b
a = b
b = r
return a
这段代码展示了欧几里得算法的非递归实现方式。通过循环迭代，不断更新余数，直到余数为 0。
分数运算的实现
class Fraction:
def __init__(self, a, b):
self.a = a
self.b = b
x = self.gcd(a, b)
self.a //= x # 使用地板除，保证结果为整数
self.b //= x
def gcd(self, a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
def lcm(self, a, b):
x = gcd_no_rec(a, b)
return a * b // x # 使用地板除，保证结果为整数
def __add__(self, other):
a = self.a
b = self.b
c = other.a
d = other.b
denominator = self.lcm(b, d)
molecule = a * (denominator // b) + c * (denominator // d)
return Fraction(molecule, denominator)
def __sub__(self, other):
a = self.a
b = self.b
c = other.a
d = other.b
denominator = self.lcm(b, d)
molecule = a * (denominator // b) - c * (denominator // d)
return Fraction(molecule, denominator)
def __mul__(self, other):
a = self.a
b = self.b
c = other.a
d = other.b
molecule = a * c
denominator = b * d
return Fraction(molecule, denominator)
def __truediv__(self, other):
a = self.a
b = self.b
c = other.a
d = other.b
molecule = a * d
denominator = b * c
return Fraction(molecule, denominator)
def __str__(self):
return "%d/%d" % (self.a, self.b)
# 使用示例
f1 = Fraction(30, 15)
f2 = Fraction(4, 6)
print("加法:", f1 + f2)
print("减法:", f1 - f2)
print("乘法:", f1 * f2)
print("除法:", f1 / f2)
这部分代码定义了一个