weixin_47387970
weixin_47387970
2020-09-24 19:55
采纳率: 57.1%
浏览 96
已采纳

看不懂这个回溯,要什么条件才能执行这个回溯呢?

题目描述:
素数环:从1到n这n个数摆成一个环,要求相邻的两个数的和是一个素数。

大佬们应该都接触过这个题,我就不详细说别的了。

本人刚接触递归回溯这个算法,无法理解
我怎么总觉得到了dfs(n,r,cur+1)这一行之后会一直递归下去呢?
如果递归到满足if(cur==n&&isP(r[0]+r[n-1]))的时候就结束,那如果不满足这个条件难道一直递归下去吗?我怎么感觉没出口呢??
在什么条件下才会执行r[cur]=0这条回溯语句呢?
求大佬们解答,救救孩子吧

代码选自蓝桥杯郑未老师的视频,视频里老师说这个回溯语句加不加都行,但是我运行之后发现不加回溯语句的话结果是不对的。

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[0]=1;
        dfs(n,r,1);
    }

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

        if(cur==n&&isP(r[0]+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条回答 默认 最新

  • caozhy
    已采纳

    应该是视频错了

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

    点赞 评论

相关推荐