本文主要是介绍hdu 1016Prime Ring Problem，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
我刚开始想到的， 1：当n为奇数的时候， 肯定没有符合条件的:2：符合条件的排列相邻的数字的奇偶性肯定不同；我开始枚举产生排列来判断是否符合条件， 但是果断TL了， 然后参考别人的代码才过的，几乎和别人的代码差不多……我还有一种想法， 可以分别产生奇数的排列， 偶数的排列， 然后合并来判断……比如6；可以产生每1,3,5的一个排列，就将 2,4,6的所有排列插入到1,3,5，以此来判断……不过这样貌似效率也不太高，并且产生的排列有些是乱序的……通过这个题我发现我对产生排列的递归还是不太明白……
#include<iostream>
#include<cstring>
using namespace std;
int used[20], a[20];
bool prime[40];
void Init()//用筛法求出40之内的素数
{memset(prime,1,sizeof(prime));for(int i=2; i<7; i++) for(int j=2; j*i<40; j++){prime[i*j]=0;}
}
void DFS(int num, int n)
{if(num>n && prime[a[n]+a[1]])//判断第一个和最后一个数的和是否为素数 {for(int i=1; i<n; i++)cout<<a[i]<<" ";cout<<a[n]<<endl;return;}for(int i=2; i<=n; i++)//生成开头数字为1的所有排列 {if(!used[i] && prime[a[num-1]+i])//如果相邻两个数的和为素数,继续 {used[i]=1;a[num]=i;DFS(num+1, n);used[i]=0; } }}
int main()
{int n, num=1;Init();a[1]=1;while( cin>>n ){cout<<"Case "<<num++<<":"<<endl;if(n%2==0)//当n为奇数时，肯定不符条件 { memset(used,0,sizeof(used)); DFS(2,n);//从第二个数开始搜索 } cout<<endl;}
}
附上我TL的代码
#include<iostream>
#include<algorithm>
using namespace std;
int a[20];
bool prime[40];
void Init()//用筛法求出40之内的素数
{memset(prime,1,sizeof(prime));for(int i=2; i<7; i++) for(int j=2; j*i<40; j++){prime[i*j]=0;}
}
bool Check(int n)
{for(int i=1; i<n; i++){if( !prime[a[i]+a[i+1]] )return 0;}if( !prime[a[n]+a[1]]) return 0;return 1;
}void Solve(int n)
{if( Check(n) ){for(int i=1; i<n; i++)cout<<a[i]<<" ";cout<<a[n]<<endl;}int posi,posj, temp, min;while( 1 )//运用排列生成的非递归算法 {for( int i=n-1; i>=1; i--){if(a[i+1]>a[i]){posi=i;break;}}if( posi==1 ) break;min=999;for(int j=n; j>posi; j--){if(a[j]>a[posi] && a[j]<min){posj=j;min=a[j];}}temp=a[posj];a[posj]=a[posi];a[posi]=temp;//交换 sort(a+posi+1,a+n+1);if( Check(n) ){for(int i=1; i<n; i++)cout<<a[i]<<" ";cout<<a[n]<<endl;}}
}
int main()
{int n, num=1;Init();while( cin>>n ){cout<<"Case"<<num<<":"<<endl;if(n%2==0){ for(int i=1; i<=n; i++)//先赋值 a[i]=i;Solve(n);} cout<<endl;num++;}
}
这篇关于hdu 1016Prime Ring Problem的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
