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

素数环：将1，2，3，n个整数摆成一个环，要求相邻的两个数的和是一个素数。

例如：
输入：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

#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;
    search(1);
    cout<<"total method = "<<total<<endl;   
}

void search(int t){
    int i;
    for ( i = 1; i <=n; i++){
        if(a[1]>1) break;
        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 k=2,i=x+y;
        while(k<=sqrt(i)&&i%k!=0)k++;
        if(k>sqrt(i))return 1;
        else return 0;
    }

洛谷：UVA524

Previous Topic

Back to Lesson

Next Topic