Java를 사용하여 하노이 타워 문제를 분석하는 방법

1. 하노이 탑 문제의 근원

하노이 탑이라고도 알려진 하노이 탑은 고대 인도 전설에 유래하는 교육용 장난감입니다. 브라흐마는 세상을 창조했을 때 세 개의 다이아몬드 기둥을 만들었고, 한 기둥에는 64개의 금 원반이 아래에서 위로 크기대로 쌓여 있었습니다. 브라흐마는 브라만에게 디스크를 바닥부터 크기 순서대로 다른 기둥에 재배치하라고 명령했습니다. 그리고 작은 원반에서는 원반을 확대할 수 없으며 세 개의 기둥 사이에서 한 번에 하나의 원반만 이동할 수 있다고 규정되어 있습니다

2. 문제 분석

간단한 질문으로 시작

생각만 하면 됩니다. 접시 64개, 어려울 수 있습니다. 아래와 같이 접시 1개부터 시작할 수 있습니다.

접시 1개

A -> C

접시 1개만 있으면 A를 바로 접시에 놓을 수 있습니다. 기둥 접시가 C 기둥으로 이동되었습니다

한 번 이동해야 합니다

두 개의 접시

두 개의 접시가 있는 경우 다음과 같은 방법으로도 얻을 수 있습니다.

A -> C B-> C

3번 이동해야 합니다

1. A -> B

2.

3개 접시

A -> B C -> C B -> A B -> C

총 7번의 이동이 필요합니다. .A ->C

2.A ->B

3.C ->A ->

6. B -> 알았어 3개의 접시 이동

4개의 접시가 있으면 이 문제는 실제로 매우 복잡합니다

Rule derivation

1개 접시 1번 이동

2개 접시 3번 이동

접시 3개를 7번 이동하세요

......

N개 접시를 2^N - 1번 이동

그러면 64개의 접시를 2^64번 - 1번 이동해야 합니다

3. 문제 해결

우리는 할 수 있습니다. 재귀를 통해 이 문제를 해결하고 올바른 이동 방법을 얻으세요.

N개의 접시가 있으면 어떻게 이동하나요?

전체 아이디어

먼저 C열의 도움을 받아 N - 1개의 접시를 A열에서 B열로 이동한 다음 나머지 접시를 A열에서 C열로 이동한 다음 N - 1개의 접시를 B열로 이동할 수 있습니다. 플레이트는 A기둥의 도움으로 C기둥으로 이동하여 모든 기둥의 이동이 완료됩니다. (중간의 구체적인 이동 과정은 당분간 논의하지 않겠습니다.)

코드 업로드

public static void hanoi(int num, String src, String help, String dest) {
    if (num == 1) {     // 只有一个盘子的时候直接移动
        System.out.print(src + "->" + dest + "  ");  // 将一个盘子从源柱子挪到目标柱子
    } else {
        hanoi(num - 1, src, dest, help);   // 将n - 1个盘子从源柱子借助目标柱子挪到辅助柱子
        System.out.print(src + "->" + dest + "  ");  // 将一个盘子从源柱子挪到目标柱子
        hanoi(num - 1, help, src, dest);  // 将辅助柱子上n - 1个盘子借助源柱子挪到目标柱子
    }
}
public static void main(String[] args) {
    hanoi(3, "A", "B", "C");
}

이 코드에서 src가 소스입니다 기둥, help는 보조 기둥이고 dest는 대상 기둥입니다.

이것은 양방향 재귀입니다

작업 결과:

이로써 판의 움직임이 성공적으로 완료되었습니다

4. 브라마의 임무

64개의 접시를 옮기는 데 시간이 얼마나 걸립니까?

브라만은 매우 똑똑해서 생각하지 않고도 올바른 이동 방법을 직접 알 수 있다고 가정합니다. 접시를 옮기고 계속 움직이는 데 1초가 걸립니다.

2^64 - 1초를 1년으로 환산하면 약 584942417355년(5849억4200만년) 정도 되는데, 지구는 겨우 45억년 동안 존재했고, 태양계의 예상 수명은 수백억년이라고 한다. 연령. 정말 5,849억 4,200만 년이 지났습니다. 태양계와 은하수는 말할 것도 없고, 적어도 바티칸 타워, 사원 등 지구상의 모든 생명체가 멸종된 지 오래입니다.

관련 예언

이것이 완성되면 우주가 순식간에 멸망할 것이라는 예언이 있습니다. 어떤 사람들은 브라민들이 여전히 디스크를 계속 움직이고 있다고 믿고 있습니다

컴퓨터가 64개의 판을 옮기는 데 얼마나 걸리나요?

내 컴퓨터의 핵심주파수는 2.90GHz로 초당 29억번의 연산을 하므로 2^64-1번 이동하는데 걸리는 시간은 약 201년이다

위 내용은 Java를 사용하여 하노이 타워 문제를 분석하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!