首页 > itarticle > 搜索策略学习笔记（3）：有界深度求证问题解的存在性实例

搜索策略学习笔记（3）：有界深度求证问题解的存在性实例

admin 11月 12, 2020 0

Case：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.
这里写图片描述

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

6
8

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

My AC Code

As long as the case require all of the solution,so we can choose either BFS or DFS.I give the priority to DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
//Author:Call偶围城
#include <math.h>
#define MAX 25
int vis[MAX];
int path[MAX];
int n;
int case_cnt = 0;
bool (int x) {
	int i;
	double m = sqrt(x);
	for (i = 2;i <= m;i++)
		if (x % i == 0) return false;
	
	 return true;
}
void PrintCase() {
	int i;
	
	printf("%d",path[1]);
	for (i = 2;i <= n;i++) {
		printf(" %d",path[i]);
	}
	printf("n");
}
void Visit (int deep) {
	if (deep > n) return;
	
	if (deep == n) {
		if (IsPrime(path[n]+1))
			PrintCase();
			
		vis[path[n]] = 0;
		return;
	}
	int i,j;	
	for (i = 2;i <= n;i++) {
		if ((path[deep]+i) % 2 != 0 && vis[i] != 1)
			if (IsPrime(path[deep]+i)) {
				vis[i] = 1;
				path[deep+1] = i; 
	
				Visit(deep+1);
			}
	}
	vis[path[deep]] = 0;
}
void Init(int *arr) {
	int i;
	
	arr[1] = 1;
	for (i = 2;i <= MAX;i++)
		arr[i] = 0;
}
int main() {
	int i,j,k;
	
	while (scanf("%d",&n) != EOF) {
		if (n % 2 == 1) {
			continue;
		}
		
		Init(vis);
		path[1] = 1;
		
		Visit(1);
		printf("n");	
	}
	return 0;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能