Posted on 2006-12-07 01:02
Yemoo'S Java Blog 閱讀(7760)
評論(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));
?????}
?}