Python数据结构与算法-欧几里算法（p95）

一、欧几里算法原理

1. 欧几里得公式

欧几里得算法：gcd(a,b) = gcd(b, a mod b) ； mod是指模，即a/b取余数。

运算示例： gcd（60,21）= gcd(21,18) = gcd(18,3)=gcd(3,0)

证明略

2. 最大公约数-欧几里得求解

（1）最大公约数定理

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

• 给定两个整数a,b，两个数的所有公共约数中的最大值即为最大公约数 (Greatest Common Divisor, GCD)

• 例:12与16的最大公约数是4。

• 最大公约数求解：

• 欧几里得，又叫辗转相除法

• 《九章算术》:更相减损术

（2）最大公约数求解-欧几里得算法实现

def gcd_1(a,b): # 最大公约数-递归，a，b是两个数值if b == 0: # 递归终止条件return aelse:return gcd_1(b, a % b) # 公式gcd(a,b) = gcd(b, a mod b)print(gcd_1(12,16))def gcd_2(a, b): # 最大公约数-非递归，a，b是两个数值while b > 0: # b = 0时就得的a就是最后求的值r = a % b # 循环中a，b值一直在变化，需要先存储在一个变量中，不能直接用a%ba = bb = rreturn aprint(gcd_2(12,16))

输出结果

4
4

二、欧几里得算法应用——分数计算

1、提出问题

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

2、分数计算代码实现

（1）知识点—__add__()函数

__add__()方法是python的内置方法之一, 是一个一元函数。作用相当于求和运算。

1）__add__(self, other)是同一个类，两个对象相加的实现逻辑：

class Myclass(object):def __init__(self,value):self.value = valuedef __add__(self, other):return self.value + other.value
a = Myclass(1)
b = Myclass(2)
print(a + b) # 实现加法运算

以上代码中，self 只本身对象，other 指另一个对象（同属于Myclass 类）

2）类外部加法使用

class Num:def __init__(self, x):self.x = xnumber = Num(5)    
print(number.x.__add__(6))# 输出结果
11

3) __add__属性-拼接操作

可以进行拼接操作，拼接list和tuple。

b = [7, 8, 9, 10, 11, 12]
d = [19, 20, 21, 22, 23, 24]# 执行了拼接动作，拼接后的值被return出来
g = b.__add__(d)
print(g)# 输出结果
[7, 8, 9, 10, 11, 12, 19, 20, 21, 22, 23, 24]

（2）代码实现-加法

# 分数运算
class Fraction(): # 分数运算的类def __init__(self,a,b): # 传入参数属性，a，b是数字self.a = a # 分子self.b = b # 分母x = self.gcd(a, b) # 分子分母的最大公约数，x不是属性，不需要加self# 约分，分子和分母都除以最大公约数self.a = a / x # 分子化简self.b = b /x # 分母化简def gcd(self, a, b): # a,b最大公约数while b > 0:r = a % ba = b b = rreturn adef lcm(self, a, b): # 最小公倍数# 12 ，16 最大公约数为4# LCM = (12/4) * (16/4) * 4x = self.gcd(a, b)return a / x * b # (a / x) * (b / x) * x 的化简def __add__(self, other): # 加法,是内置函数# 1/12 + 1/20# 分母化成最小公倍数a = self.a # 分子b = self.b # 分母c = other.a # 分子d = other.b # 分母den = self.lcm(b, d) # 找到分母的最小功倍数，作为分母num_a = den / b * a  # 换算分子anum_c = den / d * c  # 换算分子cnum = num_a + num_c # 分子相加return Fraction(num, den) # 分子分母化简def __str__(self) -> str: # 类中的字符串显示的函数return "%d/%d" %(self.a, self.b) # %d表示十进制的整数f = Fraction(30,16) # 实例化类
print(f)a = Fraction(1, 12) # 1/12 实例化类
b = Fraction(1, 20) # 1/20 实例化类
print(a + b)

输出结果

15/8
2/15