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个丑陋的数字为止。
我的代码:
我的算法没有输出正确的数字,即859963392。我得到了一个更大的数字。有人可以指出正确的方向吗?
我的程序确实输出859963392,这是正确的答案。
编辑:经过一番思考,我将其归结为线性复杂度。这是代码:
EDIT2:第一个解决方案甚至根本不需要 vector ,因为它不使用先前的数字。因此,您可以使用单个变量在内存上进行优化。这是一个这样的实现:
总之,我们有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不需要)。
想改善这个问题吗?更新问题,以便将其作为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)
我的算法很简单:
脚步:
我的代码:
# 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