`
phinecos
  • 浏览: 339841 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

HDU1016 Prime Ring Problem

 
阅读更多

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1016

<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

递归法:(简单但会超时。。。)

#include<iostream>
#include
<vector>
#include
<cmath>
usingnamespacestd;

voidswap(int&a,int&b)
{
inttmp;
tmp
=a;
a
=b;
b
=tmp;
}

boolisPrime(intnum)
{
for(inti=2;i<=sqrt(static_cast<double>(num));++i)
{
if(num%i==0)
{
returnfalse;
}

}

returntrue;
}


boolisOK(constvector<int>&v)
{//判断是否是素数环
boolresult=true;
for(inti=0;i<v.size()-1;++i)
{
if(isPrime((v[i]+v[i+1]))==false)
{
result
=false;
break;
}

}

if(isPrime(v[0]+v[v.size()-1])==false)
{
result
=false;
}

returnresult;

}

voidRerange(vector<int>&v,intm,intn)
{
if(m==n)
{
if(isOK(v))
{
for(intj=0;j<=m;++j)
{
if(j==m)
{
cout
<<v[j]<<endl;
}

else
{
cout
<<v[j]<<"";
}

}


}

}

else
{
for(inti=m;i<=n;i+=2)
{
swap(v[m],v[i]);
Rerange(v,m
+1,n);
swap(v[m],v[i]);
}

}

}


intmain(intargc,char*argv[])
{
intn,i,curCase=1,tmp;
while(cin>>n)
{
cout
<<"Case"<<curCase<<":"<<endl;
vector
<int>numVector;
if(n%2==0)
{
for(i=0;i<n;++i)
{
numVector.push_back(i
+1);
}

Rerange(numVector,
1,numVector.size()-1);
}

cout
<<endl;
curCase
++;
}

return0;
}


回溯法:

#include<iostream>
#include
<cmath>
usingnamespacestd;

inta[20],curCase=0,n;

boolisNotIn(intnum,intend)
{//是否还未在环中出现过,num是待加入环尾的元素,end是当前环尾
inti;
for(i=1;i<=end-1;++i)
{
if(a[i]==num)returnfalse;
}

returntrue;
}


boolisPrime(intnum)
{//是否是素数
for(inti=2;i<=sqrt(static_cast<double>(num));++i)
{
if(num%i==0)
{
returnfalse;
}

}

returntrue;
}


boolisPrimeCircl(intnum,intend)
{//是否是素数环,num是待加入环尾的元素,end是当前环尾
if(end<n)
return(isPrime(num+a[end-1]));
else//此时要考虑头尾和是否是素数
return(isPrime(num+a[end-1])&&isPrime(num+a[1]));
}



voidoutput()
{
intk;
cout
<<a[1];
for(k=2;k<=n;k++)
cout
<<''<<a[k];
cout
<<endl;
}


voidback(inti)
{
intk;
for(k=1;k<=n;k++)
{
if(isNotIn(k,i)==true&&isPrimeCircl(k,i)==true)
{
a[i]
=k;
if(i==n)
output();
else
{
back(i
+1);
a[i]
=0;
}

}

}

}


intmain()
{
intk;
for(k=1;k<=20;k++)
{
a[k]
=0;
}

a[
1]=1;
while(cin>>n)
{
curCase
++;
cout
<<"Case"<<curCase<<':'<<endl;
back(
2);
cout
<<endl;
}

return0;
}




分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics