本BLOG簡介（內有一道UVa524素數環進階版），uva524素數

本BLOG簡介（內有一道UVa524素數環進階版），uva524素數

【B001】Hi，大家好，今天我的博客第一天開通，今天奉上開博題，出自首都師師范大學附屬中學OJ（題號未知在練習場中）原題為UVa524，題目要求如下：

【難度B】————————————————————————————————————————————————————————————————————————————————————————————

【題目要求】輸入正整數n，用整數1，2，3，……，n 的某種排列組成一個環，使任意相鄰的兩數和均為素數。輸出時從整數1開始逆時針排列，同一個環恰好輸出一次。 有多種可能的排列，輸出時按照字典序小的排列先輸出的原則。

【輸入要求】一個正整數n

【輸入示例】

6

【輸出實例】

2
1 4 3 2 5 6
1 6 5 2 3 4

【其他要求】數據范圍：n〈=16

【試題分析】各位讀者首先想到的是暴搜但當n為12時就已經慢得要命，此題必用回溯法（有點像dfs深搜）。

【代碼】

#include <cstdio>
#include <cstring>

int A[20], vis[20];
int n;
int t=0;

int is_prime(int n)//判斷質數 
{
    for(int i = 2; i*i <= n; i++)
        if(n % i == 0)   return 0;
    return 1;
}

void js(int xx)
{
    
    if(xx == n && is_prime(A[0]+A[n-1]))
    {
        t++;
		
    }
    
	
	for(int i = 2; i <= n; i++)//嘗試每一個數 
        if(vis[i] == 0 && is_prime(i+A[xx-1]))//判斷是否和為質數 
        {
            A[xx] = i;
            vis[i] = 1;
            js(xx+1);
            vis[i] = 0;//清除標記 
        }

}
void dfs(int cur)
{
    
    if(cur == n && is_prime(A[0]+A[n-1]))
    {
        t++;
		
    }
    
	if(cur == n && is_prime(A[0]+A[n-1]))
    {
		
		for(int i = 0; i < n; i++)
        {
			printf("%d", A[i]);//打印方案 
            printf("%s", i == n-1 ? "\n" : " ");
        }
		return;
    }
	for(int i = 2; i <= n; i++)//嘗試每一個數 
        if(vis[i] == 0 && is_prime(i+A[cur-1]))//判斷是否和為質數 
        {
            A[cur] = i;
            vis[i] = 1;
            dfs(cur+1);
            vis[i] = 0;//清除標記 
        }

}
    
int main()//調用 
{
#ifdef LOCAL
    
#endif
	int kase = 0;
    while(scanf("%d", &n) != EOF)
    {
        memset(vis, 0, sizeof(vis));
        A[0] = 1;
        vis[1] = 1;
        js(1);
		printf("%d\n", t);
		dfs(1); 
    }
	return 0;
}

 【注】此代碼以AC稍有累贅，請各位讀者多多指教（話說我一直粗心沒看見示例中的2結果WA了4次）