찾다
Javajava지도 시간Java 데이터 구조 및 알고리즘을 사용하여 재귀 및 역추적을 구현하는 방법

1. 재귀란 무엇인가요?

간단히 말하면 재귀는 메소드가 호출될 때마다 다른 변수를 전달하는 것입니다. 재귀는 프로그래머가 복잡한 문제를 해결하고 코드를 간결하게 만드는 데 도움이 됩니다.

실제 응용 시나리오, 미로 문제(역추적), 재귀(재귀)를 살펴보세요

Java 데이터 구조 및 알고리즘을 사용하여 재귀 및 역추적을 구현하는 방법

재귀를 이해하는 데 도움이 되는 두 가지 작은 사례를 나열하겠습니다. 여기서는 재귀 호출 메커니즘을 검토하겠습니다.

  • 인쇄 문제

  • 팩토리얼 문제

public static void test(int n) {
    if (n > 2) {
	    test(n - 1);
    }
    System.out.println("n=" + n);
}
 
public static int factorial(int n) {
    if (n == 1) {
        return 1;
    } else {
        return factorial(n - 1) * n;
    }
}

재귀를 사용하여 해결하는 문제는 무엇인가요?

  • 여러 여왕 문제, 하노이 탑, 계승 문제, 미로 문제, 공의 합 바구니 문제(구글 프로그래밍 대회).

  • 재귀는 퀵 정렬, 병합 정렬, 이진 검색, 분할 정복 알고리즘 등 다양한 알고리즘에도 사용됩니다.

  • 스택으로 해결될 문제-->코드가 비교적 간결합니다.

재귀를 위해 따라야 할 중요한 규칙

  • 메서드가 실행되면 보호되는 새로운 독립 공간(스택 공간)이 생성됩니다.

  • 메서드의 지역 변수는 독립적이며 n 변수와 같이 서로 영향을 주지 않습니다.

  • 메소드에 참조 유형 변수(예: 배열)가 사용되는 경우 참조 유형의 데이터가 공유됩니다.

  • 재귀는 재귀를 종료하기 위한 조건에 접근해야 합니다. 그렇지 않으면 무한 재귀가 되고 StackOverflowError가 나타나며 죽게 됩니다 :).

  • 메서드가 실행을 완료하거나 반환을 만나면 반환됩니다. 이를 호출하는 사람은 누구든지 호출하는 사람에게 결과를 반환합니다. 동시에 메서드가 실행을 완료하거나 반환하면 메서드도 실행을 완료합니다.

2. 코드 사례 1 - 미로 문제

설명: 공이 가는 경로는 프로그래머가 설정한 경로 찾기 전략, 즉 위쪽, 아래쪽, 왼쪽의 경로 찾기 순서와 관련됩니다. , 오른쪽은 공과 관련된 경로를 선택할 때 먼저 (오른쪽 아래, 왼쪽 위)를 사용한 다음 (오른쪽 위, 왼쪽 아래)로 변경하여 경로가 변경되는지 확인할 수 있습니다. 역추적 현상을 테스트합니다.

package com.szh.recursion;
 
/**
 * 走迷宫问题
 */
public class MiGong {
 
    //使用递归回溯来给小球找路, 说明:
    //1. map 表示地图
    //2. i,j 表示从地图的哪个位置开始出发 (1,1)
    //3. 如果小球能到 map[6][5] 位置,则说明通路找到.
    //4. 约定:当 map[i][j] 为 0 表示该点没有走过; 当为 1 表示墙; 2 表示通路可以走;
    //5. 在走迷宫时,需要确定一个策略(方法) 下->右->上->左 , 如果该点走不通,再回溯
    public static boolean setWay(int[][] map, int i, int j) {
        //此时走到了迷宫终点
        if (map[6][5] == 2) {
            return true;
        } else {
            if (map[i][j] == 0) { //如果当前这个点还没有走过
                //按照策略 下->右->上->左  走
                map[i][j] = 2;
                if (setWay(map, i + 1, j)) { //下
                    return true;
                } else if (setWay(map, i, j + 1)) { //右
                    return true;
                } else if (setWay(map, i - 1, j)) { //上
                    return true;
                } else { //左
                    return true;
                }
            } else { //map[i][j] != 0, 即只能为1、2。 1表示墙(无法走),2表示已经走过了,所以此时直接返回false
                return false;
            }
        }
    }
 
    //修改找路的策略,改成 上->右->下->左
    public static boolean setWay2(int[][] map, int i, int j) {
        if(map[6][5] == 2) { // 通路已经找到ok
            return true;
        } else {
            if(map[i][j] == 0) { //如果当前这个点还没有走过
                //按照策略 上->右->下->左
                map[i][j] = 2;
                if(setWay2(map, i - 1, j)) { //上
                    return true;
                } else if (setWay2(map, i, j + 1)) { //右
                    return true;
                } else if (setWay2(map, i + 1, j)) { //下
                    return true;
                } else { //左
                    return true;
                }
            } else {
                return false;
            }
        }
    }
 
