素数圆环
时间限制: 1 Sec 内存限制: 32 MB
题目描述
如图所示为一个由n个圆圈构成的圆环。将自然数1,2,…,n放入圆圈内,并且要求任意两个相邻的圆圈内的数字之和为素数。请问给你圆圈数,你能给出放置自然数的所有正确方案吗?
注意:圆圈中的数字一定是从1开始的,并且连续不重复。
输入
输入包含多组测试数据。每组输入占一行,为整数n(0 < n<20),表示圆圈数。
输出
对于每组输入,输出所有正确的方案,按字典序从小到大排序。每组输出后输出一个空行。具体输出格式见输出样例。
注意:只能按照顺时针方向放置数字。
样例输入
6
8
样例输出
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
题意概括
给出一个数字n求使用1-n这n个数字组成一个素数环,第一个必须是1;
解题思路
这个题我是用的dfs暴力求解的。枚举所有情况,看哪一种情况符合就输出哪一种情况。
代码如下
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int aa[50];
int line[30],n;
int vis[30];
int date[20][30];
int sushu (int x)
{
int i;
int k=(int)sqrt(x);
for(i=2;i<=k;i++)
if(x%i==0)
return 0;
return 1;
}
/*void dfs(int x)
{
printf("%d",line[x-1]);
int i;
if(x>n){
printf("***\n");
//if(date[line[n]][0]==1)
// return ;
printf("%d",line[1]);
for(i=2;i<=n;i++){
printf(" %d",line[i]);
}
printf("\n");
return ;
}
for(i=0;date[line[x-1]][i]<=n;i++){
if(vis[date[line[x-1]][i]]==0) {
vis[date[line[x-1]][i]]=1;
line[x]=date[line[x-1]][i];
dfs(x+1);
vis[date[line[x-1]][i]]=1;
}
}
}*/
void dfs(int x)
{
int i;
if(x>n){
if(aa[line[n]+1]==0)
return ;
printf("%d",line[1]);
for(i=2;i<=n;i++)
printf(" %d",line[i]);
printf("\n");
return ;
}
for(i=0;date[line[x-1]][i]<=n;i++){
if(vis[date[line[x-1]][i]]==0){
vis[date[line[x-1]][i]]=1;
line[x]=date[line[x-1]][i];
dfs(x+1);
vis[date[line[x-1]][i]]=0;
}
}
}
int main ()
{
int i,j,k;
memset(aa,0,sizeof(aa));
memset(date,inf,sizeof(date));
for(i=3;i<=50;i++){
if(sushu(i)) aa[i]=1;
}
for(i=1;i<20;i++){
//printf("%d::",i);
for(j=1,k=0;j<20;j++){
if(aa[i+j]){
date[i][k]=j;
k++;
// printf("%d ",date[i][k-1]);
}
}
//printf("\n");
}
int l=0;
while(~scanf("%d",&n)){
l++;
memset(vis,0,sizeof(vis));
vis[1]=1;
line[1]=1;
printf("Case %d:\n",l);
dfs(2);
printf("\n");
}
return 0;
}
转载于:https://www.cnblogs.com/lanaiwanqi/p/10445728.html
今天的文章素数圆环分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/7262.html