Liukairui 2017-08-26 14:24 采纳率: 100%
浏览 797
已结题

大家帮忙看一下这个回溯哪里写错了

原题

素数环(Prime Ring Problem, UVa 524)
输入正整数n,把整数1, 2, 3,…, n组成一个环,使得相邻两个整数之和均为素数。 输出
时从整数1开始逆时针排列。 同一个环应恰好输出一次。 n≤16。
样例输入:
6 样
例输出:
1 4 3 2 5 6
1 6 5 2 3 4

我的代码

 #include <iostream>
#include <cstdio>
#include <math.h>
#include <cstring>
using namespace std;
int ans[20];
int n;
int used[20];

bool iss(int x)
{
int is=1;
int q;
q=floor(sqrt(x)+0.5);
for (int k=2;k<=q;k++)
    {
    if(x%k==0){is=0;break;}
    }
if(is==1)return true;
else return false;
}

void dfs(int cur)
{
//cout<<cur<<"     ";
if((cur==n)&&(iss(ans[cur-1]+ans[0])))
    {
    for(int k=0;k<n-1;k++)cout<<ans[k]<<",";
    cout<<ans[n-1]<<"\n";
    }

else for(int i=2;i<=n;i++)
    {if(used[i]==1)continue;
    else if(iss(ans[cur]+i)){ans[cur]=i;used[i]=1;dfs(cur+1);used[i]=0;}
    }
}

int main()
{
cin>>n;
memset(used,0,sizeof(used));
ans[0]=1;
used[1]=1;
dfs(1);
system ("pause");
return 0;
}

输入6
输出
1,4,3,6,5,2
请按任意键继续. . .

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-08-27 15:15
    关注
    评论

报告相同问题?

悬赏问题

  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)