本文共 1295 字，大约阅读时间需要 4 分钟。

欧几里得算法

1. 概念介绍

约数︰如果整数a能被整数b整除，那么a叫做b的倍数，b叫做a的约数。

如何计算两个数的最大公约数:

1. 欧几里得:辗转相除法（欧几里得算法)
2. 《九章算术》: 更相减损术

欧几里得算法:gcd(a,b)= gcd(b, a mod b)例: gcd(60,21)= gcd(21,18)= gcd(18,3)= gcd(3,0)= 3

应用:实现分数计算

2. 代码

利用欧几里得算法实现一个分数类，支持分数的四则运算。

'''TOPIC: 欧几里得算法-实现分数计算author: Bluetime: 2020-08-23QQ: 2458682080'''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):        while b > 0:            r = a % b            a = b            b = r        return a    # 计算最小公倍数    def zgs(self, a, b):        # 12  16  --> 4        # 3 * 4 * 4 = 48        x = self.gcd(a, b)        return a * b / x    # 分数相加    def __add__(self, other):        # 1/12 + 1/20        a = self.a        b = self.b        c = other.a        d = other.b        # 分母        denominator = self.zgs(b, d)        # 分子        molecule = a * (denominator / b) + c * (denominator / d)        return Fraction(molecule, denominator)    def __str__(self):        return "%d/%d" % (self.a, self.b)# 实现分数的加法a = Fraction(1, 3)  # 1/3b = Fraction(1, 2)  # 1/2print(a + b)  # 1/3 + 1/2

结果为:

5/6

转载地址：http://zdiwi.baihongyu.com/