做校园网站 怎么备案,WordPress写文章本地上传,erp系统可以自学吗,软件开发工具免费题目#xff1a;
丑数是指不能被2,3,5以外的其他素数整除的数。把丑数从小到大排列起来#xff0c;结果如下#xff1a;1,2,3,4,5,6,8,9,10,12,…求第1500个丑数
分析与解答#xff1a;
0.对于任意丑数x#xff1a;2x#xff0c;3x#xff0c;5x也是丑数
1.用优先队…题目
丑数是指不能被2,3,5以外的其他素数整除的数。把丑数从小到大排列起来结果如下1,2,3,4,5,6,8,9,10,12,…求第1500个丑数
分析与解答
0.对于任意丑数x2x3x5x也是丑数
1.用优先队列从小到大保存已生成的丑数2x3x5x//优先队列中最多存三个数
2.利用set存所有的每次生成的丑数如果以前出现过则跳过不存到优先队列和set里
3.每次找x从优先队列队首找保证x是最小的找出来后就删掉x优先队列存2x3x5x
4.找到第1500个的时候由于set的去重判断和优先队列的从小到大的顺序现在出列的一定是第1500个丑数
5.优先队列的优先级
先出队列的元素不是先进队列的元素而是队列中优先级最高的元素 priority_queue int pq pq.top()是最大的数
priority_queue int,vector int ,greater int pq pq.top()是最小的数
priority_queue int,vector int ,cmp pq
struct cmp{bool operator()(const int a,const int b) const{return a%10b%10;}
}
自定义优先级个位数大的整数优先级反而小 pq.top():个位数小的 因为类似于sortcmp排序’’,大各位数放到后面,小的在前面优先级高
6.代码
#includeiostream
#includevector
#includequeue
#includeset
#includefunctional
using namespace std;typedef long long LL;
const int coeff[3] { 2, 3, 5 };
int main()
{priority_queueLL, vectorLL, greaterLL pq;setLL s;pq.push(1);s.insert(1);for (int i 1;; i){LL x pq.top();pq.pop();if (i 1500){cout The 1500th ugly number is x endl;break;}for (int j 0; j 3; j){LL x2 x*coeff[j];if (!s.count(x2)){s.insert(x2);pq.push(x2);}}}return 0;
}
