素数环 回溯法实现

素数环就是1-n个数，按某一序列排列，使得任意相邻2个数的和为素数。

比如1-6。素数环的排列顺序如下：

1 4 3 2 5 6 
1 6 5 2 3 4

那么实现的算法，同样可以使用回溯法。

回溯法的关键思想是要找到回溯的入口点。即确定什么时候继续运算下去，什么时候停止继续，尝试下一个值。

比如对于1-6这个序列，本算法的伪代码

先把环初始化，即有0,0,0,0,0,0这样一个序列。

for i从1到6

把i放入第一个位子

检测这个环是不是素数环（忽略0，忽略首尾相加）

如果是

        继续取下一个数放到下一个位置

       直到这个环上的数字都放置了，打印此环。

如果不是

    这个位子的数字清零

如果所有的数字都尝试了，都不行

那么这个序列无法形成素数环。

其中，把这个位子清零就是回溯，代表尝试下一个值。

比如，当递归进去1234,5填入后，发现不行，则情况，再填6，也不行，此时6清零。递归退出。即set(index + 1)语句运行结束，然后再运行清零。此时清零的是4。

本质上，可以把递归调用，看成是普通调用，只是这个调用的方法，和当前方法长的一模一样而已。

具体代码如下： 

 
 


  
  
using System;  

  
  
using System.Collections.Generic;  

  
  
using System.Linq;  

  
  
using System.Text;  

  
  
 

  
  
namespace ConsoleApplication3  

  
  
{  

  
  
    public class Program  

  
  
    {  

  
  
 

  
  
        public static List<int> lst = new List<int>();  

  
  
        public static List<int> numlst = new List<int>();  

  
  
        static public readonly int count = 6;  

  
  
        static void Main(string[] args)  

  
  
        {  

  
  
            for (int i = 1; i <= count; i++)  

  
  
            {  

  
  
                numlst.Add(i);  

  
  
                lst.Add(0);  

  
  
            }  

  
  
 

  
  
            set(0);  

  
  
        }  

  
  
 

  
  
        static public void set(int index)  

  
  
        {  

  
  
            //Console.WriteLine("进入递归" + index);  

  
  
            #region for  

  
  
            foreach (var item in numlst)  

  
  
            {  

  
  
                //这句很重要，表示已经在环中的数字自动忽略掉。  

  
  
                if (lst.Contains(item))  

  
  
                    continue;  

  
  
 

  
  
                lst[index] = item;  

  
  
                //lst.ForEach(x => { if (x > 0) { Console.Write(x + " "); } });  

  
  
                //Console.WriteLine();  

  
  
                if (valid(lst))  

  
  
                {  

  
  
                    if (index == count - 1)  

  
  
                    {  

  
  
                        Console.Write("OK! ");  

  
  
                        lst.ForEach(x => { Console.Write(x + " "); });  

  
  
                        Console.WriteLine();  

  
  
                        //return;//此句表示只找一组  

  
  
                    }  

  
  
                      

  
  
                    set(index + 1);  

  
  
                }  

  
  
                lst[index] = 0;  

  
  
                //lst.ForEach(x => { if (x > 0) { Console.Write(x + " "); } });  

  
  
                //Console.WriteLine();  

  
  
            }  

  
  
            #endregion  

  
  
            

  
  
 

  
  
            //Console.WriteLine("退出递归" + index);  

  
  
        }  

  
  
 

  
  
        static public bool valid(List<int> lst)  

  
  
        {  

  
  
            List<int> tmplst = lst.Where(x => x > 0).ToList();  

  
  
            if (tmplst.Count < 2)  

  
  
                return true;  

  
  
            if (tmplst.Count == count)  

  
  
            {  

  
  
                if (!isSushu(tmplst[0] + tmplst[tmplst.Count - 1]))  

  
  
                {  

  
  
                    return false;  

  
  
                }  

  
  
            }  

  
  
            for (int i = 0; i < tmplst.Count - 1; i++)  

  
  
            {  

  
  
                if (!isSushu(tmplst[i] + tmplst[i + 1]))  

  
  
                {  

  
  
                    return false;  

  
  
                }  

  
  
            }  

  
  
            return true;  

  
  
        }  

  
  
 

  
  
        static public bool isSushu(int s)  

  
  
        {  

  
  
            if (s == 1)  

  
  
                return false;  

  
  
            if (s == 2)  

  
  
                return true;  

  
  
            for (int i = 2; i <= Math.Sqrt(s) + 1; i++)  

  
  
            {  

  
  
                if (s % i == 0)  

  
  
                {  

  
  
                    return false;  

  
  
                }  

  
  
            }  

  
  
 

  
  
            return true;  

  
  
        }  

  
  
    }  

  
  
 

  
  
} 
 
 

本文转自cnn23711151CTO博客，原文链接：http://blog.51cto.com/cnn237111/851045 ，如需转载请自行联系原作者