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/

    10-17 03:13