HDU-1016 Prime Ring Problem (DFS)

客官°小女子只卖身不卖艺 2022-05-19 00:26 162阅读 0赞

# **                                     Prime Ring Problem** #

### **Problem Description** ###

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.  
  
Note: the number of first circle should always be 1.  
  
![1016-1.gif][]

### **Input** ###

n (0 < n < 20).

### **Output** ###

The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.  
  
You are to write a program that completes above process.  
  
Print a blank line after each case.

### **Sample Input** ###

### **Sample Output** ###

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

**题意描述：**

输出1到n的自然数可以组成一个以1开头，顺时针或逆时针相邻两个和都为素数的环的情况。

**解题思路：**

a\[\]数组为盒子，盒子里放入数，book\[\]记录数字是否已被使用，a\[1\]赋值为1，book\[1\]=1数字1已被使用；当查找到第n+1个盒子时，说明前n个盒子已查找完，若a\[1\]+a\[n\]也为素数即符合情况输出。未查找到n+1时，从数字二开始判断，若数字还未被使用且与前一个盒子中的数的和为素数，既符合，将数字放入盒子，记录数字已被使用，查找下一个盒子；查找结束要取消这个点的标记。

**错误分析：**

之前先想到的是啊哈算法上的对数的全排列，可是如果先对数进行全排列的话会数据特别多，不利于查找。

#include<Stdio.h>
    #include<string.h>
    #include<math.h>
    int a[25],book[25],n;
    
    int prime(int x)
    {
    	int j,k;
    	if(x==1)
    		return 0;
    	k=(int)sqrt(x);
    	for(j=2;j<=k;j++)
    		if(x%j==0)
    			return 0;
    	return 1;
    }
    
    void dfs(int num)
    {
    	int i;//i不能定义为全局变量 
    	if(num==n+1&&prime(a[1]+a[n])==1)//当查找到n+1个盒子时，说明前n个盒子已查找完，若符合，输出 
    	{
    	
    			for(i=1;i<n;i++)
    				printf("%d ",a[i]);
    			printf("%d\n",a[n]);
    	
    		
    	}
    	else
    		for(i=2;i<=n;i++)//利用循环查看第num个盒子可以放2-n中的哪个数 
    			if(book[i]==0&&prime(i+a[num-1])==1)//判断这个数是否被使用过，是否符合条件 
    			{
    				book[i]=1;
    				a[num]=i;
    				
    				dfs(num+1);
    				book[i]=0;
    			}
    }
    
    int main()
    {
    	int t=0;
    	while(scanf("%d",&n)!=EOF)
    	{
    		memset(book,0,sizeof(book));
    		memset(a,0,sizeof(a));
    		t++;
    		printf("Case %d:\n",t);
    		a[1]=1;
    		book[1]=1;
    		dfs(2);
    		printf("\n");
    	}
    	return 0;
    }

[1016-1.gif]: /images/20220519/b9d7849a5fd44e8b8a88fde54adaccac.png