注册 登录
编程论坛 C++教室

优先队列使用时出现困惑了,请教。

鬼魅小杨 发布于 2013-11-15 01:04, 383 次点击
程序代码:
#include<iostream>//代码实现的目标是求质因子只包含2,3或5的数,规定1也在这些数中,所以前十项数为1,2,3,4,5,6,8,9,10,12,
#include<queue>
using namespace std;
typedef pair<unsigned long,int> node_type;
int main()
{
    unsigned long result[1500];
    priority_queue<node_type,vector<node_type>,greater<node_type> >Q;
    Q.push(make_pair(1,2));
    for(int i=0;i<1500;i++)
    {
        node_type node=Q.top();
        Q.pop();
        switch(node.second)//在switch这里我就卡住了,代码的结果是对的,但是我想不通result[]数组里面的值是排序好了的
        {
        case 2:Q.push(make_pair(node.first*2,2));//第一次循环时node.first==1,之后入队列,node.first也应该==2,依次类推,之后node.first的值应该是4
        case 3:Q.push(make_pair(node.first*3,3));//8,16才对啊,求大神批评。。。
        case 5:Q.push(make_pair(node.first*5,5));
        }
        result[i]=node.first;
    }
    int n;
    cin>>n;
    while(n>0)
    {
        cout<<result[n-1]<<endl;
        cin>>n;
    }
    return 0;
}
5 回复
#2
rjsp2013-11-15 10:55
看不懂你的算法,也看不懂你的中文
比如“代码的结果是对的”我听不懂是什么意思
比如“但是我想不通result[]数组里面的值是排序好了的”,不知道你想说是“为什么是排序好的”,还是“为什么不是排序好的”
比如“node.first也应该==2”,这个“也”又是谁呢么意思

另外,switch的case后没加 break,不知道是你原意如此,还是漏写了。
#3
rjsp2013-11-15 11:53
吃饭归来,如果想输出前1500个这样的数,代码如下,就是效率不高:
程序代码:
// 求质因子不包含2,3和5之外的数,即 1,2,3,4,5,6,8,9,10,12,……
#include <iostream>
using namespace std;

int main()
{
    for( unsigned i=0, n=1; n!=0 && i<1500; ++n )
    {
        unsigned m = n;
        for( ; m%2==0; m/=2 );
        for( ; m%3==0; m/=3 );
        for( ; m%5==0; m/=5 );
        if( m == 1 )
        {
            cout << n << ' ';
            ++i;
        }
    }

    return 0;
}


#4
鬼魅小杨2013-11-15 13:19
回复 2楼 rjsp
switch函数我用的时候没加break,这样三个case都能循环到,
这段代码我昨晚想了很长时间,就在使用优先队列的时候卡住了,switch函数在循环到时候,先开始进队列的是1,
之后再进的是2,再进的时候,因为4没有3大,3优先进入,以此类推。。。
  我的算法应该没错啊,哪里没看懂?
#5
鬼魅小杨2013-11-15 13:25
回复 3楼 rjsp
看了你的代码,很感谢
 但是我感觉这个效率的复杂度太大了,
我之前也用了for语句的循环来写,就是3个for循环嵌套,
程序代码:

#define MAX 10000000
for(i=1;i<MAX;i*=5)
for(j=1;j*i<MAX;j*=3)
for(k=1;i*j*k<MAX;j*=2)
s[n++]=i*j*k;

不过老是凑不到1500个数。。
#6
a1902054602013-11-16 19:31
同意楼上
1