题目描述“丑数”Ugly Numbers\texttt{Ugly Numbers}Ugly Numbers是指那些质因数只包含222、333或555的正整数。通常约定111也算作丑数。前111111个丑数为1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 8,\ 9,\ 10,\ 12,\ 15,\ \dots1,2,3,4,5,6,8,9,10,12,15,…本题要求编写程序找出并输出第150015001500个丑数。输入格式无输入。输出格式输出一行格式为The 1500th ugly number is number.其中number应替换为计算出的第150015001500个丑数。题目分析我们需要生成一个序列序列中的每个数都满足其质因数只包含222、333、555。换句话说对于任意丑数nnn存在非负整数aaa、bbb、ccc使得n2a×3b×5c n 2^a \times 3^b \times 5^cn2a×3b×5c本题的核心在于按顺序生成丑数并找到第150015001500个。解题思路方法一模拟法朴素判断一种直接的方法是从111开始逐个判断每个正整数是否为丑数直到找到第150015001500个为止。判断丑数的方法将该数不断除以222、333、555直到不能再被这三个数整除。若最终结果为111则该数是丑数。优点实现简单易于理解。缺点效率较低因为需要检查很多非丑数。不过对于第150015001500个丑数其值并不大约为8.5×1058.5 \times 10^58.5×105。时间复杂度O(nlogn)O(n \log n)O(nlogn)其中nnn是第150015001500个丑数的值。方法二优先队列法高效生成我们可以利用最小堆优先队列来按顺序生成丑数初始化一个最小堆将111压入堆中。每次从堆中取出最小元素xxx它就是当前最小的丑数。将x×2x \times 2x×2、x×3x \times 3x×3、x×5x \times 5x×5压入堆中若尚未出现过。用一个集合记录已生成的丑数避免重复入堆。重复上述过程直到取出第150015001500个丑数。优点只生成丑数无需判断非丑数效率高。缺点需要额外的数据结构堆和集合。时间复杂度O(nlogn)O(n \log n)O(nlogn)其中n1500n 1500n1500。代码实现方法一代码模拟法// Ugly Numbers// UVa ID: 136// Verdict: Accepted// Submission Date: 2016-01-08// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){longlongintstart1;intcounter1;while(counter1500){start;longlongintnumberstart;while(number%20)number/2;while(number%30)number/3;while(number%50)number/5;if(number1)counter;}coutThe 1500th ugly number is start.endl;return0;}方法二代码优先队列法// Ugly Numbers// UVa ID: 136// Verdict: Accepted// Submission Date: 2016-01-08// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;typedeflonglongintbigNumber;intmain(){intfactors[3]{2,3,5};setbigNumberuglyNumbers;priority_queuebigNumber,vectorbigNumber,greaterbigNumbercandidates;candidates.push(1);for(inti1;i1500;i){bigNumber top;do{topcandidates.top();candidates.pop();}while(uglyNumbers.count(top)0);uglyNumbers.insert(top);for(intj0;j3;j){bigNumber nexttop*factors[j];if(uglyNumbers.count(next)0)candidates.push(next);}if(i1500){coutThe 1500th ugly number is top.endl;break;}}return0;}总结本题展示了两种生成丑数的方法模拟法简单直接适合输入规模不大的情况。优先队列法高效且可扩展适合需要生成大量丑数的场景。两种方法均能快速通过输出结果一致。对于此类“按条件生成序列”的问题优先队列法是一种非常实用的技巧。最终答案第150015001500个丑数为859963392859963392859963392。