seo外链网站源码,做贷款网站犯法吗,梁山网站建设价格,小程序商城功能题目
输入正整数#xff0c;把整数1#xff0c;2#xff0c;3#xff0c;#xff0c;n组成一个环#xff0c;使得相邻两个整数之和均为素数。输出时从整数1开始逆时针排列。同一个环应恰好输出一次。n16 样例输入 6 样例输出 1 4 3 2 5 6 1 6 5 2 3 4
分析与解…题目
输入正整数把整数123···n组成一个环使得相邻两个整数之和均为素数。输出时从整数1开始逆时针排列。同一个环应恰好输出一次。n16 样例输入 6 样例输出 1 4 3 2 5 6 1 6 5 2 3 4
分析与解答
用一个数组a存答案由于是从1开始a[0]1,
void DFS ( Vertex V )
{visited[ V ] true;if(…) return;for ( V 的每个邻接点 W )if ( !visited[ W ] )DFS( W );
}在这个题中深搜需要的终止条件lnisp[A[0]A[n-1]]l是位置如果已确定了n个位置说明此时终止并且如果第一个a[0]等于a[n-1]说明此时终止终止的话从0到n-1输出即可 如果不满足终止条件我们就找新的数填到位置l然后递归找下一个位置需要填的数如何知道该位置填什么数我们知道第一个数是1那这个位置的数我们假设是2到n中任一个循环如果满足这个数不曾出现而且和上一个位置的数之和为素数那我们就把这个位置填上这个数把标记数组标记用来表明这个数已经被用过并且递归调用找下个位置我们递归完了还要清除标记数组的标记就像是找到了一个可能情况就不断地回溯一样这样的话最终会找出所有情况
#includeiostream
#includecstdio
#includecstring
#includealgorithm
using namespace std;int is_prime(int x) {for(int i 2; i*i x; i)if(x % i 0) return 0;return 1;
}int n, A[50], isp[50], vis[50];void dfs(int l){if(lnisp[A[0]A[n-1]]){for(int i0;in;i)if(i0) printf(%d,A[i]);else printf( %d,A[i]);printf(\n);}else{for(int i2;in;i)if(!vis[i]isp[iA[l-1]]){A[l]i;vis[i]1;dfs(l1);vis[i]0;}}
}
int main() {int kase 0;for(int i 2; i 20*2; i) isp[i] is_prime(i);while(scanf(%d, n) 1 n 0) {printf(Case %d:\n, kase);memset(vis, 0, sizeof(vis));A[0] 1;dfs(1);printf(\n);}return 0;
}
