c++ - 丑数UVA

Closed. This question needs debugging details。它当前不接受答案。












想改善这个问题吗？更新问题，以便将其作为on-topic用于堆栈溢出。

4年前关闭。



Improve this question




我正在尝试从UVA问题集编号中计算第1500个丑数。 136。

(引用:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=72)

我的算法很简单:

跟踪数组un中的所有丑陋数字。

令un [i]为i + 1丑数。

脚步:

使用tmp变量cur来保存第i个丑陋数字的索引。

计算un [cur] x 2，un [cur] x 3和un [cur] x5。

使用集合消除重复项并将其存储到un

中

对数组进行排序，以确保un [i + 1]始终是最小的。

递增cur变量，使其成为第i + 1个丑数的索引。

重复此操作，直到在数组中生成1500个丑陋的数字为止。

我的代码:

# include<iostream>
# include<set>
# include<algorithm>

using namespace std;

int main(void) {
    long long un[1500] = { 0 };
    set<long long> us;
    un[0] = 1;
    us.insert(1);
    int i = 1,unE = 0,cur = 0;

    while(true) {
        unE = 0;
        sort(un,un+i);
        if(us.find(un[cur]*2) == us.end()) {
            un[i+unE] = un[cur]*2;
            us.insert(un[i+unE]);
            unE++;
        }
        if(i + unE > 1500 - 1) {
            break;
        }
        if(us.find(un[cur]*3) == us.end()) {
            un[i+unE] = un[cur]*3;
            us.insert(un[i+unE]);
            unE++;
        }
        if(i + unE > 1500 - 1) {
            break;
        }
        if(us.find(un[cur]*5) == us.end()) {
            un[i+unE] = un[cur]*5;
            us.insert(un[i+unE]);
            unE++;
        }
        i+=unE;
        cur++;
    }
    sort(un,un+1500);

    for(int i = 0; i < 1500; i++) {
        cout << un[i] << " ";
    }
    cout << un[1500-1] << endl;
}

我的算法没有输出正确的数字，即859963392。我得到了一个更大的数字。有人可以指出正确的方向吗？

最佳答案

您的算法几乎是正确的，但是错误是，当生成1500个数字时，您不应停止，而当“curr”达到第1500个数字时，您应该停止。之所以这样，是因为并非生成了“curr”之后的所有丑陋数字，所以您只能确定在任何时候都没有“curr”之前的所有丑陋数字。优化算法的另一个建议是对“curr”之后的所有数字使用堆，这样一来，您不必每次都对整个数组进行排序，也根本不需要使用集合。这是我的代码:

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
vector<long long> un; //using vector because we don't know how many ugly numbers we will need to generate
//If we decide to use an array (the way you did) it is better to define it outside of main().
priority_queue<long long> nun; //priority queue used for storing the next ugly numbers
const int TARGET=1500; //always good to store magical numbers as constants instead of having them appear all over the code
int main()
{
    un.push_back(1); //adding the first ugly number
    for (int i=0;i<TARGET-1;++i)
    /*
    We have already found the first ugly number (1),
    so we only need to find TARGET-1 more.
    */
    {
        nun.push(-un[i]*2);
        nun.push(-un[i]*3);
        nun.push(-un[i]*5);
        //adding the next ugly numbers to the heap
        /*
        Adding them as negative numbers because priority_queue
        keeps the largest number on the top and we need the smallest.
        */
        while (-nun.top()==un[i])
        {
            nun.pop();
            //removing duplicates
            /*
            We can prove that we will never have more than 3 copies
            of a number in the heap and thus that this will not
            affect the performance.
            1) We will never have more than one copy of a number in un.
            2) Each number can be added to nun in 3 different ways:
            by multiplying a number form un by 2, 3 or 5.
            */
        }
        un.push_back(-nun.top());
        nun.pop();
        //adding the next ugly number to un
    }
    cout<<un[TARGET-1]<<endl;
    /*
    Indexing starts at 0 so the TARGETth number is at index TARGET-1.
    */
    return 0;
}

我的程序确实输出859963392，这是正确的答案。

编辑:经过一番思考，我将其归结为线性复杂度。这是代码:

