素数环问题(回溯_排列树)

时限：1000ms 内存限制：10000K 总时限：3000ms

描述：

把1到20这重新排列，使得排列后的序列A满足： a. 任意相邻两个数之和是素数 b. 不存在满足条件a的序列B使得：A和B的前k（0 <= k <= 19）项相同且B的第k+1项比A的第k+1项小。

输入：

没有输入。

输出：

输出A，两个数字之间用一个空格隔开，第一个数字前面和最后一个数字后面没有空格。

输入样例：

输出样例：

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
long sum=0;
int Arr[21];//Arr[0]不用
int isprime(int m)//判断是否为素数
{
    int k=(int)sqrt(m);
    for(int i=2;i<=k;i++)
        if(m%i==0)    return 0;
    return 1;
}
void printresult()
{    
    sum++;//每此满足素数环要求就加1
    if(sum==2)
    {    printf("%d",Arr[1]);
        for(int i=2;i<=20;i++)
            printf(" %d",Arr[i]);
        printf("\n");
        exit(0);//彻底结束该程序//不同于return;
        //若把if条件去掉，exit(0);改为return;可输出所有素数环
    }
}
void swap(int m,int i)
{
    int temp;
    temp=Arr[m];
    Arr[m]=Arr[i];
    Arr[i]=temp;
}    
void search(int m)//2,3,4...20,21
{
    if(m>20)
    {    if(isprime(Arr[20]+Arr[1]))    printresult();
        return;
    }
    else
    {    for(int i=m;i<=20;i++)//只能和后面的数交换，而不能和前面的数交换
        {
            swap(m,i);
            if(isprime(Arr[m-1]+Arr[m]))
                search(m+1);
            swap(m,i);
        }
    }
}
int main()
{
    for(int i=1;i<=20;i++)
        Arr[i]=i;//初始化
    search(2);
    return 0;
}

/*
sum=1: 1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 20 11 18 19 12
sum=2: 1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 20 11 12 19 18!!!!!
sum=3: 1 2 3 4 7 6 5 8 9 10 13 18 19 12 11 20 17 14 15 16
sum=4: 1 2 3 4 7 6 5 8 9 10 19 12 11 20 17 14 15 16 13 18
sum=5: 1 2 3 4 7 6 5 8 9 10 19 12 11 20 17 14 15 16 13 18
sum=10:1 2 3 4 7 6 5 8 9 20 11 12 17 14 15 16 13 10 19 18
sum=20:1 2 3 4 7 6 5 8 11 12 19 10 9 20 17 14 15 16 13 18
*/