Hdu，1016，Prime，Ring，Problem，(素数环经典dfs)

Hdu 1016 Prime Ring Problem是一道经典的dfs问题，要求在一个1~n的数字环中，将每个数字使用一次，使得环上所有相邻两个数字的和都是质数。这道题的难度在于对素数的判断和对数字环的遍历。

一、求解素数

由于本题要求判断数字的质数性质，因此需要自己写一个判断素数的函数。在此给出两种常用的方法：

1.试除法：即将x分别除以2到sqrt(x)，如果都不能整除，则x为素数。时间复杂度O(sqrt(n))。

代码实现如下：

bool isPrime(int n){

if(n<2) return false;

for(int i=2; i*i<=n; i++){

if(n%i==0) return false;

}

return true;

}

2.埃氏筛法：将2~n的数放入一个容器中，从2开始枚举，将2的倍数、3的倍数……依次标记为非素数，直到枚举到n/2.时间复杂度近似为O(nloglogn)。

代码实现如下：

void primeSieve(int n, vector& primes){

vector isPrime(n+1, true);

isPrime[0] = isPrime[1] = false;

for(int i=2; i<=n; i++){

if(isPrime[i]){

primes.push_back(i);

for(int j=2*i; j<=n; j+=i){

isPrime[j] = false;

}

}

}

}

二、遍历数字环

对于数字环的遍历，可以使用dfs递归实现。假设当前已经确定了前i位数字，还需要确定第i+1位数字。每次从未使用的数字中选出一个，并判断与前一个数字的和是否为质数，如果是，则递归地寻找下一位数字；如果不是，则回溯到上一位数字重新选择下一个数字。

代码实现如下：

void dfs(int n, vector& res, vector& path, vector& used){

if(path.size()==n){

if(isPrime(path.back()+1)){

res.push_back(path);

}

return;

}

for(int i=2; i<=n; i++){

if(!used[i] && isPrime(path.back()+i)){

used[i] = true;

path.push_back(i);

dfs(n, res, path, used);

path.pop_back();

used[i] = false;

}

}

}

三、完整代码

综上所述，完整代码如下： 如果你喜欢我们三七知识分享网站的文章， 欢迎您分享或收藏知识分享网站文章 欢迎您到我们的网站逛逛喔！https://www.37seo.cn/