八、欧几里得算法


返回

8.1 欧几里得算法

  • 辗转相除,计算最大公约数

  • 公式:gcd(a, b) = gcd(b, a % b)

  • 递归实现

    def gcd(a, b):
        """
        方法一:递归实现
        :param a:
        :param b:
        :return: 最大公约数
        """
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
            
    
  • 循环实现

    def gcd_2(a, b):
        """
        方法一:循环实现
        :param a:
        :param b:
        :return: 最大公约数
        """
        while b > 0:
            a, b = b, a % b
        return a
        
    

8.2 示例

  • 用欧几里得算法实现分数运算

    class Fraction:
        def __init__(self, a, b):
            self.a = a
            self.b = b
            x = self.gcd(a, b)
            self.a /= x
            self.b /= x
    
        @staticmethod
        def gcd(a, b):
            """ 计算最大公约数 """
            while b > 0:
                a, b = b, a % b
            return a
    
        @staticmethod
        def lcm(a, b):
            """ 计算最小公倍数 """
            return a * b / gcd(a, b)
    
        def __add__(self, other):
            """ 加法 """
            down = self.lcm(self.b, other.b)  # 分母
            up = self.a * down / self.b + other.a * down / other.b  # 分子
            return Fraction(up, down)
    
        def __sub__(self, other):
            """ 减法 """
            down = self.lcm(self.b, other.b)  # 分母
            up = self.a * down / self.b - other.a * down / other.b  # 分子
            return Fraction(up, down)
    
        def __mul__(self, other):
            """ 乘法 """
            return Fraction(self.a * other.a, self.b * other.b)
    
        def __str__(self):
            return f'{int(self.a)}/{int(self.b)}'
    
    
返回