本文主要是介绍九度OJ-1459：Prime ring problem，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本题从理论上可以转化为对状态的搜索，用枚举法暴力求解。但是其状态参量有Ｎ个，若转化为状态搜索则其判断状态检索过与否的mark数组将有N维，从实际上来说难以实现，故应另辟蹊径。
这是一道典型的深度优先搜索（遍历解答树）！！
Debug记录：
①第一次遇到真的因为cout而TLE的情况。由于此题当n=16时会出现爆炸性的输出，故cout比printf多出来的时间消耗已经不容忽视。将cout改为printf后AC。
②OJ上不知道是哪个版本的编译器，总之<iostream>不带有c的scanf、printf等诸多基础输入输出函数，需要#include <cstdio>
③以后使用递归函数时候记得尽量统一出口，这样显得逻辑清晰。例如写此题时，先前没有统一DFS的返回出口，导致只在 “if (d.size()==n){ ”处（即满队情况的分支处）写了出口，而没在非满队的分支处写出口。本来非满队的分支处是不需要写出口的，但是由于我把退栈操作（退回上层前的回溯）统一写在了本层return之前，导致当此次DFS在非满队分支执行并且执行完毕返回上层时，没有了退栈回溯操作，导致出错。
收获如下：
①掌握了双端队列#include <deque>的用法（写法基本与<vector>一致），具体见STL容器专题。
②掌握了此类题目的做法：转化为对解答树的先序遍历（深度优先搜索），而非使用循环。因为若使用循环共需嵌套N层，从实际上来说实在难以实现。
③掌握了回溯法。回溯法（结束此层DFS时退栈）在此类对解空间的先序遍历（深度优先搜索）中经常使用，更是用来求解树的路径序列问题的必要方法。这个回溯操作放在统一 返回出口处写（自己的写法）是逻辑清晰的，不要像《指南》里头那样写，东一个西一个很不清晰很容易出bug。
- 题目描述：
-
A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.
Note: the number of first circle should always be 1.
- 输入：
-
n (1 < n < 17).
- 输出：
-
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.
You are to write a program that completes above process.
Print a blank line after each case.
- 样例输入：
-
6 8
- 样例输出：
-
Case 1: 1 4 3 2 5 6 1 6 5 2 3 4Case 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
- 提示：
-
用printf打印输出。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <deque>//由于回溯操作要用到删除队尾元素，故使用双端队列
#define MAXSIZE 17
using namespace std;
deque<int> d;
bool prime[MAXSIZE*2+1];
bool mark[MAXSIZE+1];
int n;
void DFS(){if (d.size()==n){//当凑齐prime ring时 if (prime[d.back()+d.front()]==true){//若首尾满足条件,即已完成一个prime ring =>print deque<int> e=d;//声明临时队列e bool firstCase=true;while (!e.empty()){if (firstCase==true)firstCase=false;elseprintf(" ");printf("%d",e.front());e.pop_front();}printf("\n");}else{//不做任何事 }}else{for (int i=2;i<=n;i++){//add a number if (mark[i]==false&&prime[i+d.back()]==true){//若i还未放入q且满足i与前项和为素数 d.push_back(i);mark[i]=true;DFS();//继续添加 //下层已自动回溯 }}}//统一出口： //无论成功或者失败，都在此返回上层，并且返回前都要回溯 mark[d.back()]=false;d.pop_back();return;
}
int main(){//initiateint primeBound=2;prime[0]=prime[1]=false;prime[2]=true;bool isPrime=true;int time=1;//preprocessfor (int i=3;i<MAXSIZE*2+1;i++){//判断i是否为素数 isPrime=true;//initiate isPrimefor (int j=2;j<=primeBound&&j<sqrt(i)+1;j++){//遍历素数组来尝试整除 if (prime[j]==true){if (i%j==0){//能整除isPrime=false;break;} }}prime[i]=isPrime;if (isPrime){primeBound=i;}}//bodywhile (cin>>n){//initiate while (!d.empty())d.pop_front();for (int i=0;i<=n;i++){mark[i]=false;}d.push_back(1);mark[1]=true;//searchcout<<"Case "<<time<<":"<<endl;DFS();printf("\n");time++; }return true;
}
这篇关于九度OJ-1459：Prime ring problem的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
