黑马程序员技术交流社区

标题: 一个算法题，求大神给出答案 [打印本页]
作者: 奋斗_168    时间: 2015-4-12 13:35
标题: 一个算法题，求大神给出答案
题目：输入两个正整数m和n，求其最大公约数和最小公倍...
作者: Struggle_168    时间: 2015-4-12 13:35
这是我的答案，采用的是辗除法还请采纳哦，
package com.itheima;
//1.程序分析：利用辗除法。

public class Test9
{
//下面的方法是求出最大公约数
public static int gcd(int m, int n)
{
while (true)
{
//返回最小公约数
if ((m = m % n) == 0)
return n;
if ((n = n % m) == 0)
return m;
}
}
public static void main(String args[]) throws Exception
{
//取得输入值
//Scanner chin = new Scanner(System.in);
//int a = chin.nextInt(), b = chin.nextInt();
//例如求a=23,b=32的最小公倍数和最大公约数
int a=23; int b=32;
//由于main函数是静态的，所以这里的gca也必须是静态的。
int c = gcd(a, b);
System.out.println("最小公倍数：" + a * b / c + "\n最大公约数：" + c);
}
}
作者: major2015    时间: 2015-4-12 15:03
  1. /*
  2. * 求最大公约数和最小公倍数
  3. *
  4. * 概念
  5. *
  6. * 最大公约数就是几个数公有的因数中最大的一个
  7. * 假如整数n除以m，结果是无余数的整数，那么我们称m就是n的因数。
  8. * 最小公倍数就是几个数公有的倍数中最小的一个。
  9. * 整数m能够被整数n整除，整数m就是整数n的倍数。
  10. */

  12. public class Demo2 {

  14.         public static void main(String[] args) {

  16.                 int m = 9;
  17.                 int n = 4;
  18.                 System.out.println(最大公约数(m, n));// 调用maxCommonDivisor()方法
  19.                 System.out.println(最小公倍数(m, n));// 调用minCommonMultiple()方法
  20.         }

  22.         // 循环法求最大公约数
  23.         public static int 最大公约数(int m, int n) {
  24.                 // 保证m为较大数，n为较小数。若m<n,则进行数据交换
  25.                 if (m < n) {
  26.                         int temp = m;
  27.                         m = n;
  28.                         n = temp;
  29.                 }
  30.                 // 1.若m除以n余数为0，则最大公约数即为较小数n，返回n
  31.                 // 2.否则，通过交换，将较大数（1中较小数）除以较小数（1中余数），若余数为0，则最大公约数即为较小数，返回n
  32.                 // 3.否则，通过交换，将较大数（2中较小数）除以较小数（2中余数），。。。。
  33.                 // 4.直到找到较大数能除尽较小数的时候（顶点为整数1），最大公约数即为那时候的较小数。
  34.                 while (m % n != 0) {
  35.                         int temp = m % n;
  36.                         m = n;
  37.                         n = temp;
  38.                 }
  39.                 // 返回最大公约数
  40.                 return n;
  41.         }

  43.         // 求最小公倍数等于两个数中的任一数除以最大公约数，再乘上两个数中另外一个数。
  44.         public static int 最小公倍数(int m, int n) {
  45.                 return m * n / 最大公约数(m, n);
  46.         }
  47. }
复制代码
作者: 1017161726    时间: 2015-4-12 19:00
先明确最大公约数和最小公倍数的规则：
m的因子中，和n的因子相同的数中最大的那个，是最大公约数。
m*n/最大公约数=最小公倍数。


class Demo
{
        public static void main(String [] args)
        {
                int m=135;
                int n=12;
                gong(m,n);
                }
        public static void gong(int m,int n)
        {
                if (m>n)
                {
                        int temp=m;
                        m=n;
                        n=temp;
                        }
                int yue=0;                               //定义变量接收最大公约数。
                for (int x=1;x<(m/2+1);x++)
                {
                        if (m%x==0)
                        {
                                if (n%x==0)
                                        yue=x;
                                }
                        }
                int bei=m*n/yue;                             //最小公倍数求法。
                System.out.println("最大公约数是："+yue+",最小公倍数是："+bei);
                }
        }

