Go语言视频零基础入门到精通

javalearner

问题描述：
         将从1到n这n个整数围成一个圆环，若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。

20以内的素数环：
1  2  3  4  
1  4  3  2  5  6
1  2  3  8  5  6  7  4
1  2  3  4  7  6  5  8  9  10
1  2  3  4  7  6  5  12  11  8  9  10  
1  2  3  4  7  6  13  10  9  14  5  8  11  12
1  2  3  4  7  6  5  12  11  8  9  14  15  16  13  10
1  2  3  4  7  6  5  8  9  10  13  16  15  14  17  12  11  18
1  2  3  4  7  6  5  8  9  10  13  16  15  14  17  20  11  12  19  18

算法设计：
         利用回溯法穷举所有可能性，找到一个后，结束程序。具体来讲，就是在第一个位置先设置为1，然后第二个位置试试2行不行，再在第三个位置试试3行不行，再在第四个位置试试4行不行，再在第五个位置试试5，发现不行，然后试试6，发现还不行，再试试7，终于可以了，继续往下试验……

代码编写：

1. import java.util.Arrays;
   
2. import java.util.Random;
   
3. public class MyTest {
   
4.     public static void main(String[] args) {
   
5.         
   
6.         int length = 22;      //素数环的长度
   
7.         int[] b = new int[length];    //一个数组，用来标识第i个数字是否被使用过。
   
8.         Arrays.fill(b, 0);      //将数组初始化为0，标识所有数字尚未被使用
   
9.         int[] ring = new int[length];      //用于存放最终素数环的数组
   
10.         ring[0] = 1;                    //素数环的第一个数字必然为1（因为是个环，我们从1那一点开始考虑就行了）
    
11.         if(primeNumRing(b, ring, 1))
    
12.             printArray(ring);
    
13.         else
    
14.             System.out.println("不存在素数环");
    
15.     }
    
16.    
    
17.         //负责打印数组，最后输出素数环的时候用得着
    
18.     public static void printArray(int a[]) {
    
19.         for(int x:a) {
    
20.             System.out.print(x+"  ");
    
21.         }
    
22.         System.out.println();
    
23.     }
    
24.    
    
25.         //用递归的方法判断素数环
    
26.         //数组b用来标识某个数字是否被使用过了，数组ring用来存储素数环
    
27.        //整数n表示当前正在考察素数环中的第几个数字
    
28.     private static boolean primeNumRing(int[] b, int[] ring, int n) {
    
29.                //当最后一个数字考察完毕后，测试一下他加上第一个数字（也就是1）是不是素数
    
30.                //如果是素数，那么就说明找到了素数环，如果不是，则没有找到
    
31.         if(n == b.length)
    
32.             return isPrimeNum(ring[n-1]+1);
    
33.                //start是循环的开始点，因为奇数的旁边必然是偶数，偶数的旁边必然是奇数
    
34.               //因此若前一个数是偶数，那么当前考察的必然全是奇数，反之亦然
    
35.               //因此，循环的跨度为2
    
36.         int start = 2-n%2;
    
37.         for(int i=start; i< b.length; i+=2) {
    
38.                         //如果当前考察的数字没有被使用过，并且和前一个数字相加的和为素数的话
    
39.             if(b[i]==0 && isPrimeNum((i+1)+ring[n-1])) {
    
40.                 b[i] = 1;            //将其标识设置为"已使用"
    
41.                 ring[n] = i+1;   //将其放入素数环中
    
42.                                 //如果他后面的所有数字都符合要求，则找到素数环，反之将标识清零后，考察下一个数字
    
43.                 if(primeNumRing(b, ring, n+1))
    
44.                     return true;
    
45.                 else
    
46.                     b[i] = 0;
    
47.             }
    
48.         }
    
49.         return false;
    
50.     }
    
51.    
    
52.         //判断一个数是否为素数
    
53.        //这里没有使用通用的判别方法，一般来讲，素数环都不会超过30个数字
    
54.        //因此需要判断的最大的数字不会超过60。
    
55.        //本函数的测试因子最大为11，也就是说凡是小于168（13的平方）的素数都能够被判断，够用了
    
56.     private static boolean isPrimeNum(int x) {
    
57.         int[] primeNums = {2, 3, 5, 7, 11};
    
58.         int i;
    
59.         for(i=0; i< primeNums.length; i++) {
    
60.             if(x>primeNums[i] && x%primeNums[i] == 0)
    
61.                 break;
    
62.         }
    
63.         return (i==primeNums.length);
    
64.     }
    
65. }
    
67. 运行结果：
    
68. C:java>java    MyTest
69. 1  2  3  4  7  6  5  8  9  10  13  16  15  14  17  12  11  20  21  22  19  18
70. 
    

复制代码

源码下载：http://file.javaxxz.com/2014/11/6/000320671.zip