素數環：
只能被1和自己整除的數，1不是素數，2是最小的素數
素數環是指將從1到n這n個整數圍成一個圓環，若其中任意2個相鄰的數字相加，結果均為素數，那么這個環就成為素數環（比如1 2 3 4，1 6 5 2 3 4）
要求：輸出所有素數環
提示：用到表和佇列,如果n為奇數，不構成素數環
樣列
Input
6
Output
1 4 3 2 5 6
4 3 2 5 6 1
3 2 5 6 1 4
2 5 6 1 4 3
5 6 1 4 3 2
6 1 4 3 2 5
1 6 5 2 3 4
6 5 2 3 4 1
5 2 3 4 1 6
2 3 4 1 6 5
3 4 1 6 5 2
4 1 6 5 2 3
Sample Input
4
Sample Output
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
1 4 3 2
4 3 2 1
3 2 1 4
2 1 4 3
詳情看代碼注釋
#include<bits/stdc++.h>
using namespace std;
int DE[100];//儲存資料
int SUM[100];//記錄是否訪問過
int n =1;
int Prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
queue<int> Q;
bool prime(int s)
{
int i;
for( i=0;i<25;i++)
if(Prime[i]==s)
return 1;
if(i==25)
return 0;
}
void clear()
{
while(!Q.empty())Q.pop(); //清空Q
Q.push(1);
}
void Display()
{
int temp=Q.back();
for(int j=0;j<n;j++) //回圈遍歷，列印佇列
{
for(int i=0;i<n;i++)
{ int TE=Q.front();
cout<<Q.front()<<" ";
Q.pop();
Q.push(TE);
}
cout<<endl;
int g=Q.front();
Q.pop();
Q.push(g);
//cout<<g<<endl;
}
clear();//將佇列清空，也可選擇存入堆疊
}
void DFS(int num)
{
for(int i=2;i<=n;i++)
if(num==n&&prime(DE[0]+DE[num-1]))//如果滿且佇列頭與佇列位之和為素數
{
for(int i=1;i<num;i++) //把陣列的值入堆疊
Q.push(DE[i]);
Display();
return;
}
else
{
if(prime(DE[num-1]+i)&&SUM[i]!=1) //當層未使用過且相鄰兩者相加為素數
{ //cout<<i<<" ";
SUM[i]=1;
DE[num++]=i;
DFS(num);
SUM[i]=0;//遍歷回來的時候將一切恢復至當層原樣
DE[num--]=0;
}
}
}
int main()
{
cin>>n;
SUM[1]=1;
Q.push(1);
DE[0]=1;
DFS(1);
}
有事請@王也枉不了
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/280293.html
標籤：其他
上一篇：指標的進階（后半）