把只包含因子2、3和5的數稱作丑數，例如6是丑數，但14不是，因為它包含因子7，習慣上我們把1當作第一個丑數，求按從小到大的順序的第N個丑數。
輸入描述：整數N
輸出描述：第N個丑數
第一種方法：遍歷每一個整數i，若i能被2或者3或者5整除，count++，直到count = N時跳出循環，打印i

import java.util.Scanner;public class KthUgly {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int count = 0;int i;for (i = 1; ; i++) {if(isUgly(i))count++;if(count == n)break;}System.out.println(i);}private static boolean isUgly(int n){while(n%2 == 0)n = n/2;while(n%3 == 0)n = n/3;while(n%5 == 0)n = n/5;if(n == 1){return true;}return false;} }

但是第一種方法效率不高，不僅要計算丑數，還要考慮非丑數。所以產生了改進的方法：只考慮丑數。下一個丑數是該丑數前面的丑數分別乘以2、3、5中最小的那個數。例如現有丑數序列為1下一個丑數要在12，13，15中選擇最小且大于當前丑數的12，現在的丑數序列變成了1，2.下一個丑數要在13，15，22，23，25中選擇最小其大于當前丑數的13，現在序列變成了1，2，3。下一個丑數要在15，22，23，25，32，33，35中選擇最小且大于當前丑數的22…用一個數組順序存儲每一個丑數

import java.util.Scanner;public class KthUgly {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();System.out.println(getKthUgly(n));}private static int getKthUgly(int n){if(n == 0)return 0;int[] ugly = new int[n];int count = 1;ugly[0] = 1;int index2 = 0;int index3 = 0;int index5 = 0;while(count < n){int min = getMin(ugly[index2]*2, ugly[index3]*3, ugly[index5] *5);ugly[count] = min;while(ugly[index2] * 2 <= ugly[count]) index2++;while(ugly[index3] * 3 <= ugly[count]) index3++;while(ugly[index5] * 5 <= ugly[count]) index5++;count++;}return ugly[n-1];}private static int getMin(int a, int b, int c){return a>b?(b>c?c:b):(a>c?c:a);} }

但是對于此題我有一個很疑惑的點：

因子的定義是假如整數n除以m，結果是無余數的整數，那么我們稱m就是n的因子。
丑數的定義是因子只包含2、3、5的數。

以此看來以上兩個解法是不對的，因為按照代碼可以得出8是丑數，但是根據因子的定義8的因子還包括4，所以8不是丑數。

總結

以上是生活随笔為你收集整理的丑数~~~~的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。