    public static void main(String[] args) {
        //先创建一个二维数组,模拟迷宫 (地图)
        int[][] map = new int[8][7];
        //使用迷宫中的部分格子表示墙体(置1)
        //第一行和最后一行置为1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //第一列和最后一列置为1
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        //多添加两块墙体
        map[3][1] = 1;
        map[3][2] = 1;
//      map[1][2] = 1;
//		map[2][2] = 1;
        //输出地图查看
        System.out.println("原始迷宫地图为:");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
 
        //使用递归回溯走迷宫
        setWay(map, 1, 1);
//        setWay2(map, 1, 1);
        System.out.println("小球走过,并标识过的地图的情况:");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }
}

Java 데이터 구조 및 알고리즘을 사용하여 재귀 및 역추적을 구현하는 방법

3. 코드 사례 2 - 여덟 여왕 문제

여덟 여왕 문제는 오래되고 유명한 문제이자 역추적 알고리즘의 전형적인 사례입니다. 이 문제는 1848년에 국제적인 체스 선수인 Max Bethel에 의해 제기되었습니다. 8×8 체스 격자에 8명의 여왕을 배치하여 서로 공격할 수 없도록 하십시오. 즉, 두 명의 여왕이 같은 위치에 있을 수 없습니다. 행, 열 또는 대각선으로?

Java 데이터 구조 및 알고리즘을 사용하여 재귀 및 역추적을 구현하는 방법

첫 번째 퀸은 첫 번째 행과 첫 번째 열에 먼저 배치됩니다.

두 번째 퀸을 두 번째 행과 첫 번째 열에 배치한 다음 괜찮은지 확인하고 그렇지 않은 경우 계속해서 두 번째 열과 세 번째 열에 배치한 다음 모든 열을 배치하여 적합한 것을 찾습니다. .

계속해서 세 번째 퀸, 즉 첫 번째와 두 번째 열... 여덟 번째 퀸이 충돌하지 않는 위치에 배치될 수 있을 때까지는 올바른 해결책이라고 볼 수 있습니다.

올바른 솔루션을 얻었을 때 스택이 이전 스택으로 롤백되면 역추적을 시작합니다. 즉, 첫 번째 퀸을 첫 번째 열에 놓고 모든 올바른 솔루션을 얻습니다.

그런 다음 돌아가서 첫 번째 여왕을 두 번째 열에 계속 배치하고 1, 2, 3, 4단계를 반복해서 수행합니다.

package com.szh.recursion;
 
/**
 * 八皇后问题
 */
public class Queue8 {
 
    //定义max表示共有多少个皇后
    private int max = 8;
    //定义数组,保存皇后放置的位置结果,比如 arr = {0, 4, 7, 5, 2, 6, 1, 3}
    int[] array = new int[max];
    //共有多少种解法
    private static int count = 0;
    //共有多少次冲突
    private static int judgeCount = 0;
 
    //编写一个方法,放置第n个皇后
    //特别注意: check 是 每一次递归时,进入到check中都有  for(int i = 0; i < max; i++),因此会有回溯
    private void check(int n) {
        if (n == max) { //n = 8 , 表示这8个皇后已经全部放好了
            print();
            return;
        }
        //依次放入皇后,并判断是否冲突
        for (int i = 0; i < max; i++) {
            //先把当前这个皇后 n , 放到该行的第1列
            array[n] = i;
            //判断当放置第n个皇后到i列时,是否冲突
            if (judge(n)) { // 不冲突
                //接着放n+1个皇后,即开始递归
                check(n + 1);
            }
            //如果冲突,就继续执行 array[n] = i; 即将第n个皇后,放置在本行第i列向后的那一列
        }
    }
 
    //查看当我们放置第n个皇后, 就去检测该皇后是否和前面已经摆放的n-1个皇后冲突
    private boolean judge(int n) {
        //每摆放一个皇后,就循环去和之前摆好的皇后位置相比较,看是否冲突
        for (int i = 0; i < n; i++) {
            //1. array[i] == array[n]  表示判断 第n个皇后是否和前面的n-1个皇后在同一列
            //2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线
            //3. 判断是否在同一行, 没有必要,n 表示第几个皇后,这个值每次都在递增,所以必然不在同一行
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                judgeCount++;
                return false;
            }
        }
        return true;
    }
 
    //打印皇后摆放的具体位置
    private void print() {
        count++;
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
 
    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.printf("一共有%d解法\n", count);
        System.out.printf("一共判断冲突的次数%d次", judgeCount);
    }
}

Java 데이터 구조 및 알고리즘을 사용하여 재귀 및 역추적을 구현하는 방법

사실 코드를 디버깅하면 역추적 과정을 볼 수 있으니 더 말하지 않겠습니다.

