丑數 問題

  把只包含因子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;   }