Prime Ring Problem HDU - 1016
程序员文章站
2022-05-21 08:44:42
...
经典回溯法。。。
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
int a[25];
bool vis[25];
bool check(int a){
int k=2;
if(a==1||a==2) return 1;
while(k<a){
if(a%k==0){
return 0;
}
k++;
}
return 1;
}
void dfs(int cur){
if(cur==n&&check(a[0]+a[n-1])){
for(int i=0;i<n-1;i++){
cout<<a[i]<<" ";
}
cout<<a[n-1]<<endl;
}
else for(int i=2;i<=n;i++){
if(!vis[i]&&check(a[cur-1]+i)){
vis[i]=1;
a[cur]=i;
dfs(cur+1);
vis[i]=0;
}
}
}
int main(){
int k=0;
while(cin>>n){
k++;
cout<<"Case "<<k<<":"<<endl;
memset(a,0,sizeof(a));
memset(vis,0,sizeof(vis));
a[0]=1;
dfs(1);
cout<<endl;
}
return 0;
}
上一篇: 李太后得知张居正是被冤枉的 李太后为什么不说出实情
下一篇: python发腾讯微博代码分享