欧几里得算法

python实现欧几里得算法代码：

#欧几里得算法
#递归算法实现：
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
print(gcd(12,16))
#非递归算法实现
def gcd1(a,b):
    while b>0:
        r=a%b
        a=b
        b=r
    return a
print(gcd1(12,16))
#定义一个分数类，实现约分和加法等四则运算
class fraction:
    def __init__(self,a,b):
        self.a=a
        self.b=b
        #约分的运算
        x=self.gcd1(a,b)
        self.a/=x
        self.b/=x

    #最大公约数
    @staticmethod
    def gcd1(a, b):
        while b > 0:
            r = a % b
            a = b
            b = r
        return a
    #最小公倍数
    @staticmethod
    def zgs(a,b):
        x=gcd1(a,b)
        return a*b/x
    #分数的加法定义
    def __add__(self, other):
        a=self.a
        b=self.b
        c=other.a
        d=other.b
        fenmu=self.zgs(b,d)
        fenzi=a*(fenmu/b)+(c*fenmu/d)
        return fraction(fenzi,fenmu)
    #输出对应的字符串的函数定义
    def __str__(self):
        return "%d/%d" %(self.a,self.b)

a=fraction(2,4)
b=fraction(1,2)
print(a+b)
print(a)