Posted on 2006-12-07 01:02
Yemoo'S Java Blog 阅读(7749)
评论(4) 编辑 收藏 所属分类:
算法与数据结构
/**
*Description:greatest common divisor
*Author:yemoo 2006.12.06
*/
public
class
Pt32{
//
思路：辗转相除法
int
divisor1(
int
m,
int
n){
//
方法一：循环法
int
temp;
if
(m
<
n){
//
if m<n,swap m,n
temp
=
m;
m
=
n;
n
=
temp;
}
while
(m
%
n
!=
0
){
temp
=
n;
n
=
m
%
n;
m
=
temp;
}
return
n;
}
int
divisor2(
int
m,
int
n){
//
方法二：递归法
int
temp;
if
(m
<
n){
temp
=
m;
m
=
n;
n
=
temp;
}
return
divisor22(m,n);
}
int
divisor22(
int
m,
int
n){
if
(m
%
n
==
0
){
return
n;
}
else
{
return
divisor22(n,m
%
n);
}
}
public
static
void
main(String args[]){
KeyboardInput in
=
new
KeyboardInput();
Pt32 obj
=
new
Pt32();
System.out.println(
"
input two integer:
"
);
int
a
=
in.readInt();
int
b
=
in.readInt();
System.out.println(a
+
"
,
"
+
b
+
"
's greatest common divisor is
"
+
obj.divisor2(a,b));
}
}
使用了辗转相除法，分别使用循环和递归方法实现。
吸取dreamstone大哥的程序写法，发现判断m、n大小的部分可以删除，因为如果m<n求余部分会自动交换两个变量。
改进后程序代码（精简了好多哦）：
/**
*Description:greatest common divisor
*Author:yemoo 2006.12.07 */
public class Pt32{
//思路：辗转相除法
int divisor1(int m,int n){ //方法一：循环法
int temp;
while(m%n!=0){
temp=n;
n=m%n;
m=temp;
}
return n;
}
int divisor2(int m,int n){ //方法二：递归法
if(m%n==0){
return n;
}else{
return divisor2(n,m%n);
}
}
public static void main(String args[]){
KeyboardInput in=new KeyboardInput();
Pt32 obj=new Pt32();
System.out.println("input two integer:");
int a=in.readInt();
int b=in.readInt();
System.out.println(a+","+b+"'s greatest common divisor is "+obj.divisor2(a,b));
}
}