旅游网站流程图,中国商业网,做网站推广好做么,好看网站【题目链接】
ybt 2110#xff1a;【例5.1】素数环
【题目考点】
1. 深搜回溯
2. 质数
【解题思路】
1~n的数字构成一个环#xff0c;要求相邻数字加和必须是质数。 该题最终输出的是一个序列#xff0c;只不过逻辑上序列最后一个数字的下一个数字就是序列的第一个数字…【题目链接】
ybt 2110【例5.1】素数环
【题目考点】
1. 深搜回溯
2. 质数
【解题思路】
1~n的数字构成一个环要求相邻数字加和必须是质数。 该题最终输出的是一个序列只不过逻辑上序列最后一个数字的下一个数字就是序列的第一个数字。数值1一定在这个序列中因此我们让序列第1个数字就是数值1。 而后使用深搜算法依次确定第2个数字第3个数字。。。 在确定第k个数字时首先该数字只能是1~n中的数字其次该数字必须没有使用过而且该数字和前一个数字第k-1个数字的加和必须是质数。将可能的满足以上条件的数字作为序列的第k个数字。 当k为n1也就是满足kn时已经确定了序列中的n个数字此时如果第1个数字和第n个数字的加和也是质数那么就确定了一个满足条件的质数环将序列中的数字输出。 可以使用标志位isOver记录是否已经找到解。如果已经找到解那么递归调用可以直接返回不用继续进行搜索。
【题解代码】
解法1深搜回溯
#include bits/stdc.h
using namespace std;
#define N 35
int n, a[N];
bool vis[N], isOver;
bool isPrime(int x)//判断x是否是质数
{if(x 2)return false;for(int i 2; i*i x; i) if(x%i 0)return false;return true;
}
void dfs(int k)
{if(isOver)return;if(k n){if(isPrime(a[n]a[1])){isOver true;for(int i 1; i n; i)cout a[i] ;cout endl;}return;}for(int i 1; i n; i) if(!vis[i] isPrime(a[k-1]i)){vis[i] true;a[k] i;//选择数值i作为第k个数字dfs(k1);vis[i] false;}
}
int main()
{cin n;a[1] 1;vis[1] true;dfs(2);return 0;
}
