当前位置:首页 > 题解目录 > 正文内容

质数环

亿万年的星光5年前 (2021-01-28)题解目录1806

【题目描述】

有一个整数n,把从1到n的数字无重复的排列成环,且使每相邻两个数(包括首尾)的和都为素数,称为素数环。为了简便起见,我们规定每个素数环都从1开始。例如,下面就是6的一个素数环。
1 4 3 2 5 6
1 6 5 2 3 4

【输入描述】

有多组测试数据,每组输入一个n(0<n<20),n=0表示输入结束。

【输出描述】

每组第一行输出对应的Case序号,从1开始。如果存在满足题意叙述的素数环,从小到大输出。否则输出No Answer。

【样例输入】

6
8
3
0

【样例输出】

Case1:
1 4 3 2 5 6
1 6 5 2 3 4
Case2:
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
Case3:
No Answer

【题目分析】

(1)搜索回溯的题目。从1开始,每个位置有N种不同的可能,只要填进去的数合法就行。
(2)合法指的是与前面的数不同,与左边相邻的和是一个素数
(3)最后一个数还要与第一个判断。


【参考代码】

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,ans[100],flag[100]; //输入数,结果数组,标记数组
//判断两个数的和是不是素数函数
int prime(int x, int y)
{
   int k=2, i=x+y;
   while(k<=sqrt(i) && i%k!=0)
       k++;
   if(k>sqrt(i))
       return 1;
   else
       return 0;    
}
//打印输出函数
int print()
{
   for(int i=1;i<=n;i++)
       cout<<ans[i]<<" ";
   cout<<endl;    
}
//搜索回溯算法
int search(int k)
{
   int i;
   for(i=1;i<=n;i++) //n个数
       if( prime(ans[k-1],i) && (flag[i]==0)) //判断与前一个数是否构成素数及这个数当前是不是可用    
       {    ans[k]=i;
           flag[i]=1; //标记当前这个数使用过了
           if(k==n) //到达边界
           {
               if( prime(ans[n],ans[1])) //严重最后一个和第一个
                   print();
           }
           else
               search(k+1);
           flag[i]=0;
   }
}
int main()
{
   cin>>n;
   search(1); //从第一个位置开始找
   return 0;
}

但是你运行上面的代码后发现和结果不一样,因为题目要求每个序列必须从1开头。所以还要再改一下,我们稍微改下if判断条件就可以实现了。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,ans[100],flag[100]; //输入数,结果数组,标记数组
//判断两个数的和是不是素数函数
int prime(int x, int y)
{
   int k=2, i=x+y;
   while(k<=sqrt(i) && i%k!=0)
       k++;
   if(k>sqrt(i))
       return 1;
   else
       return 0;    
}
//打印输出函数
int print()
{
   for(int i=1;i<=n;i++)
       cout<<ans[i]<<" ";
   cout<<endl;    
}
//搜索回溯算法
int search(int k)
{
   int i;
   for(i=1;i<=n;i++) //n个数
       if( prime(ans[k-1],i) && (flag[i]==0)) //判断与前一个数是否构成素数及这个数当前是不是可用    
       {    ans[k]=i;
           flag[i]=1; //标记当前这个数使用过了
           if(k==n) //到达边界
           {
               if( prime(ans[n],ans[1]) && ans[1]==1) //严重最后一个和第一个
                   print();
           }
           else
               search(k+1);
           flag[i]=0;
   }
}
int main()
{
   cin>>n;
   search(1); //从第一个位置开始找
   return 0;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:
返回列表

上一篇:字符全排列(2)

下一篇:数列

相关文章

字符串比较

【题目描述】给出了n(n<=100000)个由数字和字母组成的字符串(长度小于1000),求与给出字符串相同字符串的个数。【输入描述】第一行是一个数n。接下来n行,每行都是一个字符串。接下来一行...

【题解】泥泞路(2019青岛市程序设计竞赛)

【题目描述】大雨过后,从小A的农场到镇上的公路上有一些泥泞路段,为了方便出行,他决定将若干块长度为L的木板可以铺在这些泥泞路段上,问他至少需要多少块木板,才能将所有的泥泞路段覆盖住。【输入】第一行为正...

【题解】分糖果

【题目描述】小A在生日这天收到了哥哥送来的一盒糖果,这盒糖果共有M个,小A要把这盒糖果放到N个盘子中(允许有盘子不放),请问,有多少种不同的放法?请注意:数值相同,顺序不同,我们视为是相同的放法,比如...

【题解】统计自然数

【题目描述】某次科研调查时得到了n个自然数,每个数均不超过1500000000(1.5*109)。已知不相同的数不超过10000个,现在需要统计这些自然数各自出现的次数,并按照自然数从小到大的顺序输出...

【题解】字符串

【题目描述】Kri 非常喜欢字符串,所以他准备找 t组字符串研究。 第 i次研究中, Kri 准备了两个字符串S 和R ,其中S 长度为n ,且只由  0 , 1 , -  三种...

【题解】柠檬水找零

【题目描述】在柠檬水摊上,每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。每位顾客只买一杯柠檬水,然后向你...