回溯算法-素数环

洛谷：UVA524
OJ: P1414

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

素数环：将1，2，3，n个整数摆成一个环，要求相邻的两个数的和是一个素数。这样的素数环在n=6时有2种方案， n=8时有4种方案。


例如：
输入：6
<1>1 4 3 2 5 6
<2>1 6 5 2 3 4
total method = 2
输入：8
<1>1 2 3 8 5 6 7 4
<2>1 2 5 8 3 4 7 6
<3>1 4 7 6 5 8 3 2
<4>1 6 7 4 3 8 5 2
total method = 4

动画演示：

代码实现：

 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
/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2023-07-27 18:36:00
 * 最后修改: 2026-05-06 14:40:36
 * 文件描述: 素数环
****************************************************************/

#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;
bool  b[21]={0};
int total=0,a[21]={0};
void search(int);
void print();
bool isPrimeNumber(int,int);
int n;
int main(){
    cout<<"please input a number: ";
    cin>>n;
    a[1]=1;
    b[1]=true;
    search(2);
    cout<<"total method = "<<total<<endl;   
}

void search(int t){
    int i;
    for ( i =2; i <=n; i++){
        if(isPrimeNumber(a[t-1],i) && (!b[i])){
        a[t]=i;
        b[i]=1;
        if(t==n ){
            if(isPrimeNumber(a[n],a[1]))
            print();
            }
        else search(t+1);
        b[i]=0;
        
        }
    }
}
    void print(){
        total++;
        cout<<"<"<<total<<">";
        for (int j =1; j<= n; j++){
            cout<<a[j]<<" ";
        }
        cout<<endl;
    }

    bool isPrimeNumber(int x,int y){
        int sum=x+y;
        for(int k=2;k*k<=sum;k++){
            if(sum%k==0)return false;
        }
       return true;
    }

Previous Topic
Back to Lesson
Next Topic