黑马程序员技术交流社区

标题: 菜鸟级求解:Java求1到20的最小公倍数 [打印本页]
作者: 小丑的媳妇2    时间: 2013-3-11 23:13
标题: 菜鸟级求解:Java求1到20的最小公倍数
本帖最后由 朱荣宁. 于 2013-3-12 23:49 编辑

这是一道编程题 :Java求1到20的最小公倍数

这道题本身的算法思想我觉得并不难,我自己试着想了一种方法,算法思想是:
用短除法，就是先把1-20的数一直除以质数2，直到所有的数都不能整除2为止，再除以3……，依此类推，
最后把除数相乘就行
下面是我运行出的代码:
package beishu;
import java.util.ArrayList;
import java.util.Arrays;
public class beishu
{
     private static ArrayList tagetIntegers=new ArrayList();//存放除数，它们的积就是所求的值；
   private static int[] primes=new int[]{2,3,5,7,11,13,17,19}; //存放的是1-20的质数，可以封装一个方法
   private static int[] datas=new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};//存放数据源
   private static int flag_1=0;//标记，当值为0的时候表示当前质数数据源中的任何一个数都不能除      
   private static int j=0;//primes的下标。当他为7的时候，并且没有数可以短除它的时候 结束（也可以断
                                      datas的所有元素都为1的时候结束，麻烦些）；
   public static void main(String[] args)
{
     int flag_time=0;//标记时间复杂度；
   while(true){
    flag_1=0;
    doit();
     if(j>=primes.length-1 && flag_1==0){
    break;
}
  if(flag_1==0)
{
j++;
}
dataPrint();
flag_time++;
}
resultPrint();

System.out.println(“时间复杂度为：”+flag_time*20);
}

//完成一次短除；
public static void doit() {
for(int i=0;i if(datas%primes[j]==0){
datas=datas/primes[j];
flag_1=1;
}
}
if(flag_1==1){
tagetIntegers.add(primes[j]);
}
}

//打印现在的所有数据；
public static void dataPrint(){
System.out.println(“datas数据源：”+Arrays.toString(datas));
System.out.println(“除数:”+tagetIntegers.toString());
System.out.println(“标记：”+flag_1);
System.out.println(“j的值：”+j);
System.out.println();
}

public static void resultPrint(){
int result=1;
for (Integer i : tagetIntegers) {
result*=i;
}
System.out.println(“最后的结果为：”+result);
}
}



不知道细心的高手发现没有,其实这种方法是来回的判断和调用,复杂度很高,我之前在一本书上看到过穷举法和分解质因数发来解决此类的问题,轮过的高手能不能给出可运行的代码,感激不尽!
作者: 爪哇攻城狮    时间: 2013-3-11 23:23
  1. /**
  2. * 求若干个指定数据的最小公倍数
  3. */
  4. import java.io.*;
  5. public class Main{
  6.     public static final int N = 10; //最多可计算数据的个数
  7.     public static void main(String args[]) throws Exception{
  8.         Main a = new Main();
  9.         int n = a.input("请确定数据的个数 (2<=N<="+N+") : ",2,N); //确定数据个数
  10.         int[] data = new int[n];
  11.         for(int i = 0; i < n; i++){
  12.             data[i]=a.input("",0,0);                              //输入数据
  13.         }
  14.         int result = a.commonMultiple(data);                      //计算
  15.         a.output(data,result);                                    //输出
  16.     }
  17.     /**
  18.      * 欧几里德辗转相除算法,求a、b两个数的最小公倍数
  19.      */
  20.     public int basal(int a,int b){
  21.         int i=a,j=b,s;
  22.         for(;j!=0&&(s=i%j)!=0;i=j,j=s);  //先求a、b的最大公约数j (欧几里德辗转相除算法)
  23.         return (j==0?0:(a*b/j));         //得到最小公倍数 (=他们的乘积除以最大公约数)
  24.     }
  25.     /**
  26.      * 分治算法,求整形数组p中所有元素的最小公倍数
  27.      */
  28.     public int commonMultiple(int p[]){
  29.         if (p.length<=2){
  30.             return (p.length==1?p[0]:basal(p[0],p[1])); //基础步
  31.         }
  32.         int[] t1=new int[p.length/2];
  33.         int[] t2=new int[p.length-t1.length];
  34.         System.arraycopy(p,0,t1,0,t1.length);           //划分步1
  35.         System.arraycopy(p,t1.length,t2,0,t2.length);   //划分步2
  36.         p=null;
  37.         int result1 = commonMultiple(t1);               //治理步1
  38.         int result2 = commonMultiple(t2);               //治理步2
  39.         return basal(result1,result2);                  //组合步
  40.     }
  41.     /**
  42.      * 输入方法,s为提示语,若min==max表示对输入的数大小无限制;否则输入的数应满足 min<=n<=max
  43.      */
  44.     public int input(String s,int min,int max){
  45.             BufferedReader buf=new BufferedReader(new InputStreamReader(System.in));
  46.             int n=0;
  47.             for(;;){
  48.             System.out.print(s);
  49.             try{
  50.                 n=Integer.parseInt(buf.readLine().trim());
  51.             }catch(NumberFormatException e){
  52.                     System.out.println("输入错误...");
  53.                 continue;
  54.             }catch(IOException e){
  55.                     System.out.println(e);
  56.                     System.exit(0);
  57.             }
  58.             if (min==max||n>=min&&n<=max)break;
  59.             System.out.println("输入错误...");
  60.         }
  61.         return n;
  62.     }
  63.     /**
  64.      * 输出方法
  65.      */
  66.     public void output(int[] a,int result){
  67.         System.out.print("[");
  68.         for (int i = 0; i<a.length; i++){
  69.             System.out.print(a[i]+",");
  70.         }
  71.         System.out.println("\b] 的最小公倍数是 "+result);
  72.     }
  73. }
复制代码
我在网上看到的。分享下。看能引起你的思路吗？
作者: 小丑的媳妇2    时间: 2013-3-12 10:56
李松柏 发表于 2013-3-11 23:23
我在网上看到的。分享下。看能引起你的思路吗？

谢谢额 我要的就是这个效果



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