回溯法——素数环C++实现

以你之姓@ 2022-01-23 03:35 218阅读 0赞

本文共928个字，预计阅读时间需要3分钟。

## 回溯法简介 ##

回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行（即能得到问题的解）。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。

回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。剪枝函数包括两类：

1.  使用约束函数，剪去不满足约束条件的路径；
2.  使用限界函数，剪去不能得到最优解的路径。  
    问题的关键在于如何定义问题的解空间，转化成树（即解空间树）。解空间树分为两种：子集树和排列树。两种在算法结构和思路上大体相同。

## 素数环问题 ##

#### 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.

![在这里插入图片描述][20190602085324200.gif]

#### 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

#### C++代码 ####

#include<iostream>
    #include<vector>
    using namespace std;
     
    //Nmax = 17
     
    //Prime Ring
    int n;
    int ans[22];
    bool hashx[22];
    int prime[] = {
        2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41};
     
    bool isPrime(int x){
        
        for(int i = 0; i < 13; i++){
        
            if(prime[i] == x)return true;
        }
        return false;
    }
     
    void checkAndPrint(){
         //检查输出由回溯法枚举得到的解
        if(! isPrime(ans[n] + ans[1]))return; //判断最后一个数与第一个数是否为素数，若不是则直接返回
        for(int i = 1; i <= n; i++){
        
            printf("%d%s", ans[i], i == n ? "\n" : " ");
        }
    }
     
    void DFS(int num){
         //num为环中的个数
        if(num > 1){
        
            if(!isPrime(ans[num] + ans[num - 1]))return; //如果不是素数，则返回
        }
        if(num == n){
        
            checkAndPrint(); //输出结果
            return;
        }
        for(int i = 2; i <= n; i++){
        
            if(!hashx[i]){
         //没有被放入
                hashx[i] =true;
                ans[num + 1] = i;
                DFS(num + 1); //继续尝试放入下一个
                hashx[i] = false; //回溯后，重新标记为未使用
            }
        }
    }
     
    int main(){
        
        int casex = 0;
        while(cin>>n){
        
            casex++;
            for(int i = 0; i < 22; i++)hashx[i] = false;
            ans[1] = 1;
            printf("Case %d:\n", casex);
            hashx[1] = true; //标记1已经被使用
            DFS(1);
        }
        return 0;
    }

[20190602085324200.gif]: /images/20220123/f5091d9617d0423685f3e272f9938ab7.png
[omegaxyz.com]: http://omegaxyz.com