问题描述

UVa1374快速幂运算迭代深搜法 ，C++初学者，求优化方法

这是我的代码，优化过几次，但是还是很慢很慢，求大神给优化途经，就是在我的代码的进行优化
#include
#include
#include
#include
using namespace std;
bool search(int,set&,int dep,int);
int MAX=1;
int tempMax;
int main()
{
sets;int n;
for(n=2;n!=1000;++n)
{
s.clear();s.insert(1);
size_t maxd=0;
int temp=n;//找出最小的maxd
while(temp!=0)
{
++maxd;
temp/=2;
}
for(;;maxd++)
{
MAX=1;
if(search(n,s,0,maxd))
{
cout<<n<<" "<<maxd<<endl;
break;
}
}
}
while(1);
}

bool search(int n,set&s,int dep,int maxd)
{
if(dep==maxd)
return false;
if(MAX*int(pow(2,maxd-dep-1))
return false;
for(set::reverse_iterator iter1=s.rbegin();iter1!=s.rend();++iter1)
for(set::reverse_iterator iter2=s.rbegin();iter2!=s.rend();++iter2)
{
tempMax=MAX;
int nn=*iter1,m=*iter2;
if(s.find(nn+m)==s.end())
{
if(nn+m==n)
return true;
s.insert(nn+m);
if(nn+m>MAX)
MAX=nn+m;
if(search(n,s,dep+1,maxd))
return true;
else s.erase(nn+m),MAX=tempMax;
}
if(nn>m&&s.find(nn-m)==s.end())
{
if(nn-m==n)
return true;
s.insert(nn-m);
if(search(n,s,dep+1,maxd))
return true;
else s.erase(nn-m);
}
if(nn<m&&s.find(m-nn)==s.end())
{
if(m-nn==n)
return true;
s.insert(m-nn);
if(search(n,s,dep+1,maxd))
return true;
else s.erase(m-nn);
}
}
return false;
}

解决方案

http://blog.csdn.net/helloworld10086/article/details/46944881