题目来自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 500unsigned 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 500inline 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个丑陋数列出来。很快，我发现了规律：观察数列：12 3 54 6 9 10 15 258 12 18 27 20 30 45 50 75 12516 24 36 54 81 40 60 90 135 100 150 225 250 375 62532 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 1500int 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;}
评论