자바 프로그래밍 과제 : 하노이 더미의 재발견

이 과제는 프로그래밍 능력을 사용하여 디스크 수를 고려하여 Towers of Hanoi 퍼즐을 해결하는 데 필요한 단계를 인쇄하는 Java 프로그램을 작성하는 데 도움이됩니다.

하노이 타워 (Tower of Hanoi) 는 세 개의 수직 페그와 다양한 지름의 디스크로 구성된 고전적인 논리 퍼즐입니다. 각 디스크에는 가운데에 구멍이있어 디스크를 못으로 밀어 넣을 수 있습니다.

수수께끼는 나무못 중 하나에 쌓인 모든 디스크로 시작합니다. 가장 큰 디스크는 맨 아래에 있고 가장 작은 디스크는 맨 위에 있습니다. 퍼즐의 목적은 두 개의 단순한 규칙에 따라 디스크 뭉치를 다른 쐐기 중 하나로 이동시키는 것입니다: (1) 한 번에 하나의 디스크 만 이동할 수 있고, (2) 더 작은 것의 꼭대기.

다음 그림은 3 개의 디스크 스택에 대한 솔루션을 보여줍니다.

디스크 1을 Peg 3에서 Peg 2로 이동합니다.
디스크 1을 Peg 2에서 Peg 2로 이동합니다.
디스크 1을 Peg 3에서 Peg 2로 이동합니다.
디스크 3을 Peg 1에서 Peg 3으로 이동합니다.
디스크 1을 Peg 2에서 Peg 1로 이동합니다.
디스크 2를 Peg 2에서 Peg 3으로 이동합니다.
디스크 1을 Peg 1에서 Peg 3으로 이동합니다.

이 7 단계가 끝나면 디스크 스택이 Peg 3에있게됩니다.

Three of Towers of Hanoi puzzle for three 디스크.

시작 위치에 디스크를 추가하기 시작하면 퍼즐이 재미 있습니다. 3 개의 디스크를 사용하여 퍼즐을 풀려면 7 개의 동작 만 있으면됩니다. 4 개의 디스크로 15 개의 이동이 필요합니다. 5 개의 디스크가 있으면 31 개의 움직임이 필요합니다. 여섯 개의 디스크에 64 개의 이동이 필요합니다.

흥미 진진한 전설은 퍼즐과 관련이 있습니다. 하노이의 한 사원에서 스님들은 지구가 창조 된 이래로 64 개의 디스크가있는 하노이 타워 퍼즐에서 작업했습니다. 그들이 끝나면 세상은 끝날 것입니다. 다행히도, 우리는 기다릴 시간이 오래갑니다. 스님들이 초당 디스크 하나를 움직일 수 있다면, 퍼즐을 끝내기 전에 또 다른 580 억년이 걸릴 것입니다. 당신의 도전 과제는 간단합니다: 디스크 개수를 고려해 Towers of Hanoi 퍼즐을 해결하는 데 필요한 단계를 인쇄 할 Java 프로그램을 작성하십시오. 프로그램은 먼저 사용자에게 디스크 수를 프롬프트해야합니다. 그런 다음 각 행을 하나씩 표시해야합니다.각 단계는 디스크를 이동시킬 페그와 디스크를 이동할 페그를 표시해야합니다. 단계에도 순차적으로 번호가 매겨 져야합니다. 작업이 끝나면 프로그램을 반복하여 사용자에게 디스크 수를 다시 묻습니다. 프로그램은 사용자가 0을 입력하면 종료되어야합니다. ^{다음은 프로그램에서 생성해야하는 콘솔 출력의 샘플입니다.} 디스크 수는 얼마입니까? (0에서 종료) 399: 1에서 3 2: 1에서 2 3: 3에서 2 4: 1에서 3 5: 2에서 1 6: 2에서 3 7: 1에서 3 얼마나 많은 디스크 ? (0에서 끝까지) ⁰ 이 과제를 해결하기위한 유일한 요구 사항은 솔루션에서 재귀 프로그래밍을 사용해야한다는 것입니다. 즉, 솔루션에는 퍼즐을 해결하기 위해 자신을 호출하는 메서드가 포함되어야합니다.

재귀 프로그래밍은 어려울 수 있으므로 여기에이 퍼즐의 해결책에 대한 몇 가지 힌트가 있습니다.

퍼즐은 세 개의 못으로 구성됩니다. 그 중 하나에는 디스크의 시작 스택이 들어 있습니다. 이 페그를

소스 페그

라고 부르십시오. 나머지 두 개의 페그 중 하나는 디스크 더미를 이동하려는 페그입니다. 이 페그를

목표 페그 라고 부르십시오. 세 번째 말뚝은 중간 말뚝으로 사용하여 일시적으로 디스크를 옮길 때 사용할 수 있습니다. 이 페그를 예비 페그 라고 부르십시오.

재귀 적 메서드는 세 개의 매개 변수, 즉 이동할 디스크 수, 소스 페그 및 대상 페그를 받아 들여야합니다. 페그를 나타 내기 위해 정수 값 1, 2 및 3을 사용하십시오.

소스 페그에서 대상 페그로 디스크 더미를 이동하려면 다음 세 단계가 필요합니다.

스택의 모든 디스크를 맨 아래 디스크를 제외하고 예비 페그. 원래 스택에서 가장 큰 디스크를 대상 페그로 이동합니다. 1 단계에서 이동 한 스택을 예비 페그에서 대상 페그로 이동하십시오. 물론 퍼즐 규칙을 사용하면 한 번에 하나의 디스크 만 이동할 수 있으므로 여기에 제시된 절차의 1 단계와 3 단계는 스택을 집어 들고 옮기는 것만으로는 불가능합니다. 재귀가 들어오는 지점입니다. 1 단계와 3 단계에서는 메서드를 재귀 적으로 호출 할 때마다 이동할 디스크를 하나씩 지정하고 이전 대상 페그를 예비 페그로 사용할 때마다 호출합니다. 왜 재귀 적 방법으로 예비 페그를 인수로 받아 들일 필요가 없는지 궁금하십니까? 소스 및 대상 못을 주면 쉽게 계산할 수 있기 때문입니다. 1, 2, 3으로 번호가 매겨진 3 개의 못이 있기 때문에, 3 개의 못의 합은 6 (1 + 2 + 3)입니다. 소스와 타겟 페그가 주어지면 소스 페그와 타겟 페그를 6에서 뺀 예비 페그를 계산할 수 있습니다. 예를 들어 소스 페그가 1이고 타겟 페그가 3 인 경우 예비 페그는 2이어야합니다. 6 - 3 - 1 = 2. 해당 솔루션의 경우
Java Jam-in-One for Dummies,
4th Edition 제품 페이지의 다운로드 탭으로 이동하십시오.
1. 행운을 빌어 요!