丑数(Ugly Numbers, UVa 136)

题目描述

我们把只包含因子2、3和5的数称作丑数（Ugly Number）。求按从小到大的顺序的第1500个丑数。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做第一个丑数。

算法实现

版本1：错误版本

//#define LOCAL

#include<iostream>

#include<cstdio>

#include<queue>

/*

输出第1500个丑数

*/

using namespace std;

typedef long long LL;

const int coeff[3]={2,3,5};

int main(){

    #ifdef LOCAL

    freopen("data.in","r",stdin);

    freopen("data.out","w",stdout);

    #endif

    priority_queue<LL,vector<LL>,greater<LL> > pq;//!1

    pq.push(1);//初始化得有1个1.

    for(int i=1;;i++){

        //每次循环都从pq中取出一个丑数，根据这个丑数计算出新的丑数，并注入。

        LL ugly=pq.top();

        pq.pop();

        if(i==1500){cout<<ugly;break;}

        else{

            //通过这个取出的丑数，计算新的丑数，并入队

            for(int i=0;i<3;i++){

                LL x=ugly*coeff[i];

                pq.push(x);

            }

        }

    }

}

以上思路是通过每次从优先队列pq中获取一个丑数，然后通过这个丑数计算出新的丑数，对于任意的丑数x，他的2，3，5倍也都是丑数，通过这样的方法，可以把所有的丑数一网打尽。

但是这个地方没有考虑周全的是，不同的生成方法可能会生成同一个丑数，所以里面肯定有许多次重复了，比如235=325=532=...，所以需要一个数据结构来记录丑数是不是已经出现过了，set集合挺适合的，那么修改代码后如下。

//#define LOCAL

#include<iostream>

#include<cstdio>

#include<queue>

#include<set>

/*

输出第1500个丑数

*/

using namespace std;

typedef long long LL;

const int coeff[3]={2,3,5};

int main(){

    #ifdef LOCAL

    freopen("data.in","r",stdin);

    freopen("data.out","w",stdout);

    #endif

    priority_queue<LL,vector<LL>,greater<LL> > pq;//!1

    set<LL> s;

    pq.push(1);//初始化得有1个1.

    s.insert(1);

    for(int i=1;;i++){

        //每次循环都从pq中取出一个丑数，根据这个丑数计算出新的丑数，并注入。

        LL ugly=pq.top();

        pq.pop();

        if(i==1500){cout<<ugly;break;}

        else{

            //通过这个取出的丑数，计算新的丑数，并入队

            for(int i=0;i<3;i++){

                LL x=ugly*coeff[i];

                if(!s.count(x)){

                    s.insert(x);

                    pq.push(x);

                }

            }

        }

    }

    return 0;

}

巴特西

丑数(Ugly Numbers, UVa 136)

丑数(Ugly Numbers, UVa 136)

题目描述

算法实现

最新文章

热门文章