하노이 탑 알고리즘: Python, C++ 암호

하노이타워란?

하노이 탑은 1883개의 막대와 수많은 원판이 서로 겹쳐진 수학적 퍼즐입니다. XNUMX년 프랑스 수학자 에두아르 루카스(Edouard Lucas)가 소개한 브라흐마 타워(Tower of Brahma) 또는 루카스 타워(Lucas tower)라고도 알려져 있습니다. 이 퍼즐은 세 개의 막대 사이에서 금 원반을 움직이는 전설을 바탕으로 합니다.

이 퍼즐에는 세 개의 막대와 다양한 개수의 디스크가 쌓여 있습니다. 그 막대는 순환 타워로 설계되었습니다. 따라서 직경이 큰 원판은 아래쪽에 쌓이고, 작은 원판은 위에 쌓입니다.

처음에는 세 개의 못이나 막대가 제공됩니다. 그리고 그 중 하나(예에 표시된 A)에는 모든 디스크가 쌓여 있습니다. 우리는 몇 가지 특정 규칙을 준수하여 전체 디스크 스택을 한 막대(A)에서 다른 막대(C)로 이동하는 것을 목표로 합니다.

퍼즐의 초기 설정은 다음과 같습니다.

그리고 이것이 최종 목표입니다-

하노이 타워의 규칙

하노이 타워의 몇 가지 필수 규칙은 다음과 같습니다.

이 퍼즐의 초기 상태에서는 모든 디스크가 막대 XNUMX에 쌓이게 됩니다.
최종 상태는 막대 XNUMX의 모든 디스크가 막대 XNUMX 또는 막대 XNUMX에 쌓이는 것입니다.
우리는 언제든지 디스크상의 막대를 한 막대에서 다른 막대로 이동할 수 있습니다.
막대에서 가장 위쪽의 디스크만 움직일 수 있습니다.
디스크는 더 작은 다른 디스크 위에 놓일 수 없습니다.

원래 전설은 64개의 디스크를 옮기는 것에 관한 것이었습니다. 사제들은 규칙에 따라 한 번에 한 개의 디스크를 옮길 수 있었습니다. 전설에 따르면, 그들이 그 행위를 완수할 수 있다면 세상이 끝날 것이라는 예언이 있었습니다. 시간 복잡도 섹션에서는 n개의 디스크로 구성된 하노이탑 설정에 2^n – 1회 이동이 필요하다는 것을 보여드리겠습니다.

따라서 사제들이 디스크를 움직이는 데 1초가 필요하다면 퍼즐을 푸는 데 필요한 총 시간은 2^64 - 1초, 즉 584,942,417,356년 26일 7시간 15초가 될 것입니다.

하노이 타워 알고리즘

하노이 타워를 해결하는 일반적인 방법 중 하나는 재귀 알고리즘입니다. 먼저 두 개의 막대 또는 말뚝을 소스와 대상으로 결정해야 하며, 예비 말뚝은 보조 또는 도우미가 될 것입니다.

하노이 타워 퍼즐을 푸는 단계는 다음과 같습니다.

소스 페그에서 상단 n-1개의 디스크를 헬퍼 페그로 이동합니다.
그런 다음 소스 페그에서 n번째 디스크를 대상 페그로 이동합니다.
마지막으로 나머지 n-1개의 디스크를 도우미 페그에서 대상 페그로 옮깁니다.

주의 사항: 단일 디스크가 있는 경우 소스에서 대상으로 직접 이동할 수 있습니다.

하노이탑 퍼즐 푸는 방법

세 개의 디스크에 대한 알고리즘을 설명하고 페그 A를 소스로, 페그 B를 도우미로, 페그 C를 대상으로 생각해 보겠습니다.

단계 1) 처음에는 모든 디스크가 페그 A에 쌓입니다.

이 단계에서:

출처=페그A
목적지 = 페그 C
도우미 = 페그 B

이제 상위 n-1개 디스크를 소스에서 도우미로 이동해야 합니다.

참고 : 한 번에 하나의 디스크만 이동할 수 있지만 문제는 3디스크 문제에서 재귀 호출인 2디스크 문제로 전환됩니다.

단계 2) 페그 A에서 재귀 호출을 호출하고 대상이 페그 B이므로 페그 C를 도우미로 사용합니다.

두 개의 디스크에 대한 동일한 하노이 타워 문제의 경우 다시 XNUMX단계에 있습니다.

이제 n-1개 또는 하나의 디스크를 소스에서 도우미로 이동하고 가장 작은 디스크를 페그 A에서 페그 C로 이동해야 합니다.

이 단계에서:

출처=페그A
목적지 = 페그 B
도우미 = 페그 C

단계 3) 그런 다음 우리 알고리즘에 따라 n번째 또는 두 번째 디스크 요구 사항이 대상 또는 페그 B로 전송되어야 합니다.

이 단계에서:

출처=페그A
목적지 = 페그 B
도우미 = 페그 C

단계 4) 이제 알고리즘의 세 번째 단계에 따라 n-1개의 디스크 또는 디스크 XNUMX을 도우미 또는 페그 C에서 대상 또는 페그 B로 이동합니다.

이 단계에서:

출처=페그A
목적지 = 페그 B
도우미 = 페그 C

단계 5) 재귀 호출을 완료한 후 알고리즘의 첫 번째 단계가 되면 이전 설정으로 돌아갑니다.

단계 6) 이제 두 번째 단계에서는 소스를 대상으로 이동하여 디스크 3을 페그 A에서 페그 C로 이동합니다.

이 단계에서:

출처=페그A
목적지 = 페그 C
도우미 = 페그 B

단계 7) 이제 우리는 그것을 볼 수 있습니다

d는 나머지 디스크를 도우미(페그 B)에서 대상(페그 C)으로 이동하는 것입니다. 이 경우 초기 소스 또는 페그 A를 도우미로 사용합니다.

단계 8) 두 개의 디스크를 동시에 이동할 수 없으므로 디스크 1에 대한 재귀 호출을 호출합니다. 마지막 단계와 우리의 연산, 이 단계의 대상은 페그 A입니다.

이 단계에서:

출처=페그B
목적지 = 페그 A
도우미 = 페그 C

단계 9) 이제 재귀 호출이 완료되었습니다. 그런 다음 디스크 2를 소스에서 대상으로 이동합니다.

이 단계에서:

출처=페그B
목적지 = 페그 C
도우미 = 페그 A

단계 10) 그런 다음 나머지 n-1 또는 디스크 1을 도우미에서 대상으로 이동합니다.

이 단계에서:

출처=페그A
목적지 = 페그 C
도우미 = 페그 B

하노이 타워에 대한 의사 코드

START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
  		IF disk == 1, THEN
      			move disk from source to dest             
   		ELSE
     			Tower_Of_Hanoi (disk - 1, source, helper, dest)     
      			move disk from source to dest          
      			Tower_Of_Hanoi (disk - 1, helper, dest, source)     
   		END IF   
END Procedure

프로그램 코드 C++

#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
  if (num == 1) {
    cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
    return;
  }
  tower_of_hanoi(num - 1, source, helper, dest);
  cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
  tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
  int num;
  cin >> num;
  printf("The sequence of moves :\n");
  tower_of_hanoi(num, "I", "III", "II");
  return 0;
}

산출

3
The sequence of moves :
Move disk 1 from tower I to tower III
Move disk 2 from tower I to tower II
Move disk 1 from tower III to tower II
Move disk 3 from tower I to tower III
Move disk 1 from tower II to tower I
Move disk 2 from tower II to tower III
Move disk 1 from tower I to tower III

프로그램 코드 Python

def tower_of_hanoi(n, source, destination, helper):
	if n==1:
		print ("Move disk 1 from peg", source," to peg", destination)
		return
	tower_of_hanoi(n-1, source, helper, destination)
	print ("Move disk",n," from peg", source," to peg", destination)
	tower_of_hanoi(n-1, helper, destination, source)		
# n = number of disks
n = 3
tower_of_hanoi(n,' A','B','C')

출력:

Move disk 1 from peg A to peg B
Move disk 2 from peg A to peg C
Move disk 1 from peg B to peg C
Move disk 3 from peg A to peg B
Move disk 1 from peg C to peg A
Move disk 2 from peg C to peg B
Move disk 1 from peg A to peg B

하노이의 탑의 복잡성

하노이탑의 시간 및 공간 복잡도는 다음과 같습니다.

1) 시간 복잡도:

알고리즘을 다시 살펴보면 (n-1) 디스크에 대한 재귀 호출을 두 번 도입하고 있음을 알 수 있습니다. (n-1) 디스크에 대한 재귀 호출은 이동할 디스크가 하나만 나올 때까지 다른 ((n-1)-1) 등으로 분할될 수 있습니다.

세 개의 디스크의 경우-

디스크 3은 디스크 XNUMX에 대한 재귀 함수를 두 번 호출합니다.
디스크 2는 디스크 XNUMX에 대한 재귀 함수를 두 번 호출합니다.
디스크 1은 일정한 시간 내에 이동할 수 있으며, 디스크 XNUMX개를 해결하는 데는 시간이 걸립니다.

= 2*(두 개의 디스크를 푸는 데 걸리는 시간) + 상수 디스크 3을 이동하는 데 걸리는 시간

= 2*(2*한 디스크를 푸는 데 걸리는 시간 + 상수 디스크 2를 이동하는 데 걸리는 시간) + 상수 디스크 3을 이동하는 데 걸리는 시간

= (2*2) (디스크 1을 이동하는 데 걸리는 상수 시간) + 2*디스크 2를 이동하는 데 걸리는 상수 시간 + 디스크 3을 이동하는 데 걸리는 상수 시간

n개 디스크의 경우 다음과 같이 쓸 수 있습니다.

(2^n-1* 디스크 1 + 2를 이동하는 데 걸리는 일정한 시간^n-2 * 디스크 2를 이동하는 데 걸리는 일정한 시간 + ....

이 기하학적 진행은 O(2^n-1) 또는 O (2ⁿ), 이는 기하급수적이다.

2) 공간 복잡도

하노이탑의 공간 복잡도는 0(n)입니다. 그 이유는 우리가 접시의 순서를 저장해야 하기 때문입니다. 재귀를 사용할 때는 스택을 사용합니다. 그리고 스택의 최대 크기는 "n"이 될 수 있습니다. 그래서 공간 복잡도는 O(n)이 됩니다.

하노이타워란?

하노이 타워의 규칙

하노이 타워 알고리즘

하노이탑 퍼즐 푸는 방법

관련 기사

하노이 타워에 대한 의사 코드

프로그램 코드 C++

프로그램 코드 Python

하노이의 탑의 복잡성

뉴스레터 신청하기