用递归法求两个数的最大公约数
求两个数的最大公约数的思路是,用辗转现除法
辗转相除法求两个数的最大公约数的步骤如下:
先用小的一个数除大的一个数,得第一个余数;
再用第一个余数除小的一个数,得第二个余数;
又用第二个余数除第一个余数,得第三个余数;
这样逐次用后一个数去除前一个余数,直到余数是0为止.那么,最后一个除数就是所求的最大公约数(如果最后的除数是1,那么原来的两个数是互质数)。
例如:求1515和600的最大公约数,
第一次:用600除1515,商2余315;
第二次:用315除600,商1余285;
第三次:用285除315,商1余30;
第四次:用30除285,商9余15;
第五次:用15除30,商2余0.
1515和600的最大公约数是15.
就相当于用先用m除以n,然后下一次用n替换m,m%n替换n,变成n除以m%n,也就是m–>n,n–>m%n,这样就可以构成递归的关系,用(n,m%n)替换(m,n)。递归的出口就是当余数(上一次的m%n)n为0的时候,最大公约数就是m(上一次的n)。
代码实现如下:
import java.util.Scanner;
public class GCD {
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("请输入两个数:");
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
System.out.print("这两个数的最大公约数为:"+gcd(m,n));
}
static int gcd(int m,int n)
{
if(n==0)return m;
return gcd(n,m%n);
}
}
代码结果如下: