本文目录一览：
- 1、数据结构求解素数环问题（JAVA版）：将N个自然数（1~N），使得每相邻两数之和为素数，构成一个素数环！
- 2、悬赏并跪求C语言大神帮忙解决此问题！关于素数环的
- 3、C语言素数环问题：输入n，输出n以内的素数环。我感觉思路是对的，怎么没有输出，请大侠看看！
- 4、回溯法求解素数环问题的时间复杂度分析
- 5、Exception in thread "main" java.lang.NumberFormatException:
数据结构求解素数环问题（JAVA版）：将N个自然数（1~N），使得每相邻两数之和为素数，构成一个素数环！
嗯。想一下。
这个是分别以每个自然数为起点，开始遍历，结果会有重复。
比如
(1, 2, 3, 4, 7, 10, 9, 8, 5, 6)
(6, 1, 2, 3, 4, 7, 10, 9, 8, 5)
import java.util.ArrayList;
import java.util.List;
public class PrimeRing {
// 求1～n素数环
public PrimeRing(int n) {
ListInteger src = new ArrayListInteger();
ListInteger dest = new ArrayListInteger();
for (int i = 1; i = n; i++) {
src.add(i);
}
loop(src, dest, n);
}
public void loop(ListInteger src, ListInteger dest, int n) {
if (dest.size() == n) {
Integer start = dest.get(0);
Integer end = dest.get(dest.size() - 1);
if (isPrime(start + end)) {
System.out.println(dest);
}
return;
}
for (int i = 0; i src.size(); i++) {
Integer element = src.remove(i);
if (dest.isEmpty()) {
dest.add(element);
} else {
Integer tmp = dest.get(dest.size() - 1);
if (isPrime(tmp + element)) {
dest.add(element);
} else {
src.add(i, element);
continue;
}
}
loop(src, dest, n);
src.add(i, element);
dest.remove(dest.size() - 1);
}
}
// 判断k是否为素数
public boolean isPrime(int k) {
if (k == 2)
return true;
if (k 2 || k 2 k % 2 == 0)
return false;
int j = (int) Math.sqrt(k); // Math.sqrt(k)返回k的平方根值
if (j % 2 == 0)
j--; // 获得测试范围内的最大奇数
while (j 2 k % j != 0)
j -= 2;
return j 2;
}
public static void main(String args[]) {
new PrimeRing(10);
}
}
悬赏并跪求C语言大神帮忙解决此问题！关于素数环的
文件输入输出应该不用多说吧。
freopen("prime.in","r",stdin);
freopen("prime.out","w",stdout);
至于算法的话，就是暴力搜索加剪枝：
如果当前值与上一个值之和是一个素数才继续向下搜索
用一个stack[N]记录数字
深搜过程：
void dfs(int depth)
{
if (depthn)
{
if (judge(stack[1]+stack[n]))
{
for (int i=1;i=n;++i)
printf("%d ",stack[i]);
printf("\n");
}
return ;
}
for (int i=1;i=n;i++)
if (!flag[i] judge(stack[depth-1]+i))
{
stack[depth]=i;
flag[i]=1;
dfs(depth+1);
flag[i]=0;
}
}
判断素数
bool judge(int N) //返回0为不是素数，返回1为是素数
{
if (N2) return 0;
for (int i=2;i=(int)sqrt(N);++i)
if (N%i) return 0;
return 1;
}
最后注意一点，在执行dfs过程时直接dfs(2)，然后令stack[1]=1;因为当stack[1]1之时，它的解可以由stack[1]=1时的解变换而来。flag[i]是记录该数出现过没有，因为每个数只能出现一次。
C语言素数环问题：输入n，输出n以内的素数环。我感觉思路是对的，怎么没有输出，请大侠看看！
#includestdio.h
#includestring.h
int is_prime(int x)
{
int i,flag;
for(i=2;i=x/2;i++)
if(x%i==0)
return 0;
return 1;
}
void dfs(int n,int *a,int *isp,int *vis,int cur)
{
if(cur==nisp[a[0]+a[n-1]])
{
for(int i=0;in;i++)
printf("%d ",a[i]);
printf("\n");
return ;
}
else
for(int i=1;i=n;i++)
if(!vis[i]isp[i+a[cur-1]])//如果i没有用过，并且与前一个数之和为素数
{
a[cur]=i;
vis[i]=1;
dfs(n,a,isp,vis,cur+1);
vis[i]=0;
}
}
int main()
{ int i,n,a[100],isp[100],vis[100];
memset(vis,0,sizeof(vis));
memset(isp,0,sizeof(isp));
scanf("%d",n);
for(i=0;in;i++)
a[i]=i+1;
for(i=1;i100;i++)
isp[i]=is_prime(i);
dfs(n,a,isp,vis,0);
return 0;
}
判断素数有问题
回溯法求解素数环问题的时间复杂度分析
其时间复杂度应该是O(!n)因为需要找到满足素数环的所有条件的取值，等价于找到2～n的其中一个排列。
C++的回溯素数环：
#includeiostream
using namespace std;
int n;
int a[20];
bool vist[20];
bool isPrime(int x){
if(x 2) return false;
for(int i = 2; i*i = x; i++){
if(x%i == 0) return false;
}
return true;
}
void print(){
for(int i = 0; i = n-1; i++){
cout a[i] " ";
}
cout endl;
}
void dfs(int cur){
int i;
if(cur == n isPrime(a[n-1]+a[0])){
print();
return;
}
for(i = 2; i = n; i++){
if(!vist[i]isPrime(i+a[cur-1])){
a[cur] = i;
vist[i] = 1;
dfs(cur+1);
vist[i] = 0;
}
}
}
int main(){
cin n;
if(n%2 == 0){
a[0] = 1;
vist[1] = 1;
dfs(1);
}
return 0;
}
Exception in thread "main" java.lang.NumberFormatException:
printf 格式化输出
%d 是数值
而根据报告的错误 数值转换异常
基本上可以认定 是非数值字符串转换成数值造成的
