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
#include <stdio.h> #include <string.h> #define MAXLEN 40 #define DATALEN 20 int isPrime[MAXLEN]; int visited[DATALEN]; int result[DATALEN]; void DFS(int curr, int num); int main(void) { int n; int count = 0; memset(isPrime, 0, MAXLEN * sizeof(int)); isPrime[3]=isPrime[5]=isPrime[7]=isPrime[11]=isPrime[13]=isPrime[17]=isPrime[19]=isPrime[23]=isPrime[29]=isPrime[31]=isPrime[37]=1; while(scanf("%d", &n) == 1) { count++; memset(visited, 0, DATALEN * sizeof(int)); memset(result, 0, DATALEN * sizeof(int)); visited[1] = 1; result[1] = 1; printf("Case %d:/n", count); DFS(2, n); printf("/n"); } } void DFS(int curr, int num) { int i, j; for(i = 2; i <= num; i++) { if(visited[i]==0 && isPrime[result[curr-1]+i]==1) { visited[i] = 1; result[curr] = i; if(curr != num) { DFS(curr+1, num); } else if(isPrime[i+1]==1) { for(j = 1; j < num; j++) { printf("%d ", result[j]); } printf("%d/n", result[j]); } visited[i] = 0; result[curr] = 0; } } }
方法：使用深度优先搜索
注意：1、素数的定义，2也是素数；此外最后一个数除了与前面的数的和为素数外，还需于第一个数的和为素数，因为是环；
技巧：数组isPrime[n] 表示n是否为素数，1为是0为否，这样直接操作数组下标就可以判断该数是否为素数，eg：isPrime[result[curr-1]+i]==1
