首页 > 代码库 > hdu1016【dfs】
hdu1016【dfs】
题目很简单,给出n(1<n<20),将1-n这n个数字排成一个环,使得这个环所有相邻的数字之和都是素数,打印出所有可能。
直接深搜,逐个递归时判断素数剪枝即可~
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 bool prime[40]; 5 bool hash[40]; 6 int ans[40]; 7 int n; 8 int cas = 1; 9 10 void getprime() {11 memset(prime, 0, sizeof(prime));12 int a[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};13 for(int i = 0; i < 12; i++)14 prime[a[i]] = true;15 return;16 }17 18 void dfs(int id, int fro) {19 if (id == n) {20 if (!prime[ans[n - 1] + 1])21 return;22 23 for(int i = 0; i < n - 1; i++)24 cout << ans[i] << " ";25 cout << ans[n - 1] << endl;26 }27 28 for(int i = 2; i <= n; i++) {29 if (hash[i]) continue;30 if (!prime[fro + i]) continue;31 hash[i] = true;32 ans[id] = i;33 dfs(id + 1, i);34 hash[i] = false;35 }36 }37 38 int main() {39 getprime();40 ans[0] = 1;41 while(cin >> n) {42 printf("Case %d:\n", cas++);43 memset(hash, 0, sizeof(hash));44 dfs(1, 1);45 cout << endl;46 }47 return 0;48 } 49 50 /*51 6 52 853 Case 1:54 1 4 3 2 5 655 1 6 5 2 3 456 57 Case 2:58 1 2 3 8 5 6 7 459 1 2 5 8 3 4 7 660 1 4 7 6 5 8 3 261 1 6 7 4 3 8 5 262 */
hdu1016【dfs】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。