 2020-09-24 19:55

# 看不懂这个回溯，要什么条件才能执行这个回溯呢？

``````import java.util.Scanner;

public class 素数环 {

public static void main(String[] args) {

Scanner sss=new Scanner(System.in);
int n=sss.nextInt();
int r[]=new int[n];
r=1;
dfs(n,r,1);
}

public static void dfs(int n,int r[],int cur) {

if(cur==n&&isP(r+r[n-1])) {    //填到末尾了，并且首尾相加为素数才算成功
print(r);
return;
}
for(int i=2;i<=n;i++) {        //尝试用每个数字填到cur这个位置
if(check(r,i,cur)) {       //数组中没有i这个数，且i和上一个数之和为素数
r[cur]=i;              //将i放在cur的位置，并向前走一步
dfs(n,r,cur+1);
r[cur]=0;              //回溯
}
}
}

public static void print(int a[]) {

for(int i=0;i<a.length;i++) {
System.out.print(a[i]+(i==a.length-1?"":" "));
}
System.out.println();
}

public static boolean check(int a[],int i,int cur){    //检测i这个数能否放到cur这个位置。
for(int e:a) {
if(e==i||!isP(a[cur-1]+i))  return false;
}

return true;
}

public static boolean isP(int x) {     //判定是否为素数

for(int i=2;i*i<=x;i++) {

if(x%i==0)   return false;
}
return true;
}
}

``````
• 点赞
• 写回答
• 关注问题
• 收藏
• 复制链接分享
• 邀请回答

#### 1条回答

• 应该是视频错了

这里不会无限递归
if(cur==n&&isP(r+r[n-1]))
这是递归终止条件

点赞 评论 复制链接分享