DFS,好像主要是对dfs的递归调用吧,自己也不太懂,
总之,它很神奇,多看看代码吧
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int n;
int isp[100];
int vis[100];
int A[100];
int is_prime(int x) //判断一个数是否为素数(该数比较小,不会引起超时)
{
int i=1,k;
for(i=2;i<=(k=(int)sqrt(x));i++)
if(x % i == 0)break;
if(i<=k)return 0;
else return 1;
return x;
}
void dfs(int cur) //深搜寻路
{
if(cur == n && isp[A[0] + A[n-1]]) //递归边界,别忘了保证第一个和最后一个数,环结构
{
int i;
printf("1");
for(i=1;i<n;i++)
printf(" %d",A[i]); //打印方案
printf("\n");
}
else
{
int i;
for(i=2;i<=n;i++) //尝试放置每个数 i
if(!vis[i] && isp[i + A[cur-1]]) //如果 i 没有用过,且与前一个数之和为素数
{
A[cur] = i;
vis[i] = 1; //设置使用标志,表明用过
dfs(cur + 1);
vis[i] = 0; //清除标记
}
}
}
int main()
{
int N,i;
for(i=2;i<=200;i++)
isp[i] = is_prime(i); //生成素数表(较小范围的素数表,大范围的用素数筛法)
while(scanf("%d",&N) == 1,N)
{
n = N;
A[0] = 1;
dfs(1);
}
return 0;
}
分享到:
相关推荐
c/c++解决素数环问题,深度优先搜索算法,算法设计与分析
求解素数环问题 数据结构代码,初级学习人员使用
java求解素数环经典问题,很好的算法设计,看看就知道了
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
acm上的一个关于素数环的实现代码。感觉有意义的代码一定要分享。
素数环问题 把从1到20这20个数摆成一个环,要求相邻的两个数的和是一个素数。 分析:用回溯算法,考察所有可能的排列。
素数环问题 把从1到20这20个数摆成一个环 分析:用回溯算法,考察所有可能的排列。
C语言是一门通用计算机编程语言,广泛应用于底层开发。C语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码
用回溯法解决问题,给出了素数环和最小重量机器人的解答,帮助大家掌握回溯法
欧几里得、批处理作业、素数环、天平问题、图着色、折半查找、最大字段和、最长递增子序列
12. 素数环问题 21 13. 迷宫问题 23 14. 踩气球 27 15. 字母转换 29 16. 农场灌溉问题 32 17. 求图像的周长 36 18. 电子老鼠闯迷宫 41 19. 跳马 45 20. 独轮车 50 21. 六数码问题 56 22. 找倍数 61 23. 木乃伊迷宫 ...
6. 素数环问题 7. 迷宫问题 8. *农场灌溉问题(ZOJ2412) 9. *求图像的周长(ZOJ1047) 10. *骨牌矩阵 11. *字母转换(ZOJ1003) 12. *踩气球(ZOJ1004) 实验三:搜索 1. Floodfill 2. 电子老鼠闯迷宫 3. 跳马 4. ...
利用回溯法求解素数环问题,由于素数环问题结果的多样性,因此可能会有较长的运行时间
把所有数据围成一圈,使得任意相邻的两个数都为素数
01背包问题 8皇后问题 堡垒问题 踩气球 迷宫问题 农场灌溉问题 求图像的周长 素数环问题 装载问题 字母转换
通过学习轻松掌握算法求八皇后、N皇后、素数环等问题,掌握搜索算法
算法题中约瑟夫环函数的一个例题,大家可以看看
首先,介绍了素数研究的初等数论和代数学基础,重点讲解了素数的基本理论和群环域格等理论;然后,对素数的分布规律,从薛式筛法中提出数数论理论,对素数在6n+1和6n-1两列分布形式中的因子分布规律进行讨论; ,从...