HDU 1016 Prime Ring Problem：回溯法構造質數環

問題描述

1..n (n≤16, 偶數) 排成環，相鄰兩數之和為質數，且首尾相鄰。按字典序輸出所有方案，1 固定在首位。

回溯框架

• 狀態：當前環 `ring[0..pos-1]`，`used[1..n]` 標記
• 遞歸：`pos` 位置嘗試 2..n 未用數字
• 剪枝：`ring[pos-1] + candidate` 必須為質數
• 終止：`pos==n` 且 `ring[n-1]+ring[0]` 為質數 → 輸出

質數預處理

最大和 16+15=31，預計算 `isPrime[32]`。

完整代碼

#include 
using namespace std;
bool isPrime[32];
int n, ring[17];
bool used[17];

void initPrime() {
    fill(isPrime, isPrime+32, true);
    isPrime[0]=isPrime[1]=false;
    for (int i=2; i*i<32; ++i)
        if (isPrime[i])
            for (int j=i*i; j<32; j+=i) isPrime[j]=false;
}

void dfs(int pos) {
    if (pos == n) {
        if (isPrime[ring[n-1] + ring[0]]) {
            for (int i=0; i> n) {
        cout << "Case " << cas++ << ":\n";
        fill(used, used+17, false);
        ring[0] = 1; used[1] = true;
        dfs(1);
        cout << "\n";
    }
    return 0;
}

優化技巧

1. 預計算質數表，O(1) 判斷
2. 按遞增順序嘗試候選數，天然滿足字典序輸出要求
3. `used` 數組而非 `set`，O(1) 標記/檢查
4. n≤16，狀態空間極小，無需複雜優化

複雜度

最壞 O(n!)，但質數約束極強，實際搜索節點極少，瞬間通過。

此題是回溯法入門經典，「質數環」約束使搜索樹極度稀疏，適合練習回溯框架與剪枝思維。