黑马程序员技术交流社区

标题: 【基础算法】最大公约数和最小公倍数，用到递归和循环 [打印本页]
作者: 刘伟平    时间: 2012-10-18 12:15
标题: 【基础算法】最大公约数和最小公倍数，用到递归和循环
题目：输入两个正整数m 和n，求其最大公约数和最小公倍数。
程序分析：利用辗除法。
设两数为a、b(b<a)，求它们最大公约数(a、b)的步骤如下：
用b除a，得a=bq......r 1(0≤r)。
若r1=0，则(a，b)=b；若r1≠0，则再用r1除b，得b=r1q......r2 (0≤r2).
若r2=0，则(a，b)=r1，若r2≠0，则继续用r2除r1,……
如此下去，直到能整除为止。其最后一个非零余数即为(a，b)。

另外，最小公倍数等于两数之积除以最大公约数。
  1. class Test06
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.                 System.out.println(getLCM(30,20));
  6.         }
  7.         //求最大公约数
  8.         public static int getGCD(int a,int b)
  9.         {
  10.                 //需确定两数的大小
  11.                 int great=a,low=b;
  12.                 if (a<b)
  13.                 {
  14.                         great = b;
  15.                         low = a;
  16.                         //System.out.println("great="+great+" ; low="+low);
  17.                 }
  18.                 //求余数
  19.                 int r= -1;
  20.                 while(r!=0)
  21.                 {
  22.                         r= great%low;
  23.                         great = low;
  24.                         low=r;
  25.                         //System.out.println("great="+great+" ; low="+low+" ; r="+r);
  26.                 }
  27.                 return great;
  28.         }
  29.         public static int getGCD2(int a,int b)
  30.         {
  31.                 //用递归计算最大公约数
  32.                 int great=a,low=b;
  33.                 if (a<b)
  34.                 {
  35.                         great = b;
  36.                         low = a;
  37.                         System.out.println("great="+great+" ; low="+low);
  38.                 }
  39.                 if (low != 0)
  40.                 {
  41.                         return getGCD2(low,great%low);//递归时return的应该是递归方法的返回值，而不是其中的变量
  42.                 }
  43.                 else
  44.                 {
  45.                         return great;
  46.                 }
  47.         }
  48.         //求最小公倍数。最小公倍数等于两数之积除以最大公约数。
  49.         public static int getLCM(int a,int b)
  50.         {
  51.                 return a*b/getGCD(a,b);
  52.         }
  53. }
复制代码




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