八、欧几里得算法

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)}'