黑马程序员技术交流社区

标题: 利用数学中的方法来解决两个数的最大公约数的问题 [打印本页]

---

作者: Huylens    时间: 2015-5-9 15:39
标题: 利用数学中的方法来解决两个数的最大公约数的问题

在数学中求最大公约数有多种方法，常见的有质因数相处法、短除法、辗转相除法、更相减损法。

下面主要说说后面两种方法：

辗转相除法也叫欧几里德算法。简单的说就是两个数m和n相除求模（m%n），当模为0的时候，n就是最大公约数；否则，将n赋值给m,将所得的模为n,重复这个步骤。

假设求数字m和数字n的最大公约数，结果最大公约数d

int  tmode;

do{

tmode=m%n;

m=n;

n=tmode;

}while(tmode!=0);

d=m;

更相减损法：就是利用减法。我们知道两个数m和n之间的差就是最大的公约数的K倍（这里的K不确定），然后我们要做的就是逐步逐步的缩小这个K值。

在数学中的解释思路是

       第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

       第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

假设求假设求数字m和数字n的最大公约数，结果最大公约数d；

int  temp;

int d=1;//最大公约数

boolean  ifEven(int a);//判断数字是否是偶数

具体的代码：

if(ifEven(m)){m=m/2;    d=d*2;}

if(ifEven(n)){n=n/2;d=d*2;}

下面是第二步的具体实现过程

int temp=m;do{
if(temp>n)
m=temp;
else{
m=n;
n=temp;
}
temp=m-n;
}while(temp!=0);

最后temp的结果为0的时候，最大公约数就是m;

如有错误欢迎指正！

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2