作业内容:
1、给出Bezout定理的完整证明。
2、实现GCD算法的迭代版本。
3、实现EGCD算法。输入:a、b两个整数,输出:r、s、d三个整数,满足ar + bs =d。
4、实现一种批处理版本的GCD算法,即,给定一个整数数组,输出其中所有整数的最大公因子。输入:一个整数数组a;输出:一个整数d,是a数组中所有整数的最大公因子。
1、定理证明:
证明:
构造集合S = S =S= {a m + b n : m , n ∈ Z 且 a m + b n > = 0 am+bn:m,n∈Z且am+bn>=0am+bn:m,n∈Z且am+bn>=0}。
显然集合SSS非空,根据良序原则,取其中最小值d = a x + b y d=ax+byd=ax+by.
下面证明d dd为a aa和b bb的公因子.
根据除法定理,有a = q d + r , 0 < = r < d a = qd+r,0<=r<da=qd+r,0<=r<d,q ∈ Z q∈Zq∈Z,则有r = a − q d = a − q ( a x + b y ) = ( 1 − q x ) a + ( − q y ) b ∈ S r = a - qd = a - q(ax+by) = (1-qx)a + (-qy)b∈Sr=a−qd=a−q(ax+by)=(1−qx)a+(−qy)b∈S,又因为d dd是S SS中的最小值,所以r = 0 r = 0r=0,则a ∣ d a|da∣d,同理b ∣ d b|db∣d。所以d dd为a aa和b bb的公因子。
下面证明如果存在a aa和b bb的公因子d ′ d′d′,则 d ′ ∣ d d′|dd′∣d。
设d’是a和b的公因子,则有d = a x + b y d=ax+byd=ax+by = d ′ ( a ′ x + b ′ y ) d'(a'x+b'y)d
y)。所以d ′ ∣ d d′|dd′∣d。
所以ddd为aaa和bbb的最大公因子,即d = g c d ( a , b ) d = gcd(a,b)d=gcd(a,b)。
所以定理成立
2、GCD算法迭代版本
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
int n;
while (b)
{
n = a % b;
a = b;
b = n;
}
return a;
}
int main()
{
int a, b, c = 0;
cin >> a >> b;
c = gcd(a, b);
cout << c << endl;
return 0;
}
3、EGCD算法:
#include<iostream>
using namespace std;
int egcd(int a, int b, int s0, int s1, int r0, int r1, int q)
{
if (b == 0)
{
cout << a << ' ' << r0 << ' ' << s0;
}
else
{
egcd(b, a % b, r1, r0 - q * r1, s1, s0 - q * s1, a / b);
}
}
int main()
{
int a, b, r0, r1, s0, s1, q;
r0 = 1;
r1 = 0;
s0 = 0;
s1 = 1;
q = 0;
cin >> a >> b;
egcd(a, b, r0, r1, s0, s1, q);
return 0;
}
4、批处理GCD算法:
#include <iostream>
using namespace std;
unsigned int gcd(unsigned int a, unsigned int b)
{
int m, n;
if (a == 0) return b;
if (b == 0) return a;
for (m = 0; 0 == (a & 1); ++m)
{
a >>= 1;
}
for (n = 0; 0 == (b & 1); ++n)
{
b >>= 1;
}
if (n < m)
{
m = n;
}
while (true)
{
if (a < b)
{
a = a ^ b;
b = b ^ a;
a = a ^ b;
}
if (0 == (a -= b))
{
return b << m;
}
while (0 == (a & 1))
{
a >>= 1;
}
}
}
unsigned int main()
{
unsigned int a, b, c = 0;
cin >> a >> b;
c = gcd(a, b);
cout << c << endl;
return 0;
}