首页 > 代码库 > 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】