巧排数字，将1,2,...,19,20这20个数字排成一排，使得相邻的两个数字之和为一个素数

数字，将1,2,...,19,20这20个数字排成一排，使得相邻的两个数字之和为一个素数"/>

巧排数字，将1,2,...,19,20这20个数字排成一排，使得相邻的两个数字之和为一个素数

巧排数字，将1,2,...,19,20这20个数字排成一排，使得相邻的两个数字之和为一个素数，且首尾两数字之和也为一个素数。编程打印出所有的排法。

排序方法：以贪心算法进行搜索，由于两个数字之和是一个素数，且首尾两数字之和也为一个素数，因此只需要找出以1开头的排列就可以了。使用贪心算法的同时使用回溯法，当遇到相邻两个数的时候就回溯到上一步从新搜索。

ofstream fout("D://Prime.txt",ios::app);
bool ISPrime(int n)
{for(int i=2;i<=sqrt((double)n);i++)if(n%i==0)return false;return true;
}
void PrimeArrange(int *arr,int begin,int length)
{if(begin==length){if(ISPrime(arr[begin-1]+arr[0])){copy(arr,arr+length,ostream_iterator<int,char>(fout,"  "));fout<<"\n";cout<<endl;}return;}else if(begin>1&&!ISPrime(arr[begin-1]+arr[begin-2]))//截枝和回溯{return;}else{for(int i=begin;i<length;i++){swap(arr[begin],arr[i]);PrimeArrange(arr,begin+1,length);//搜索swap(arr[begin],arr[i]);}}
}
void PrimeArrange(int *arr,int length)
{if(arr==NULL||length<=0){return;}PrimeArrange(arr,1,length);
}int main()
{int a[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};PrimeArrange(a,20);fout.close();cout<<"结束"<<endl;return 0;
}

部分结果如下（结果集太大）