1到n素数环
由于此题以前代码丢失。。补写一下
给出一个N(0<N<20)，在1~N的所有排列中，满足相邻两个数之和是素数（头尾相邻）的排列输出
比如当N = 4时，满足条件的素数环有如下几种
1 2 3 4
1 4 3 2
2 1 4 3
2 3 4 1
3 2 1 4
3 4 1 2
4 1 2 3
4 3 2 1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include<iostream> #include<cstdio> using namespace std; int n,ans[21]; bool used[21]; void print() { for(int i=1;i<=n;i++) printf("%d ",ans[i]); printf("\n"); } bool is_prime(int x) { if(x==2||x==3||x==5||x==7||x==11||x==13||x==17||x==19||x==23||x==29||x==31||x==37||x==41)return 1; return 0; } void search(int k) { if(k==n+1&&is_prime(ans[1]+ans[k-1])){print();return;} for(int i=1;i<=n;i++) { if(used[i])continue; if(k==1||is_prime(i+ans[k-1])) { ans[k]=i;used[i]=1; search(k+1); used[i]=0; } } } int main() { scanf("%d",&n); search(1); return 0; } |
Subscribe
计数器 9787809
OI 课件=>
OI 课件=>