这个搜索............搜的我头都大了.......不过还是 懂了那么一点点...哈哈
从3/7晚上 做到3/8晚上------从女生到妇女 我都用来做着一道题了.........
所谓的 深度优先搜索 还是 递归调用自身 关键思想是
在上面写出 满足 条件的 情况 例如 if 然后怎么怎么 然后 不满足的话 继续 调整 一点一点继续 调用尝试 如果发现 不合适的话 在调用的 后面 重新 将数据还原成 没有 尝试 时 的 样子 ,,,,,,just so so
明天据需努力 先开始 N 皇后问题 听说 和这一道题 挺像的 .
#include<stdio.h> #include<string.h> int n,a[21]; // 用于储存 戒指 上 数字的 顺序 int prime_num[12] = {2,3,5,7,11,13,17,19,23,29,31,37},visited[21]; bool is_prime(int num) // 判断 是不是 素数 { for(int i=0;i<12;i++) if(num==prime_num[i]) return true; return false; } void DFS(int num) { int i; if(n==num-1&&is_prime(a[n]+1)) // 最后 一个数字 + 1 也是 素数的话 // 如果 符合要求的话 就开始 输出 { for(i=1;i<n;i++) printf("%d ",a[i]); printf("%d\n",a[i]); } else { for(i=2;i<=n;i++) { if(visited[i]==0&&is_prime(i+a[num-1]))// 没有被访问 并且 这个 数字 + 上一个 戒指上的 数字 之和为 素数的话 . { visited[i]=1; a[num++]=i; // 戒指上的 下一个 空位 可以补齐 并且 将 和上一个数字 合拍的数字填进去 DFS(num); // 传输 下一个 空位 /*出现 上一个栈帧 跳出的情况*/ visited[i]=0; // 这样的话 就表明 呢个数字并不合适 所以 重新 定义为 未访问 num--; } } } } int main() { int num=0; while(scanf("%d",&n)!=EOF) { num++; memset(visited,0,sizeof(visited)); // 用于 访问 标记 printf("Case %d:\n",num); a[1]=1; visited[1]=1; DFS(2); // 戒指的 第二个 位置为空 printf("\n"); } return 0; }
Prime Ring Problem -- 第一个真正意义上的 搜索
原文:http://www.cnblogs.com/A-FM/p/5255623.html