Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The
sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
shows the first 11 ugly
numbers. By convention, 1 is included.
Write a program to find and print the
150′th ugly number.
METHOD 1 (Simple)
Thanks to Nedylko
Draganov for suggesting this solution.
Algorithm:
Loop for all positive integers until ugly
number count is smaller than n, if an integer is ugly than increment ugly number
count.
To check if a number is ugly, divide the number by greatest divisible powers of 2, 3 and 5, if the number becomes 1 then it is an ugly number otherwise not.
For example, let us see how to check for 300 is ugly or not. Greatest divisible power of 2 is 4, after dividing 300 by 4 we get 75. Greatest divisible power of 3 is 3, after dividing 75 by 3 we get 25. Greatest divisible power of 5 is 25, after dividing 25 by 25 we get 1. Since we get 1 finally, 300 is ugly number.
下面是这个简单方法，这里带了可以打印所有小于n的ugly number的程序：
int maxDivide(int num, int div) { while (num % div == 0) { num /= div; } return num; } bool isUgly(int num) { num = maxDivide(num, 2); num = maxDivide(num, 3); num = maxDivide(num, 5); return num == 1? true:false; } int getNthUglyNo(int n) { int c = 0; int i = 0; while (c < n) { if (isUgly(++i)) c++; } return i; } #include <vector> using std::vector; vector<int> getAllUglyNo(int n) { vector<int> rs; for (int i = 1; i <= n; i++) { if (isUgly(i)) rs.push_back(i); } return rs; }
动态规划法：
注意： 可能会有重复的数字要跃过，程序注释出去了。否则答案错误！
细想一下，其实一句话概括就是：
由最小的Ugly number算起，然后每个都分别乘以2,3,5得到最终答案。
class UglyNumbers { public: int getNthUglyNo(int n, vector<int> &rs) { if (n < 1) return n; int n2 = 2, n3 = 3, n5 = 5; int i2 = 0, i3 = 0, i5 = 0; rs.resize(n, 1); for (int i = 1; i < n; i++) { int t = min(n2, min(n3,n5)); if (t == n2) { rs[i] = n2; n2 = rs[++i2]*2; } if (t == n3) //注意：不能使用else，避免重复 { rs[i] = n3; n3 = rs[++i3]*3; } if (t == n5) //注意：不能使用else { rs[i] = n5; n5 = rs[++i5]*5; } } return rs.back(); } };
测试：
int main() { unsigned no = getNthUglyNo(35); printf("ugly no. is %d \n", no); vector<int> rs = getAllUglyNo(35); for (auto x:rs) cout<<x<<" "; cout<<endl; UglyNumbers un; printf("Ugly no. is %d \n", un.getNthUglyNo(35, rs)); for (auto x:rs) cout<<x<<" "; cout<<endl; system("pause"); return 0; }
Geeks 面试题： Ugly Numbers,布布扣,bubuko.com
原文：http://www.cnblogs.com/kenden23/p/3596066.html