这个搜索............搜的我头都大了.......不过还是 懂了那么一点点...哈哈
从3/7晚上 做到3/8晚上------从女生到妇女 我都用来做着一道题了.........
所谓的 深度优先搜索 还是 递归调用自身 关键思想是
在上面写出 满足 条件的 情况 例如 if 然后怎么怎么 然后 不满足的话 继续 调整 一点一点继续 调用尝试 如果发现 不合适的话 在调用的 后面 重新 将数据还原成 没有 尝试 时 的 样子 ,,,,,,just so so
明天据需努力 先开始 N 皇后问题 听说 和这一道题 挺像的 .
奇数的话除了 1 其余的都是无解
#include<stdio.h> #include<string.h> #include<math.h> #include<iostream> #include<algorithm> #include<queue> #include<vector> #include<set> #include<stack> #include<string> #include<sstream> #include<map> #include<cctype> using namespace std; bool isPrime(int num) { if (num == 2 || num == 3) { return true; } if (num % 6 != 1 && num % 6 != 5) { return false; } for (int i = 5; i*i <= num; i += 6) { if (num % i == 0 || num % (i+2) == 0) { return false; } } return true; } int n,a[25],mark=0,visited[25]; void DFS(int m) { if(m==n+1&&isPrime(a[m-1]+1)) //戒指 填充完毕 , 比且最后一个数字和第一个数字之和 也是素数 { for(int i=1;i<n;i++) printf("%d ",a[i]); printf("%d ",a[n]); mark=1; } for(int i=2;i<=n;i++) { if(visited[i]==0) // 这个数字 没有用过 { if(isPrime(a[m-1]+i)) // 如果上一个和这一个 之和是素数的话 { a[m]=i; visited[i]=1; DFS(m+1); visited[i]=0; } } } } int main() { int count1=0; while(scanf("%d",&n),n) { printf("Case %d: ",++count1); if(n%2==1&&n!=1) { printf("No Answer "); continue; } mark=0; a[1]=1; //第一个位置上 一定 是 1 memset(visited,0,sizeof(visited)); visited[1]=1; DFS(2); // 直接 开始填第二个坑 . if(mark==0) printf("No Answer "); } return 0; }