Uva 524 回溯大法好

一、题意

每组数据给一个n。
要求你输出所有1...n的从1开始的排列，每个排列满足相邻两个（包括首尾两个）之和为素数。
输出顺序按字典序。

二、解析

看到这题第一反应是枚举全排列，事实证明那样会超时。
紫薯告诉我们，回溯法总是比生成-测试法快得多。因此我们考虑用回溯的思想。
需要一个递归深度值idx表示当前递归到第几个数，然后还有一个值cur表示当前选择的值。
需要一个判断素数得函数。

三、代码

#include <iostream>
using namespace std;
const int maxn = 16 + 5;
int n, kase = 0, vis[maxn], ans[maxn];

bool isPrime(int x) {
    for(int i = 2; i * i <= x; i ++) if(x % i == 0) return 0;
    return 1;
}

void solve(int idx, int cur) {
    ans[idx] = cur;
    if(idx == n - 1) {
        if(isPrime(cur + 1)){
            for(int i = 0; i < n; i ++) cout << (i ? " " :"") << ans[i];
            cout << endl;
        }
        return;
    }
    for(int i = 1; i <= n; i ++) if(!vis[i] && isPrime(cur + i)) {
        vis[i] = 1;
        solve(idx + 1, i);
        vis[i] = 0;
    }
}

int main() {
    while(cin >> n) {
        fill(vis, vis + n + 1, 0);
        if(kase) cout << "\n";
        cout << "Case " << ++ kase << ":\n";
        vis[1] = 1;
        solve(0, 1);
    }
}

四、归纳

• 注意判断素数是i得遍历范围是[2, i * i]得闭区间，如果忘了i * i的话9就会变成素数了hhhh
• 吐槽一句：Uva的输出格式是真的严格，比如这题，每组末尾不能有空格，最后一组数据最后不能有空行...