丑数问题


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

补充：软件开发 , C++ ,

丑数 问题

丑数问题