作者: 弃车保    时间: 2015-4-13 00:27
本帖最后由 弃车保 于 2015-4-13 00:34 编辑
  1. import java.util.*;

  3. public class GreatCD     {
  4.         public static void main(String[] args) throws Exception {
  5.                 int     a ,b,gcd;
  6.                 Scanner s = new Scanner(System.in);
  7.                 System.out.print( "键入一个整数n:");
  8.                 a = s.nextInt();
  9.                 System.out.print( "再键入一个整数m: ");
  10.                 b = s.nextInt();
  11.                 s.close();
  12.                 gcd = gcd(a,b);
  13.                 int gd = a * b / gcd;
  14.             
  15.                 System.out.println("最大公约数: " + gcd);
  16.                 System.out.println("最小公倍数: " + gd);
  17.    
  18. }

  20. static public int gcd(int x, int y) {
  21.         int t;
  22.         if(x < y) {
  23.                 t = x;
  24.                 x = y;
  25.                 y = t;
  26.         }
  27.         while(y != 0) {
  28.                 if(x == y)
  29.                         return x;
  30.                 else {
  31.                         int k = x % y;
  32.                         x = y;
  33.                         y = k;
  34.                         }
  35.                 }
  36.         return x;
  37.         }
  38. }
复制代码

作者: yangqing_tt    时间: 2015-4-13 10:19
看到黑马币，很兴奋！！！我要努力、努力！！！！
作者: itheima_llt    时间: 2015-4-13 10:58
让我先想一想
作者: 静心明德    时间: 2015-4-13 12:45
/**下面的程序给出了一种算法。
    函数 myfunc 接受两个正整数a,b
    经过运算后打印出 它们的最大公约数和最小公倍数
* @(#)GongYueShu_GongBeiShu.java
*/


  2. public class GongYueShu_GongBeiShu {
  3.        
  4.         // 交换数值
  5.         public static void swap(int a,int b)
  6.         {
  7.            int temp;
  8.            temp=a;
  9.            a=b;
  10.            b=temp;
  11.         }
  12.        
  13.         public static void myfunc(int a, int b)
  14.         {
  15.            int m,n,r;  
  16.            if(a<b)
  17.                     swap(a,b);
  18.            m=a;
  19.            n=b;
  20.            r=a%b;
  21.            while(r!=0)
  22.            {
  23.             a=b;b=r;
  24.             r=a%b;
  25.            }
  26.            System.out.println("b:"+b);  // 最大公约数
  27.            System.out.println("最小公倍数:"+ (m*n/b));  // 最小公倍数
  28.         }
  29.        
  30.         public static void main (String args[]){
  31.                
  32.                 new GongYueShu_GongBeiShu().myfunc(15,20);
  33.         }
  34. }
复制代码
作者: rick1991chen    时间: 2015-4-13 21:04
来的晚了只能学（喝）习（点）下（汤）咯。。。
作者: malcold    时间: 2015-4-13 21:09
import java.util.*; public    class     lianxi06     {  public static void main(String[] args) { int     a ,b,m; Scanner s = new Scanner(System.in); System.out.print( "键入一个整数： ");  a = s.nextInt(); System.out.print( "再键入一个整数： ");  b = s.nextInt();       m = deff(a,b);//这是什么意思？？？       int n = a * b / m;       System.out.println("最大公约数: " + m);       System.out.println("最小公倍数: " + n); }  //后面这一段可以不要嘛？是什么意识解释一下？？？ static public int deff(int x, int y) { int t; if(x < y) { t = x; x = y; y = t; } while(y != 0) { if(x == y) return x; else { int k = x % y; x = y; y = k; } } return x; }  }
作者: 知识改变人生    时间: 2015-4-13 21:44
噢噢噢噢哦
作者: 綦敦涛    时间: 2015-4-14 21:21
最大公约数*最小公倍数=两个数的乘积，这样只求一个，第二个就有了，这样算不算偷懒？
作者: ziqingjie    时间: 2015-4-14 22:00
小手一抖，积分到手
作者: windform    时间: 2015-4-15 19:43
哈哈，都一个个是大神啊



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