外贸手机网站模板,网站开发培训训,临安建设规划局网站,昆明汽车建站网站模板祝大家新年快乐#xff0c;今天给大家带来龙年第一道题
时间限制#xff1a;1秒 内存限制#xff1a;128M
题目描述
如图所示为一个由n个圆圈构成的圆环。将自然数1#xff0c;2#xff0c;...#xff0c;n放入圆圈内#xff0c;并且要求任意两个相邻的圆圈内…祝大家新年快乐今天给大家带来龙年第一道题
时间限制1秒 内存限制128M
题目描述
如图所示为一个由n个圆圈构成的圆环。将自然数12...n放入圆圈内并且要求任意两个相邻的圆圈内的数字之和为素数。请问给你圆圈数你能给出放置自然数的所有正确方案吗
注意圆圈中的数字一定是从1开始的并且连续不重复。 输入描述
输入包含多组测试数据。每组输入占一行为整数n0n20表示圆圈数。
输出描述
对于每组输入输出所有正确的方案按字典序从小到大排序。每组输出后输出一个空行。具体输出格式见输出样例。 注意只能按照顺时针方向放置数字。
样例
输入
6
8
输出
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
#includeiostream
#includealgorithm
#includecstring
#includestring
#includecstdio
using namespace std;
int n,m,cnt1,sx,sy;
const int N1e210;
int g[N];
int vis[N];
bool prime(int n ){for(int i2; i*in; i) {if(n%i0){return 0;}}return 1;
}
void print( ) {for(int i1; in; i) {printf(%d ,g[i]);}printf(\n);
}
void dfs(int pos ) {if(posn1) {if(prime(g[1]g[n])pos!2){print();return;}}for(int i2; in; i) {if(vis[i]0) {if(prime(ig[pos-1])){g[pos]i;vis[i]1;dfs(pos1);g[pos]0;vis[i]0;}}}
}
int main() {while(cinn) {g[1]1;printf(Case %d:\n,cnt);cnt;dfs(2);printf(\n);}return 0;
}