#include<iostream>
#include<vector>
//#include<conio.h>
using namespace std;
vector<long long> un; //using vector because we don't know how many ugly numbers we will need to generate
//If we decide to use an array (the way you did) it is better to define it outside of main().
const int TARGET=1500; //always good to store magical numbers as constants instead of having them appear all over the code
int l2=0,l3=0,l5=0; //store the indexes of the last numbers multiplied by 2, 3 and 5 respectively
int main()
{
    un.push_back(1); //adding the first ugly number
    for (int i=0;i<TARGET-1;++i)
    /*
    We have already found the first ugly number (1),
    so we only need to find TARGET-1 more.
    */
    {
        un.push_back(min(min(un[l2]*2,un[l3]*3),un[l5]*5));
        //adding the next ugly number to un
        if (un[i+1]==un[l2]*2) //checks if 2 multiplied by the number at index l2 has been included in un, if so, increment l2
        {
            ++l2;
        }
        if (un[i+1]==un[l3]*3) //checks if 3 multiplied by the number at index l3 has been included in un, if so, increment l3
        {
            ++l3;
        }
        if (un[i+1]==un[l5]*5) //checks if 5 multiplied by the number at index l5 has been included in un, if so, increment l5
        {
            ++l5;
        }
        /*
        Basically only one of the variables l2, l3 and l5 (the one we used) will be incremented in a cycle unless we can get a number
        in more than one way, in which case incrementing more than one of them is how we avoid duplicates.
        Uncomment the commented code to observe this.
        P.S. @PaulMcKenzie I can deal without a debugger just fine.
        */
        //cerr<<i<<": "<<l2<<"("<<un[l2]*2<<") "<<l3<<"("<<un[l3]*3<<") "<<l5<<"("<<un[l5]*5<<") "<<un[i+1]<<endl;
        //getch();
    }
    cout<<un[TARGET-1]<<endl;
    /*
    Indexing starts at 0 so the TARGETth number is at index TARGET-1.
    */
    return 0;
}

EDIT2:第一个解决方案甚至根本不需要 vector ，因为它不使用先前的数字。因此，您可以使用单个变量在内存上进行优化。这是一个这样的实现:

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
long long un; //last ugly number found
priority_queue<long long> nun; //priority queue used for storing the next ugly numbers
const int TARGET=1500; //always good to store magical numbers as constants instead of having them appear all over the code
int main()
{
    un=1; //adding the first ugly number
    for (int i=0;i<TARGET-1;++i)
    /*
    We have already found the first ugly number (1),
    so we only need to find TARGET-1 more.
    */
    {
        nun.push(-un*2);
        nun.push(-un*3);
        nun.push(-un*5);
        //adding the next ugly numbers to the heap
        /*
        Adding them as negative numbers because priority_queue
        keeps the largest number on the top and we need the smallest.
        */
        while (-nun.top()==un)
        {
            nun.pop();
            //removing duplicates
            /*
            We can prove that we will never have more than 3 copies
            of a number in the heap and thus that this will not
            affect the performance.
            1) We will never have more than one copy of a number in un.
            2) Each number can be added to nun in 3 different ways:
            by multiplying a number form un by 2, 3 or 5.
            */
        }
        un=-nun.top();
        nun.pop();
        //adding the next ugly number to un
    }
    cout<<un<<endl;
    /*
    Indexing starts at 0 so the TARGETth number is at index TARGET-1.
    */
    return 0;
}

总之，我们有2种竞争解决方案(考虑到我们不需要存储数字，最后一种方法比第一种方法更好(或更好)。其中一个具有线性时间复杂度和线性内存复杂度(不过，它不是N，因为更优化的解决方案将释放用于我们不再需要的数字的内存。但是，N变得更大的l5越来越落后于l2和l3，因此，当N接近无穷大时，内存复杂度接近N.)，而另一个具有NlogN时间复杂度和一些我们需要确定的内存复杂度。每次我们向堆中添加3个数字，然后取出1到3之间的任意位置(因为一个数字最多可以出现在堆中3次，并且我们已经取出其中一个副本，因此可以删除其他两个副本) 。因此，它的内存复杂度可能在常数到2N之间。在执行进一步分析之后，我将编辑此答案，但是我的第一印象是，对于较大的Ns，内存复杂度将小于N。

进一步得出结论，线性解在速度上更好，而NlogN解在记忆上可能更好，但这尚未得到证实。

EDIT3:NlogN解决方案绝对在内存方面更差。随着N的增大，越来越多的数字可以被2、3和5整除，直到几乎所有数字都可以被三除。因此，几乎在每个周期我们都从堆中删除了3个数字，因此它不会增长。因此，当N接近无穷大时，内存复杂度接近常数。您可以通过在每个周期或最后输出优先级队列的大小来进行测试。例如，当N = 5000时，堆的大小为1477。但是当N达到10000时，堆的大小仅为2364。

看来此解决方案会更好，但实际上我在原始分析中犯了一个错误。 l5不会越来越落后。正如我为大N所解释的那样，几乎所有数字都可以被三个2、3和5整除。由于l15几乎每次都增加，因此我们需要存储的数字数量几乎保持不变。例如，当N = 5000时，l5 = 4308，由于我们只需要存储l5和N之间的数字，因此我们需要存储690个数字。当N达到10000时，l5 = 8891，我们需要存储1107个数字。它几乎是两倍，因此它趋近于常数并不明显，但是如果我们进行更多测试，则它的速度明显变慢。

从理论上讲，两种内存复杂性应该以大约相同的速度减慢，但是堆大小的初始增加才使它占用更多的内存。

总结(第三次魅力)，线性解决方案在速度和内存方面都更好(如果在我的解决方案中实现了动态内存分配，则不是，因为这样小的N-1500不需要)。

关于c++ - 丑数UVA ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/38420581/