nyoj 488 素数环（深搜）

素数环

描述

有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。

为了简便起见，我们规定每个素数环都从1开始。例如，下图就是6的一个素数环。

输入

有多组测试数据，每组输入一个n(0 输出

每组第一行输出对应的Case序号，从1开始。
如果存在满足题意叙述的素数环，从小到大输出。
否则输出No Answer。

样例输入

6
8
3
0

样例输出

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4
Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
Case 3:
No Answer

来源

hdu改编

上传者

ACM_丁国强

考察的是深搜；

深搜模板：

//深搜模板：（自己总结的，有不对的地方，还请各位路过的大牛，不吝指教！） 
int n;//首先申请一个全局变量 
int visit[10010];//标记 元素 
int a[10010];//存放元素 
void dfs(int cur)
{
	//此处是递归跳出条件 
	if(cur==n)//此处的判断条件看数组下标是否 是从1 开始的
	{
		if(   )//题目中限定的一定条件。
		{
			printf("  ");//输出相应的要求解的值 
		}
	}
	for(i=2;i<=n;++i)
	{
		if(  )//又是与题中的限定条件有关，到那时多了一个判断是否已经标记过
		{
			visit[i]=1;
			a[k]=i;//将此时境况下满足条件的数据存入数组 
			dfs(k+1); //对后面的元素进行递归 
			visit[i]=0;//这两步与输出多组数据有关，递归跳出的时候，在多组跳出的时候
			           //为了后续满足题意的数据的输出，需要返回出师状态 
		} 
	} 
} 

代码如下：

#include
      
       
#include
       
         int n; int visit[110]; int ring[110]={1}; int prime(int x)//判断是否是素数 { for(int i=2;i*i<=x;++i) { if(x%i==0) return 0; } return 1; } void dfs(int k)//深搜 { int i; if(k==n-1)//循环跳出的条件 { if(prime(1+ring[k]))//满足和为素数 { printf("1"); for(i=1;i
        
         
 
         
 
         
 
        
       
      

<script type="text/java script">BAIDU_CLB_fillSlot("771048");

点击复制链接 与好友分享! 回本站首页

<script> function copyToClipBoard(){ var clipBoardContent=document.title + '\r\n' + document.location; clipBoardContent+='\r\n'; window.clipboardData.setData("Text",clipBoardContent); alert("恭喜您！复制成功"); }

<script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];