3．丑陋数

   题目来自http://acm.pku.edu.cn/JudgeOnline/problem?id=1338，我做了一点小改动。

丑陋数是指质因数只包含2，3，5的自然数，例如前十个丑陋数依次为：1, 2, 3, 4, 5, 6, 8, 9, 10, 12。

给定一个自然数n (n <= 1500)，请你求出对应的第n个丑陋数。

函数接口：unsigned long UglyNumber(int n);
输入输出示例：

n = 2， 返回 2； n = 5， 返回 5；n = 7， 返回 8； n = 11， 返回 15；

解决此问题的一种思路就是先建立一个丑陋数表，把前1500个丑陋数全部求出来存储到数组lib[]中，这样只要返回lib[n-1]就好了。

本文分析一些建立丑陋数表的方法。

方法一：很容易想到判断一个数是否为丑陋数的方法，那就是判断它的因子是否只包含2，3，5。最简单的方法就是依次判断各个自然数，直到找齐1500个丑陋数为止。

代码如下：

#define MAX 500
unsigned long UglyNumber(int n)
{
    unsigned long lib[MAX] = {1,};//用来存储丑陋数表 
    unsigned long i, num;
    int k = 1;
    
    for (i=2; k<MAX; n++)
    {
        num = i;
        while (num % 2 == 0)
            num /= 2;
        while (num % 3 == 0)
            num /= 3;
        while (num % 5 == 0)
            num /= 5;
        
        if (num == 1)    //i是丑陋数 
            lib[k++] = i;    
    }

       return lib[n-1];
}   
程序很简洁的，也能得到正确的结果。但是当MAX大于1000的时候，程序就会超时。
原因是要逐个检查i，还要进行多次的求余运算，时间复杂度O（nlogn），当i很大时，耗时多。

方法二：利用任何一个丑陋数都是由比它小的丑陋数乘以2或3或5得到，可以利用已经求得的丑陋数表来判断一个数是否为丑陋数。
代码如下：
#define MAX 500

inline bool Find(const unsigned long lib[], int len, unsigned long data);

unsigned long UglyNumber(int n)
{
    unsigned long lib[MAX] = {1,2,3,4,5,};
    int k = 5;
    unsigned long i;
    
    for (i=6; k<MAX; i++)
    {
        if (i % 2 == 0 && Find(lib, k, i/2))//i能被2整除，且i/2是丑陋数 
            lib[k++] = i;
        else if (i % 3 == 0 && Find(lib, k, i/3))//i能被3整除，且i/3是丑陋数
            lib[k++] = i;
        else if (i % 5 == 0 && Find(lib, k, i/5))//i能被5整除，且i/5是丑陋数
            lib[k++] = i;    
    }
    
    return lib[n-1];
}   

inline bool Find(const unsigned long lib[], int len, unsigned long data)//判断data是否为lib[]的元素 
{
    int i;
    for (i=0; i<len && data>=lib[i]; i++)
    {
        if (data == lib[i])
            return true;        
    }
    return false;
} 

此方法看似比方法一要快，实际上因为每次都要遍历数组lib[]，所花时间比求余运算还多。时间复杂度为O（i*k），比方法一还要高。
看来，计算的瓶颈在于需要逐个判断自然数，当i的值很大时，耗时太多。能否不用排除法，而直接求出丑陋数表呢？我陷入了沉思。

方法三：为了便于分析，我把前50个丑陋数列出来。很快，我发现了规律：
观察数列：1
2 3 5
4 6 9 10 15 25
8 12 18 27 20 30 45 50 75 125
16 24 36 54 81 40 60 90 135 100 150 225 250 375 625
32 48 72 108 162 243 80 120 180。。。 
可以看出每行依次递增3，4， 5，6。。。个元素。以第2行为例，递增的元素分别是
4 = 2 * 2， 6 = 3 * 2， 9 = 3 * 3，后面三个元素10，15，25分别由2，3，5各乘以5得到；    
以第3行为例，递增的元素分别是
8 = 4 * 2， 12 = 6 * 2， 18 = 9 * 2，27 = 9 * 3；
后面六个元素20 30 45 50 75 125分别由4 6 9 10 15 25各乘以5得到；
由此可以得出规律：
设k表示栈顶，由于数组栈已经存储了4个元素{1,2,3,5,}，则k初始值为4。
设第n(n>1)行最左边元素的下标为left，最右边元素的下标为right-1，sum表示第n行的元素个数，其中n初始值为2，sum初始值为1。则对于第n行(n>1)来说，
 sum += n; left = k - sum; right = k;
 根据第n行的元素值，求出第n+1行的各个元素。
 其中前n-1个元素为  for (i=left; i<left+n; i++)
                 lib[k++] = lib[i] * 2;
 第n个元素为 lib[k++] = lib[left+n-1] * 3;
 后面的sum个元素为 for (; left<right; left++)    
            lib[k++] = lib[left] * 5;
依此类推，直到存储了足够的元素。
注意：此处不能以k==MAX为结束标志，因为数组的元素不是递增排列的，有可能遗漏前面较小的元素。
解决方案是宁多勿缺，增大k的取值，经测试当MAX=1500时，取MAX*9较好，注意同时设置lib[MAX*10]；
为防止溢出，把溢出的数值设置为0，注意即便数值很大，发生溢出，也不能跳出循环，因为k值必须递增，以满足前面总结出来的规律。
最后对得到的数组按递增排序，消去前面为0的元素。 
这样得到的丑陋数虽然远大于1500个，但因为时间复杂度不高，反而非常快，是典型的用空间换时间方法。
代码如下：
#define MAX 1500

int Move(unsigned long lib[], int len);
static int Compare(const void *p1, const void *p2); 

unsigned long UglyNumber(int n)
{
    unsigned long lib[MAX*10] = {1,2,3,5,};
    int left, right;
    int k = 4;
    int n = 2;
    int sum = 1;
    
    unsigned long max = MAX*9;        
    while (k < max)
    {
        sum += n;
        left = k - sum;
        right = k;
        
        int i;
        for (i=left; i<left+n; i++)
        {
            if (lib[i] * 2 < LONG_MAX)    //若数值太大（溢出），则取0 
                lib[k++] = lib[i] * 2;
            else
                lib[k++] = 0;
        }
        if (lib[left+n-1] * 3 < LONG_MAX)    //若数值太大（溢出），则取0 
            lib[k++] = lib[left+n-1] * 3;
        else
            lib[k++] = 0;
            
        for (; left<right; left++)    //若数值太大（溢出），则取0 
        {
            if (lib[left] * 5 < LONG_MAX)    
                lib[k++] = lib[left] * 5;
            else
                lib[k++] = 0;
        }                 
        n++;
    }

    qsort(lib, k, sizeof(unsigned long), Compare);//递增排列
    k = Move(lib, k); //去掉数值为0的元素 

    return lib[n-1];
}   

static int Compare(const void *p1, const void *p2)
{
    return (*(unsigned long *)p1) - (*(unsigned long *)p2);
}

int Move(unsigned long lib[], int len)
{
    int i = 0;
    while (lib[i] == 0)
        i++;
    
    int j = 0;
    while (i < len)
        lib[j++] = lib[i++];
        
    return j;
}

评论