题目描述题目要求将111到nnn的整数nnn为偶数排成一个环使得相邻两个数的和均为素数。环的第一个数固定为111。输出所有满足条件的环按字典序。输入格式输入包含多个nnn值每行一个0n≤160 n \le 160n≤16。输入以文件结束符EOF\texttt{EOF}EOF终止。输出格式对于每个nnn输出Case X:然后每行一个环数字之间用空格分隔。不同测试用例的输出之间由一个空行分隔。样例输入6 8输出Case 1: 1 4 3 2 5 6 1 6 5 2 3 4 Case 2: 1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2题目分析本题的核心是回溯搜索所有可能的素数环。素数预处理由于n≤16n \le 16n≤16相邻两数和最大为313131可以预先生成222到313131的素数表。回溯算法从位置000值为111开始依次确定下一个位置的数字。每个数字只能使用一次。当前数字与上一个数字的和必须为素数。当填满n−1n-1n−1个位置后还需检查最后一个数与第一个数111的和是否为素数。按递增顺序尝试数字保证输出字典序。复杂度分析n≤16n \le 16n≤16最坏情况为15!15!15!但剪枝素数约束大幅减少搜索空间。代码实现// Prime Ring Problem// UVa ID: 524// Verdict: Accepted// Submission Date: 2016-08-07// UVa Run Time: 0.110s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intring[20],visited[20],n;intprimes[32]{0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1};voidbacktrack(intdepth){if(depthn-1){if(primes[ring[depth]1]){for(inti0;in;i)cout(i0? :)ring[i];cout\n;}}else{for(inti2;in;i)if(!visited[i]primes[ring[depth]i]){visited[i]true;ring[depth1]i;backtrack(depth1);visited[i]false;}}}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases0;while(cinn){if(cases)cout\n;coutCase cases:\n;ring[0]1;backtrack(0);}return0;}