iLeichun

当前位置:首页数据结构与算法

求最大公约数的算法分析

分类:数据结构与算法  来源:网络  时间:Mar 7, 2011 10:45:32 PM
问题:请编写一个方法,功能是实现传入两个正整数,返回他们的最大公约数

public static int math(int a, int b) {

...

}

分析: 关于这道题的算法有多种,我们今天只研究下面这种算法:

1    public static int math(int a, int b) {

2       int hold = 0;

3       while (b != 0) {

4           hold = a % b;

5           a = b;

6           b = hold;

7       }

8       return a;

9    }

初看这个解法,你可能会一头雾水。再看看,更是不知所云。甚至怀疑这样算是不是可 以得到正确结果,但经过测试你会发现的确可以得到正确结果,这究竟是为什么呢?让我们 来分析一下这个算法,为了便于叙述,把行号加上:

第 1 行,程序调用这个方法时会传入两个正整数 a 和 b

第 2 行,声明一个 int 类型的变量 hold 并赋初值 0;第 3-7 行是一个 while 循环,循环条件是 b!=0;

第 4 行,用 hold 来保存 a%b 的结果

第 5 行,把 b 的值赋给 a

第 6 行,把 hold 的值赋给 b

若 b 不为 0,则进行下一次循环,直到 b=0 时停止循环

最后第 8 行把 a 的值返回。

首先我们假设程序只进行一次循环,也就是说:方法传入 a 和 b 时

第 4 行,hold=a%b=0;

第 5 行,a=b;

第 6 行,b=hold=0;再进行第 3 行判断循环停止

第 8 行,返回 a 的值,也就是第 5 行中方法开始时传入的 b 的值,这说明: 如果 a%b=0 那么 a 和 b 的最大公约数就为 b,

这点好理解,a%b=0 也就是说 a 能被 b 整除,那当然 a 和 b 的最大公约数就是 b 了。 关键是如果不是进行一次,而是进行多次循环呢?

为了便与理解,我把上面的程序改为递归算法:

1    public static int math1(int a, int b) {

2       if (b == 0) {

3           return a;

4       }

5       int hold = a % b;

6       a = b;

7       b = hold;

8       return math1(a, b);

9    }

第 1 行,程序调用这个方法时传入两个正整数 a 和 b

第 2-4 行,如果 b 等于 0 返回 a 的值

第 5 行,声明一个 int 类型的变量 hold 保存 a%b 的结果

第 6 行,把 b 的值赋给 a

第 7 行,把 hold 的值赋给 b

第 8 行,递归调用,直到 b 的值为 0 时返回 a 的值

最后第 8 行把 a 的值返回。

在首次调用这个方法传入 a 和 b 的值时第 3 行肯定不会执行,而是执行 5-8 行的代码, 由第 8行,我们可以看出程序的意思是 a和 b的最大公约数与 b和 a%b 的最大公约数相同。

假设程序进行三次递归:

 

第一次程序传入 a 和 b,

35

30

第二次相当于传入 b 和 a%b,

30

5

第三次相当于传入 a%b 和 0;(上次中 b%(a%b)=0)

5

0

最后程序返回 a%b。

5

 

 

由此我们可以得到如下两个命题:

命题一:a 和 b 的最大公约数与 b 和 a%b 的最大公约数相同;

命题二:如果 b%(a%b)=0,那么 a 和 b 的最大公约数为 a%b,(其中 a,b 都为正整数,且 a%b!=0)。 

如果能证明这两个命题,则上面的算法也就不难理解了:因为程序实际上一直在运用命题一反复进行递归调用,只是在最后两次时运用命题二,得出最后结果。

 我们先看命题一:a 和 b 的最大公约数与 b 和 a%b 的最大公约数相同。 证明:由于 a%b!=0 则 a!=b,当 a<b 时 a%b=a,命题自然成立;

当 a>b  时可设 a 和 b 的最大公约数为 x;

a=mx,b=nx,其中 m 和 n 为正整数且 m 与 n 互质(除 1 之外再无其它公因数) 则可设:a%b=(m-kn)x,其中 k 为正整数

这说明:b 和 a%b 有公因数 x,下面证明 n 与 m-kn 互质 假设 n 与 m-kn 有公因数 y,y 为正整数且 y 不等于 1 则可设:n=py,m-kn=qy,其中 p 和 q 为正整数 那么:m-kn=m-kpy=qy

可得:m=kpy+qy=(kp+q)y

这说明 m 和 n 有公因数 y,与 m 和 n 互质相矛盾,故 n 与 m-kn 互质 由此得 b 和 a%b 的最大公约数也为x,命题一得证。

 

再看命题二:如果 b%(a%b)=0,那么 a 和 b 的最大公约数为 a%b

为了便于证明我们修改一下这个命题:

已知:m 为正整数,a=mb+x(即 a%b=x),b 能被 x 整除(即 b%x=b%(a%b)=0),

求证:a 和 b 的最大公约数为 x(即 a%b) 证明:因为 b 能被 x 整除,故可设

b=nx,(其中 n 为正整数)

则:

a=mb+x

=mnx+x

=(mn+1)x

所以:

a 也能被 x 整除 那么:

a 和 b 的最大公约数一定是 x 的倍数,假设为 kx,其中 k 为正整数 则可设:

a=pkx,b=qkx,其中 p 和 q 都为正整数

那么:

a=mb+x

=mqkx+x

=(mqk+1)x=pkx

故:

mqk+1=pk

解出 k 得:

k=1/(p-mq)

由于:其中 m、p、q、k 都为正整数故:k 的值只能为 1

所以:a 和 b 的最大公约数为 x,命题二得证。