素数环
时间限制: 1000 ms | 内存限制: 65535 KB
难度: 2
描述
有一个整数 n, 把从 1 到 n 的数字无重复的排列成环, 且使每相邻两个数 (包括首尾) 的和都为素数, 称为素数环.
为了简便起见, 我们规定每个素数环都从 1 开始. 例如, 下图就是 6 的一个素数环.
输入
有多组测试数据, 每组输入一个 n(0<n<20),n=0 表示输入结束.
输出
每组第一行输出对应的 Case 序号, 从 1 开始.
如果存在满足题意叙述的素数环, 从小到大输出.
否则输出 No Answer.
样例输入
6 8 3 0
样例输出
- Case 1:
- 1 4 3 2 5 6
- 1 6 5 2 3 4
- Case 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
- Case 3:
- No Answer
来源
hdu 改编 http://acm.nyist.edu.cn/JudgeOnline/search_result.php?source=hdu改编
上传者
ACM_丁国强 http://acm.nyist.edu.cn/JudgeOnline/profile.php?userid=ACM_丁国强
- #include<stdio.h>
- #include<string.h>
- int a[99],b[99],c[99];
- //a[99]数组用来放 0,1 是奇数就放 1 反之, b[99]数组用判断 1~n 个数中是否放入 c[99]数组里放入就 1 反之, c[99]数组用来存放 1~n;
- int f(int x) // 用来判断是否为素数, 是就返回 1
- {
- int i;
- for(i=2;i*i<=x;i++)
- {
- if(x%i==0)
- return 0;
- }
- return 1;
- }
- void f1(int x,int n)
- {
- int i;
- if(x==n&&a[c[0]+c[n-1]]) // 如果 c[0]+[n-1](也就是头尾相加)也为奇数时满足
- {
- for(i=0;i<n;i++)
- printf("%d",c[i]);
- printf("\n");
- return;
- }
- for(i=2;i<=n;i++)
- {
- if(!b[i]&&a[i+c[x-1]]) // 当前的 i+c[x-1](也就是 i + 它上一个相连的数)也为奇数时
- {
- c[x]=i;
- b[i]=1;
- f1(x+1,n); // 递归
- b[i]=0; // 回溯
- }
- }
- }
- int main()
- {
- int i,n,ans;
- ans=1;
- for(i=2;i<=40;i++)
- a[i]=f(i);
- while(scanf("%d",&n)!=EOF,n)
- {
- memset(b,0,sizeof(b));
- c[0]=1; // 第一个位置放 1;
- if(n==1) // 特殊情况
- {
- printf("Case %d:\n1\n",ans++);
- continue;
- }
- if(n%2==1) // 奇数不行
- {
- printf("Case %d:\nNo Answer\n",ans++);
- continue;
- }
- else
- {
- printf("Case %d:\n",ans++);
- f1(1,n);
- continue;
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2694155.html