问题：丑数是指只有2、3或5素数因子的数，比如前11个丑数分别为1、2、3、4、5、6、8、9、10、12、15，现在给定一个正整数n，问第n个丑数是多少？
举例：
输入1：n = 7 输出1：8 输入2：n = 10 输出 2：12 输入3：n = 15 输出3：24 输入4：n = 150 输出4：5832 |
方法一（暴力）：
从1开始一直暴力，判断每个数是否为丑数，是丑数计数器加1，一直到计数器为n为止。
判断x是否为丑数的方法是：将x不断除以2，直到不能除为止，3和5也用同样的方法，如果最后结果为1，表示为丑数，否则不是。
//a一直除以b，直到不能除为止 int maxDivide(int a, int b) { while (a%b == 0) a = a/b; return a; } //检测是否为丑数 int isUgly(int no) { no = maxDivide(no, 2); no = maxDivide(no, 3); no = maxDivide(no, 5); return (no == 1)? 1 : 0; } //得到第n个丑数 int getNthUglyNo(int n) { int i = 1; int count = 1;//计数器 while (count<n) { i++; if (isUgly(i)) count++; } return i; } |
这个算法要检查所有的数，直到第n个，因此效率较低，不过空间复杂度是O(1)。
方法二：动态规划
因为所有的丑数都可以分解成若干个2、3或5，我们可以将丑数分为3个子序列（可能会重复，但已经全部包括在内）：
(1)1*2, 2*2, 3*2, 4*2, 5*2, 6*2, 8*2...
(2)1*3, 2*3, 3*3, 4*3, 5*3, 6*3, 8*3...
(3)1*5, 2*5, 3*5, 4*5, 5*5, 6*5, 8*5....
这些子序列都是由丑数序列(1, 2, 3, 4, 5, 6, 8...)分别乘以2、3或5得到的，因此我们可以从这三个子序列合并得到每个丑数，每步我们都优先选择3个子序列中最小的那个，如果三个子序列的值有相同的，则跳过。
#include <stdio.h> int ugly[10000];//n假设<10000 int min(int a, int b) { return a<b?a:b; } int min(int a, int b, int c) { return min(min(a, b), c); } int getNthUglyNo(int n) { if(ugly[n-1]) return ugly[n-1]; int i; ugly[0] = 1; int i2=0, i3=0, i5=0; int next2=2, next3=3, next5=5, next_ugly; for(i=1;i<n;i++)//求出每个丑数 { next_ugly = min(next2, next3, next5); ugly[i] = next_ugly; if(next_ugly==next2) { i2++; next2 = ugly[i2]*2; } if(next_ugly==next3)//可能去重 { i3++; next3 = ugly[i3]*3; } if(next_ugly==next5)//可能去重 { i5++; next5 = ugly[i5]*5; } } return ugly[n-1]; } |