위 내용은 Java 데이터 구조 및 알고리즘을 사용하여 재귀 및 역추적을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명
이 기사는 亿速云에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제
고급 Java 프로젝트 관리, 구축 자동화 및 종속성 해상도에 Maven 또는 Gradle을 어떻게 사용합니까?고급 Java 프로젝트 관리, 구축 자동화 및 종속성 해상도에 Maven 또는 Gradle을 어떻게 사용합니까?Mar 17, 2025 pm 05:46 PM

이 기사에서는 Java 프로젝트 관리, 구축 자동화 및 종속성 해상도에 Maven 및 Gradle을 사용하여 접근 방식과 최적화 전략을 비교합니다.

적절한 버전 및 종속성 관리로 Custom Java 라이브러리 (JAR Files)를 작성하고 사용하려면 어떻게해야합니까?적절한 버전 및 종속성 관리로 Custom Java 라이브러리 (JAR Files)를 작성하고 사용하려면 어떻게해야합니까?Mar 17, 2025 pm 05:45 PM

이 기사에서는 Maven 및 Gradle과 같은 도구를 사용하여 적절한 버전 및 종속성 관리로 사용자 정의 Java 라이브러리 (JAR Files)를 작성하고 사용하는 것에 대해 설명합니다.

카페인 또는 구아바 캐시와 같은 라이브러리를 사용하여 자바 애플리케이션에서 다단계 캐싱을 구현하려면 어떻게해야합니까?카페인 또는 구아바 캐시와 같은 라이브러리를 사용하여 자바 애플리케이션에서 다단계 캐싱을 구현하려면 어떻게해야합니까?Mar 17, 2025 pm 05:44 PM

이 기사는 카페인 및 구아바 캐시를 사용하여 자바에서 다단계 캐싱을 구현하여 응용 프로그램 성능을 향상시키는 것에 대해 설명합니다. 구성 및 퇴거 정책 관리 Best Pra와 함께 설정, 통합 및 성능 이점을 다룹니다.

캐싱 및 게으른 하중과 같은 고급 기능을 사용하여 객체 관계 매핑에 JPA (Java Persistence API)를 어떻게 사용하려면 어떻게해야합니까?캐싱 및 게으른 하중과 같은 고급 기능을 사용하여 객체 관계 매핑에 JPA (Java Persistence API)를 어떻게 사용하려면 어떻게해야합니까?Mar 17, 2025 pm 05:43 PM

이 기사는 캐싱 및 게으른 하중과 같은 고급 기능을 사용하여 객체 관계 매핑에 JPA를 사용하는 것에 대해 설명합니다. 잠재적 인 함정을 강조하면서 성능을 최적화하기위한 설정, 엔티티 매핑 및 모범 사례를 다룹니다. [159 문자]

Java의 클래스로드 메커니즘은 다른 클래스 로더 및 대표 모델을 포함하여 어떻게 작동합니까?Java의 클래스로드 메커니즘은 다른 클래스 로더 및 대표 모델을 포함하여 어떻게 작동합니까?Mar 17, 2025 pm 05:35 PM

Java의 클래스 로딩에는 부트 스트랩, 확장 및 응용 프로그램 클래스 로더가있는 계층 적 시스템을 사용하여 클래스로드, 링크 및 초기화 클래스가 포함됩니다. 학부모 위임 모델은 핵심 클래스가 먼저로드되어 사용자 정의 클래스 LOA에 영향을 미치도록합니다.

See all articles

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

인기 기사

R.E.P.O. 에너지 결정과 그들이하는 일 (노란색 크리스탈)
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 최고의 그래픽 설정
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 아무도들을 수없는 경우 오디오를 수정하는 방법
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25 : Myrise에서 모든 것을 잠금 해제하는 방법
4 몇 주 전By尊渡假赌尊渡假赌尊渡假赌

뜨거운 도구

SublimeText3 Linux 새 버전

SublimeText3 Linux 새 버전

SublimeText3 Linux 최신 버전

Dreamweaver Mac版

Dreamweaver Mac版

시각적 웹 개발 도구

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

mPDF

mPDF

mPDF는 UTF-8로 인코딩된 HTML에서 PDF 파일을 생성할 수 있는 PHP 라이브러리입니다. 원저자인 Ian Back은 자신의 웹 사이트에서 "즉시" PDF 파일을 출력하고 다양한 언어를 처리하기 위해 mPDF를 작성했습니다. HTML2FPDF와 같은 원본 스크립트보다 유니코드 글꼴을 사용할 때 속도가 느리고 더 큰 파일을 생성하지만 CSS 스타일 등을 지원하고 많은 개선 사항이 있습니다. RTL(아랍어, 히브리어), CJK(중국어, 일본어, 한국어)를 포함한 거의 모든 언어를 지원합니다. 중첩된 블록 수준 요소(예: P, DIV)를 지원합니다.

VSCode Windows 64비트 다운로드

VSCode Windows 64비트 다운로드

Microsoft에서 출시한 강력한 무료 IDE 편집기