当前位置:编程学习 > C/C++ >>

丑数 问题

 
把只包含因子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++ ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,