[問題] 如何用遞迴的方式求最大公因數?

[壞人嗎>"<]

最近開始學如何使用遞迴的方式寫一些程式，但典型的求最大公因數用
FOR迴圈的方式我寫的出來，但用呼叫遞迴的方式我卻寫的不出來~"~
請教各位大大幫我我指點一下吧!!!
以下是用FOR迴圈寫的:
import java.io.*;

public class MaxCommomFactor{
static int MaxNum(int a,int b){ /*求最大公因數方法*/
int max,min;
if(a>b){ //將輸入的值比大小,大的放max,小的放min
max=a;
min=b;}
else{
max=b;
min=a;}
int i;
for(i=min;i>=1;i--) //最大公因數從最小的值開始作
{
if((max%i==0)&&(min%i==0))
break;
else
continue;
}
return i;
}
public static void main(String[] args)throws IOException /*主要程式*/
{
System.out.print("請輸入第一個數 : ");
BufferedReader input=new BufferedReader(new InputStreamReader(System.in));
int A=Integer.parseInt(input.readLine());
System.out.print("請輸入第二個數 : ");
int B=Integer.parseInt(input.readLine());
int Big=MaxNum(A,B);
System.out.println("最大公因數 : "+Big);
}
}

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.116.177.113

[淺水中]

※ 引述《FAVORITGREEN (壞人嗎>"<)》之銘言：
: 最近開始學如何使用遞迴的方式寫一些程式，但典型的求最大公因數用
: FOR迴圈的方式我寫的出來，但用呼叫遞迴的方式我卻寫的不出來~"~
: 請教各位大大幫我我指點一下吧!!!
: 以下是用FOR迴圈寫的:
: import java.io.*;
: public class MaxCommomFactor{
: static int MaxNum(int a,int b){ /*求最大公因數方法*/
: int max,min;
: if(a>b){ //將輸入的值比大小,大的放max,小的放min
: max=a;
: min=b;}
: else{
: max=b;
: min=a;}
: int i;
: for(i=min;i>=1;i--) //最大公因數從最小的值開始作
: {
: if((max%i==0)&&(min%i==0))
: break;
: else
: continue;
: }
: return i;
: }
: public static void main(String[] args)throws IOException /*主要程式*/
: {
: System.out.print("請輸入第一個數 : ");
: BufferedReader input=new BufferedReader(new InputStreamReader(System.in));
: int A=Integer.parseInt(input.readLine());
: System.out.print("請輸入第二個數 : ");
: int B=Integer.parseInt(input.readLine());
: int Big=MaxNum(A,B);
: System.out.println("最大公因數 : "+Big);
: }
: }
輾轉相除法
public class gcd{
public static int gcd(int a,int b){
if ( a % b == 0 ){
return b;
}
else{
return gcd(b,a%b);
}
}
public static void main(String[] args){
System.out.println(gcd(100,250));
}
}

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.123.105.36

[壞人嗎>"<]

※ 引述《calais007 (淺水中)》之銘言：
: ※ 引述《FAVORITGREEN (壞人嗎>"<)》之銘言：
: :
: 輾轉相除法
: public class gcd{
: public static int gcd(int a,int b){
: if ( a % b == 0 ){
: return b;
: }
: else{
: return gcd(b,a%b);
: }
: }
: public static void main(String[] args){
: System.out.println(gcd(100,250));
: }
: }
謝謝這位大大的幫忙,原來是利用數學中展轉相除法的原理:
(a,b)=(b,r)的方式!!!我懂了^^~~~大感謝!!!

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.116.177.113