广东省网站设计师,茶叶包装设计,长沙网站设计拓谋网络,网站建设记什么科目信息学奥赛一本通#xff08;C版#xff09;在线评测系统
【题目描述】 输入正整数nn#xff0c;把整数11,22,…,nn 组成一个环#xff0c;使得相邻两个整数之和均为素数。 【输入】 输入正整数nn。 【输出】 输出任意一个满足条件的环。 【输入样例】
6
【输出样例】
…信息学奥赛一本通C版在线评测系统
【题目描述】 输入正整数nn把整数11,22,…,nn 组成一个环使得相邻两个整数之和均为素数。 【输入】 输入正整数nn。 【输出】 输出任意一个满足条件的环。 【输入样例】
6
【输出样例】
4 3 2 5 6 1
【提示】 数据满足 4≤n≤30 #includeiostream
#includecmath
using namespace std;int n;
bool vis[110];
int cnt[110];
bool flag false;//先假装搜不到bool isPrime(int x) {if (x 2) return false;for (int i 2; i sqrt(x); i) {if (x % i 0) return false;} return true;
}void dfs(int depth) {//7.终止条件if (depth n) {//前n层已经搜完了if (!isPrime(cnt[depth - 1] cnt[1])) return;for (int i 1; i depth; i) {cout cnt[i] ;}cout endl;flag true;return;}//1.枚举方案for (int i 1; i n; i) {// 2.判断标记if ((depth 1 !vis[i]) || (depth 1 !vis[i] isPrime(i cnt[depth - 1]))) {// 3.搜索cnt[depth] i;// 4.标记 - 防止重复搜索vis[i] 1;// 5.进入下一层搜索dfs(depth 1);// 6.回溯vis[i] 0;if (flag true) return;}}
}int main() {cin n;dfs(1);return 0;
}
优化
#includeiostream
#includecmath
using namespace std;int n;
bool vis[110];
int cnt[110];
bool flag false;//先假装搜不到//bool isPrime(int x) {
// if (x 2) return false;
// for (int i 2; i sqrt(x); i) {
// if (x % i 0) return false;
// } return true;
//}bool isPrime[110];//标记素数 isPrime[x]0/1 0-x是素数 1-x不是素数
//埃氏筛原理将素数的倍数全部筛掉留下的就是素数
void E_sieve(int n) {isPrime[0] isPrime[1] 1;//0和1不是素数for (int i 2; i * i n; i) {if (isPrime[i] 0) {//代表i是素数for (int j i * i; j n; j i) {//j代表i的所有倍数n以内isPrime[j] 1;//j一定不是素数}}}
}void dfs(int depth) {//7.终止条件if (depth n) {//前n层已经搜完了if (isPrime[cnt[depth - 1] cnt[1]]) return;for (int i 1; i depth; i) {printf(%d , cnt[i]);}cout endl;flag true;return;}//1.枚举方案for (int i 1; i n; i) {// 2.判断标记if ((depth 1 !vis[i]) || (depth 1 !vis[i] !isPrime[i cnt[depth - 1]])) {// 3.搜索cnt[depth] i;// 4.标记 - 防止重复搜索vis[i] 1;// 5.进入下一层搜索dfs(depth 1);// 6.回溯vis[i] 0;if (flag true) return;}}
}int main() {cin n;E_sieve(2*n);//最大要筛nn-1,dfs(1);return 0;
}
