uglynumber的定义是只能被1,2,3,5整除的数
规定1是第一个uglynumber；以此类推，1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 ...
问题1，给定一个非零int整数，判断是否为ugly number
此数除以2,3,5；看是否能被整除；整除的判断是用hasDigit方法，利用小数来判断的
如果能被整除，递归下去，再除以2,3,5；直到完成判断
1 /** 2 * Ugly number1 3 * @author Rust Fisher 4 * Judge the number whether ugly 5 */ 6 public class UglyNumber1 { 7 public static boolean hasDigit(double d){ 8 return d*10%10 != 0; 9 } 10 /** 11 * @param num 12 * @return boolean whether num is ugly 13 */ 14 public static boolean isUgly(int num) { 15 if (num <= 0) { 16 return false; 17 } 18 if (num == 1) { 19 return true; 20 } 21 if (!hasDigit(num/2.0)) { 22 if (isUgly(num/2)) { 23 return true; 24 } 25 } 26 if (!hasDigit(num/3.0)) { 27 if (isUgly(num/3)) { 28 return true; 29 } 30 } 31 if (!hasDigit(num/5.0)) { 32 if (isUgly(num/5)) { 33 return true; 34 } 35 } 36 37 return false; 38 } 39 /** 40 * Find the nth ugly number 41 * @param n 42 * @return the nth ugly number 43 */ 44 public static int nthUglyNumber(int n) { 45 if (n <= 0) { 46 return -1; 47 } 48 int count = 0; 49 int i = 0; 50 while (count <= n){ 51 if (isUgly(i)) { 52 count++; 53 } 54 if (count == n) { 55 break; 56 } 57 i++; 58 59 } 60 return i; 61 } 62 63 public static void main(String args[]){ 64 int count = 0; 65 for (int i = 0; i < 100; i++) { 66 if (isUgly(i)) { 67 count++; 68 System.out.print(i + "\t"); 69 } 70 if (count == 10) { 71 count = 0; 72 System.out.println(); 73 } 74 } 75 System.out.println("\nThe n-th ugly numbers : "); 76 count = 0; 77 for (int i = 1; i < 21; i++) { 78 System.out.print(nthUglyNumber(i) + " "); 79 } 80 System.out.println("\n用这种方式输出第n个ugly number很没效率"); 81 } 82 }
输出：
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72 75 80 81 90 96 The n-th ugly numbers : 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 用这种方式输出第n个ugly number很没效率
问题2：求第n个ugly number
比如第1个ugly number是1，第二个是2，第三个是3 ...
已知1,2,3,5是ugly number，那么接下去的数能够乘以2,3,5得到；一个一个向后推算，直到第n个
设定3个游标，对应因数为2,3,5；利用到因数2一次，index2加一
1 public class UglyNumber2{ 2 public static int getMin(int a,int b,int c){ 3 int min = a < b ? a : b; 4 return min < c ? min : c; 5 } 6 public static int nthUglyNumber(int n) { 7 if (n < 1) { 8 return -1; 9 } 10 int index2 = 0, index3 = 0, index5 = 0; // three index 11 int[] uglyNums = new int[n]; 12 uglyNums[0] = 1; 13 int next = 1; 14 while (next < n) { 15 uglyNums[next] = getMin(uglyNums[index2]*2,uglyNums[index3]*3,uglyNums[index5]*5); 16 if (uglyNums[next] == uglyNums[index2]*2) index2++;// find out which index should move 17 if (uglyNums[next] == uglyNums[index3]*3) index3++;// index moving forward 18 if (uglyNums[next] == uglyNums[index5]*5) index5++; 19 next++; 20 } 21 return uglyNums[next - 1]; 22 } 23 24 public static void main(String args[]){ 25 for (int i = 1; i < 21; i++) { 26 System.out.print(nthUglyNumber(i) + " "); 27 } 28 } 29 }
输出：
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
输出了前20个ugly number
