把只包含因子2、3和5的數稱作丑數（Ugly Number）。 例如6、8都是丑數，但14不是，因為它包含因子7。 習慣上我們把1當做是第一個丑數。求按從小到大的順序的第N個丑數。 輸入： 輸入包括一個整數N(1<=N<=1500)。 輸出： 可能有多組測試數據，對於每組數據， 輸出第N個丑數。 樣例輸入： 3 樣例輸出： 3 代碼已AC： 思想：本質就是2 ，3 ，5 的乘積的組合，不過要順序組合，那麼我們的操作就是：每次都將2,3,5乘以一個已經是丑數的數，再比較大小，小的進入數組，然後在比較； 例如：1是丑數，那麼下一個比較 2 * 1、3 * 1和5*1，那麼得到的是2，2進入數組，下面比較的是2*2、3*1 和5*1( 注意因為後面的3*1和5*1的大小並不確定，所以還要繼續進行比較 )得到3進入數組，再比較 2 * 2、3 * 2和5*1.。。。。。 基本算法就是：2 * c2 、3*c3 、5 * c5，ci 是數組的下標，每次都選擇後都ci++一個。。。直到N個丑數。。 [cpp] #include <stdio.h> #include <math.h> long long int min( long long int n1, long long int n2, long long int n3 ) { long long int t = n1 < n2 ? n1 : n2; return t < n3 ? t : n3; } int main() { long long int ug[1500]; int c2 = 0, c3 = 0, c5 = 0, N; ug[0] = 1; N = 1; while( N < 1500 ) { ug[N] = min( ug[c2] * 2, ug[c3] * 3, ug[c5] * 5 ); if( ug[N] == ug[c2] * 2 ) // 因為可能數相等，所以不能else if { c2++; } if( ug[N] == ug[c3] * 3 ) { c3++; } if( ug[N++] == ug[c5] * 5 ) { c5++; } } while( scanf("%d", &N) != EOF ) { printf("%lld\n", ug[N-1]); } return 0; }
