素數環
時間限制(普通/Java) : 1000 MS/ 3000 MS 運作記憶體限制 : 65536 KByte
總送出 : 1018 測試通過 : 154
題目描述
輸入正整數n,把整數1,2,3,…,n組成一個環,使得相鄰兩個整數之和為素數。輸出時從整數1開始逆時針排列。同一個環應恰好輸出一次。1<n≤16。
輸入
輸入正整數n,1<n≤16。
輸出
輸出素數環序列,從整數1開始逆時針排列。
樣例輸入
6
樣例輸出
1 4 3 2 5 6
1 6 5 2 3 4
分析:回溯法比枚舉排列法快了很多很多,即使n=16速度也不錯。該函數取名為dfs并非巧合,從解答樹的角度講,回溯法正是按照深度優先的順序在周遊解答數。
實作代碼:
#include<cstdio>
#include<cstdlib>
#include<string.h>
int n;
int *A=new int[16];
int *vis=new int[17];
int *isp=new int[34];
void dfs(int cur)
{
if(cur==n&&isp[A[0]+A[n-1]])
{
for(int i=0;i<n;i++) if(i==0) printf("%d",A[i]); else printf(" %d",A[i]);
printf("\n");
}
else for(int i=2;i<=n;i++)
{
if(!vis[i]&&isp[i+A[cur-1]])
{
A[cur]=i;
vis[i]=1;
dfs(cur+1);
vis[i]=0;
}
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) A[i]=i+1;
memset(vis,0,sizeof(vis));
memset(isp,0,sizeof(isp));
isp[2]=1,isp[3]=1,isp[5]=1,isp[7]=1,isp[11]=1,isp[13]=1,isp[17]=1,isp[19]=1;isp[23]=1,isp[29]=1,isp[31]=1;
dfs(1);
}