查找在1到10,000,000之间不算难看的数字

Question

当我试图找出这个不难看的数字时，我遇到了一些问题。丑陋的数字是唯一的素数是2，3或5的数字，那么不是丑陋数的数字呢？我试着找出介于1到10万之间的不难看的数字。我的程序可以解决这个问题，但是看起来有点slow.How，我能让它更快吗？以下是代码：

#include <iostream>
#include <queue>
using namespace std;
typedef pair<unsigned long,int> node_type;
main()
{
    //generates 1500 ugly numbers into result[];
    unsigned long result[1500];
    priority_queue<node_type,vector<node_type>,greater<node_type> > Q;
    Q.push(node_type(1,2));
    for(int i=0;i<1500;i++)
    {
        node_type node = Q.top();
        Q.pop();
    switch(node.second)
    {
        case 2:Q.push(make_pair(node.first*2,2));
        case 3:Q.push(make_pair(node.first*3,3));
        case 5:Q.push(make_pair(node.first*5,5)); 
    }
    result[i]=node.first;
}
/*****************************************************
//Here is the approach I used:
//The initial value of the integer k is 1;
//and will increase by 1 every time 
//k will be checked if it's a ugly number,if not increase by 1,keep doing
//this till k is not a ugly number,then count how much ugly number(we may 
//call it n) is less the the
//current value of k.The result of (k-n) is the order number of this (k)　not ugly
//for example:the 1st not ugly number is 7.
// there are 6 ugly number less than 7,which are 1 2 3 4 5 6,
// k=1-->k==2-->.....k=7, k-n=7-6=1,so 7 is the 1st not ugly number
***************************************************************/
int T;  // The amount of cases
cin>>T;
while(T--)
{
    int n;
    int k=0,i=0,count=0;
    cin>>n;

    while(n)
    {
        if((k+1)==result[i]) {k++;i++;count++;}
        else 
        {
            k++;
            if(k-count==n) {cout<<k<<endl;break;}
        }
    }
}}

最大的问题是它似乎不够快！你能告诉我如何使它更快吗?或者有其他的方法来解决这个问题？

Answer 1

从您的代码中了解，我知道您真正想要的是快速找到n个非丑陋的数字。

你的算法找到第n个非丑陋数是O(N)，你可以用二进制搜索找到它们，它是O(log(N))。

如果T很大的话，我的方法可以节省很多时间。

这是我的密码，换你的。

#include <iostream>
#include <queue>
using namespace std;
typedef pair<unsigned long,int> node_type;
int main()
{
    //generates 1500 ugly numbers into result[];
    unsigned long result[1500];
    priority_queue<node_type,vector<node_type>,greater<node_type> > Q;
    Q.push(node_type(1,2));
    for(int i=0;i<1500;i++)
    {
        node_type node = Q.top();
        Q.pop();
        switch(node.second)
        {
            case 2:Q.push(make_pair(node.first*2,2));
            case 3:Q.push(make_pair(node.first*3,3));
            case 5:Q.push(make_pair(node.first*5,5));
        }
        result[i]=node.first;
    }

    int T;  // The amount of cases
    cin>>T;
    //b_search_data[i] mean the count of non ugly number blow or equal i, i start from 1
    unsigned long b_search_data[1501];

    for (int i=0; i<1500; i++)
    {
        b_search_data[i] = result[i] - i - 1;
    }
    vector<int> search_data(b_search_data, b_search_data+1500);
    while(T--)
    {
        int n;
        int k=0,i=0,count=0;
        cin>>n;
        // use binary search here to find the n-th non ugly number instead your approach
        int position = upper_bound(search_data.begin(), search_data.end(), n-1) - search_data.begin();
        // position means
        cout<<position + n<<endl;
    }
}

Answer 2

生成丑陋的数字可以通过递归函数来实现。

实际上，如果N是丑陋的，那么2*N、3*N和5*N也是丑陋的。

实际上，2*N、3*N和5*N是大于N的丑陋数字，因此您可以修正一个最大值，比如MAX，通过添加2*N、3*N和5*N (这是递归的部分)，看起来比N更难看的数字。

为了停止重复搜索，我们可以将所有找到的数字存储在一组uglies中，因此，当我们获得6作为3*2的乘积时，当我们找到2*3 (也等于6--我们称之为碰撞)时，我们不会添加它(并研究它所有丑陋的后代)。

该程序最终达到：

#include <cstdio>
#include <set>

using namespace std;

const unsigned N = 10000000;

set<unsigned> uglys;
unsigned n_collis = 0;


void srch_ugly(unsigned n)
{
    if (uglys.find(n) != uglys.end()) { /* found in set */
        ++n_collis;
    } else {
        uglys.insert(n);
        if (2*n < N) srch_ugly(2*n);
        if (3*n < N) srch_ugly(3*n);
        if (5*n < N) srch_ugly(5*n);
    } /* if */
} /* srch_ugly(unsigned) */

int main()
{
    unsigned col = 0; /* printing column */

    srch_ugly(1);

    /* print results */    
    printf("%lu uglys.  %u collissions.\n", uglys.size(), n_collis);
    for (set<unsigned>::iterator i = uglys.begin();
            i != uglys.end();
            ++i)
    {
        if (col >= 72) {
            puts("");
            col = 0;
        } /* if */
        col += printf("%s%i", col ? " " : "", *i);
    } /* for */
    if (col) puts("");
} /* main */

备注

很抱歉使用了printf stdio函数，但是我想将72个字符的行剪短，而printf函数返回打印的字符数(我实际上不知道如何从ostream类中获得实际的打印字符数)，所以我使用了它们。