黑马程序员技术交流社区

标题: Java基础算法题（第四天） [打印本页]
作者: 黄小贝    时间: 2012-10-20 03:16
标题: Java基础算法题（第四天）
饭后一道题，天天好心情~~

题目：将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。

表示我擅长把简单的事情复杂化，虽然做出结果了，但是算法实在是太坑爹了，我这里不好意思先贴自己的坑爹算法，目测学妹看到了会鄙视我的。。

先看标准答案~简洁无比~

  1. package day4;

  3. import java.util.Scanner;

  5. public class Test2 {

  7.         public static void main(String[] args) {
  8.                 // 解决要分解的数字
  9.                 System.out.println("请输入要分解的数字(一定要是整数):");
  10.                 Scanner in = new Scanner(System.in);
  11.                 int i = in.nextInt();

  13.                 // 分解方法
  14.                 int k = 2;
  15.                 System.out.print(i + "=");
  16.                 while (i > k) {
  17.                         if (i % k == 0) {
  18.                                 System.out.print(k + "*");
  19.                                 i = i / k;
  20.                         } else {
  21.                                 k++;
  22.                         }
  23.                 }
  24.                 System.out.print(i + ";");
  25.         }
  26. }
复制代码
咳咳，我这里要展示我的坑爹算法了~

看看有没有和我一样这样做的，受上次那道求素数的题的影响，这次我的思路是

（1）算出所有小于 90 的素数
（2）遍历这些素数，然后看看有没有能被90整除的，有的话，把这个整数加入 List
（3）然后用相除的结果递归调用 （1）（2）
  1. package day4;

  3. import java.util.ArrayList;
  4. import java.util.Iterator;
  5. import java.util.List;

  7. /**
  8. * 将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。
  9. *
  10. * @author yellowbaby
  11. *
  12. */
  13. public class Test {

  15.         private static List<Integer> integers = new ArrayList<Integer>();

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

  19.                 decompose(90);
  20.                
  21.                 System.out.println(integers);

  23.         }

  25.         /**
  26.          * 利用递归分解整数 i
  27.          */
  28.         private static void decompose(int i) {

  30.                 List<Integer> primes = getPrime(i);

  32.                 for (Iterator<Integer> it = primes.iterator(); it.hasNext();) {
  33.                         int current = it.next();
  34.                         if (i % current == 0) {
  35.                                 integers.add(current);
  36.                                 decompose(i / current);
  37.                                 break;
  38.                         }
  39.                 }
  40.         }

  42.         /**
  43.          * 得到小于 i 的所有素数
  44.          */
  45.         private static List<Integer> getPrime(int i) {

  47.                 List<Integer> retVal = new ArrayList<Integer>();// 存放所有的素数

  49.                 for (int num = 2; num <= i; num++) {
  50.                         if (isPrime(num)) {
  51.                                 retVal.add(num);
  52.                         }
  53.                 }
  54.                 return retVal;
  55.         }

  57.         /**
  58.          *
  59.          * 判断是否是素数，素数的概念：指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数
  60.          */
  61.         private static boolean isPrime(int num) {
  62.                 for (int i = 2; i*i < num; i++) {
  63.                         if (num % i == 0) {
  64.                                 return false;
  65.                         }
  66.                 }
  67.                 return true;
  68.         }

  70. }
复制代码
作者: 给生活加点料    时间: 2012-10-20 07:26
沙发，顶。
作者: 刘伟平    时间: 2012-10-20 08:34
我当时做的时候也是受到前面求素数那道题目的影响，现在看了答案明白了，直接从2一直++去试除即可，如果k不是素数，那么前面的k肯定已经把此时k的质因数除去了，所以i % k == 0的条件就不可能满足，会直接k++。
我的算法里面有求最小素数的方法，有判断是不是素数的方法，确实没想到这些不用判断。{:soso_e134:}
  1. class  Test04
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.                 //参数传入要分解质因数的正整数
  6.                 resolve(13463634);
  7.         }

  9.         //输出
  10.         public static void resolve(int num)
  11.         {
  12.                 //判断是否是正整数
  13.                 if (num<0)
  14.                 {
  15.                         System.out.println("请输入正整数");
  16.                         return;
  17.                 }
  18.                 String result = num+" = ";
  19.                 int k = 2;
  20.                 while ((k = minRemNum(num)) != num)
  21.                 {
  22.                         result +=k + "*";
  23.                         num = num/k;
  24.                         System.out.println(result);
  25.                 }
  26.                 System.out.println(result+k);
  27.         }

  29.         //获得能整除num的最小素数
  30.         private static int minRemNum(int num)
  31.         {
  32.                 for (int r = 2; r<num+1 ; r++ )
  33.                 {
  34.                         if(isRem(r) && num%r==0)
  35.                                 return r;
  36.                 }
  37.                 return 1;
  38.         }

  40.         //判断参数是否是素数
  41.         private static boolean isRem(int r)
  42.         {
  43.                 for (int m = 2; m<r ; m++ )
  44.                 {
  45.                         if (r%m == 0)
  46.                                 return false;
  47.                 }
  48.                 return true;
  49.         }
  50. }
复制代码
作者: 孙卫营    时间: 2012-10-20 08:41
不错 学习了 c#试试



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