文章目录
欧几里得算法历史发展表示证明代码例题 扩展欧几里得算法表示求解方法代码其他定理:例题欧几里得算法
历史发展
欧几里得算法用来求得两个数的最大公约数,大约公元前300年首次出现于几何原本,又称作辗转相除法,不过似乎不是来源于欧几里得,有人称来自于毕达哥拉斯学院的数学家。
虽然世界分隔,可是历史的进程似乎总会有相似,欧几里得算法后来先后被印度人、中国人独立发现。虽然语言不同、风俗不同、文化不同。但人们都发现了同样的真理,实是让人惊叹。
“欧几里得算法是所有算法的鼻祖,因为它是现存最古老的非凡算法。” ----高德纳,《计算机程序设计艺术,第二卷:半数值算法》,第二版 (1981), p. 318.
表示
g c d ( a , b ) gcd(a,b) gcd(a,b): 表示整数 a , b a,b a,b的最大公约数。 a ∣ d a | d a∣d: 表示 d d d能整除 a a a。则欧几里得算法可以表示为:
g c d ( a , b ) = g c d ( b , a % b ) gcd(a,b) = gcd(b, a\%b) gcd(a,b)=gcd(b,a%b)
证明
思路:令 D 1 D_1 D1为 a , b a, b a,b的公约数集合, D 2 D_2 D2为 b , a % b b, a\%b b,a%b的公约数集合。我们证明 D 1 = D 2 D_1 = D_2 D1=D2, 公约数集合相同,最大公约数自然相同。步骤: 证明 ∀ d ∈ D 1 , 则 d ∈ D 2 \forall d \in D_1, 则d\in D_2 ∀d∈D1,则d∈D2:令 r = a % b , 有 a = k b + r → r = a − k b 令r = a \% b, 有a = kb + r \rightarrow r = a - kb 令r=a%b,有a=kb+r→r=a−kb
∀ d ∈ D 1 , 有 a ∣ d , b ∣ d . 又 r = a − k b , 故 r ∣ d \forall d \in D_1, 有 a|d, b|d. 又 r = a -kb, 故 r|d ∀d∈D1,有a∣d,b∣d.又r=a−kb,故r∣d
因 此 有 r ∣ d , b ∣ d , 故 d ∈ D 2 因此有 r|d, b|d, 故d \in D_2 因此有r∣d,b∣d,故d∈D2.证明 ∀ d ∈ D 2 , 则 d ∈ D 1 \forall d \in D_2, 则d\in D_1 ∀d∈D2,则d∈D1:
∀ d ∈ D 2 , 有 r ∣ d , b ∣ d , 又 a = k b + r , 故 a ∣ d , 又 b ∣ d , 因 此 d ∈ D 1 \forall d \in D_2, 有 r|d, b|d, 又a = kb+r, 故a|d, 又b|d,因此d \in D_1 ∀d∈D2,有r∣d,b∣d,又a=kb+r,故a∣d,又b∣d,因此d∈D1.得证
代码
int gcd(int a, int b){if(b == 0){return a;}else{return gcd(b, a%b);}}
例题
线段上的格点数扩展欧几里得算法
表示
扩展欧几里得算法是用递归的方式求解 x , y x, y x,y,使其满足。
a x + b y = g c d ( a , b ) ax + by = gcd(a, b) ax+by=gcd(a,b)
求解方法
采用递归思想
递归出口: b=0。
b = 0 , 则 g c d ( a , b ) = a , 因 此 x o u t = 1 , y o u t = 0 b = 0, 则gcd(a, b) = a, 因此x_{out}=1, y_{out}=0 b=0,则gcd(a,b)=a,因此xout=1,yout=0建立联系:
如何将b变成0呢?注意到欧几里得算法其实就是一个逐渐将b变成0的过程。借助欧几里得算法,我们有:
令 a x 1 + b x 2 = g c d ( a , b ) 令 ax_1 + bx_2 = gcd(a, b) 令ax1+bx2=gcd(a,b)
令 b x 2 + ( a % b ) y 2 = g c d ( b , a % b ) 令 bx_2 + (a\%b)y_2 = gcd(b, a\%b) 令bx2+(a%b)y2=gcd(b,a%b)
由 欧 几 里 得 定 理 , g c d ( a , b ) = g c d ( b , a % b ) , 因 此 由欧几里得定理, gcd(a, b) = gcd(b, a\%b), 因此 由欧几里得定理,gcd(a,b)=gcd(b,a%b),因此
a x 1 + b x 2 = b x 2 + ( a % b ) y 2 = b x 2 + ( a − a / b ∗ b ) y 2 ( 针 对 C 语 言 ) ax_1 + bx_2 = bx_2 + (a\%b)y_2 = bx_2 + (a-a/b*b)y_2(针对C语言) ax1+bx2=bx2+(a%b)y2=bx2+(a−a/b∗b)y2(针对C语言)
我 们 已 知 底 层 出 口 的 ( x o u t , y o u t ) , 因 此 我 们 需 要 求 出 ( x , y ) 的 递 归 式 我们已知底层出口的(x_{out},y_{out}),因此我们需要求出(x,y)的递归式 我们已知底层出口的(xout,yout),因此我们需要求出(x,y)的递归式
对 a , b 合 并 同 类 项 , a x 1 + b y 1 = a y 2 + b ∗ ( x 2 − a / b ∗ y 2 ) 对a,b合并同类项,ax_1+by_1 = ay_2 + b * (x_2 - a/b*y_2) 对a,b合并同类项,ax1+by1=ay2+b∗(x2−a/b∗y2)
因 此 x 1 = y 2 , y 1 = x 2 − a / b ∗ y 2 因此x_1 = y_2, y_1 = x_2 - a/b*y_2 因此x1=y2,y1=x2−a/b∗y2
这样自底向上,便可求得最终的 ( x , y ) (x,y) (x,y)
代码
int extend_ojld(int a, int b, int &x, int &y){int d;if(b == 0){d = a;x = 1;y = 0;}else{d = extend_ojld(b, a%b, y, x);y -= (a / b) * x;}return d;}