하노이의 탑

% 수정예정

 

 

********************************************************************************************************

INDEX

** 하노이의 탑이란?

** 코딩 구현 

********************************************************************************************************

** 하노이의 탑이란?

> 이렇게 생긴 게임

> 한번에 하나씩만 옮길 수 있고, 큰 원판은 작은 원판보다 밑에있어야 한다  

 

 

 

** 코딩 구현

** 재귀 함수로 구현 가능한 로직인 이유 

 

1개를 옮길 때 : 출 -> 목

2개를 옮길 때 : 출 -> 경 , 출-> 목, 경 -> 목 

3개를 옮길 때, 2개를 목적지가 아닌 경유지로 옮기고 ( 인자 순서 바뀌어서 재귀 호출 ).  나머지 하나를 출->목

                       그 다음은 경유지에서 목적지로 나머지 2개를 옮기는 재귀함수 호출 

 

--------------------------------------------------------------------------------------------------------

def move_d(disks,start,end,via) , 모든 이동은 디스크 개수를 {} 기둥에서 {} 기둥으로 출력하는 상황을 말한다

1개를 옮기는 상황  (1,1,2,3), 목적 기둥은 2.

# 1개를 출발기둥에서 목적 기둥으로 이동함 (1-편의상 0, 1-start,2-end,3-via)

if disks ==1: ~~~ 만약 디스크가 한개라면

print(디스크 목적지{end} 이동 완료 ! )  현재 end는 end.

 

--------------------------------------------------------------------------------------------------------

2개를 옮기는 상황에서 일반화를 하면 (2,1,2,3)

기둥1에서 3으로, 1에서 2로, 3에서 2로 옮기는 상황이 가능하다. 

-> start =1 to = 2 via =3

---------------------------------------------------------------------------------------------------------

(3,1,2,3) 

 

if disks ==1: ~~~ 만약 디스크가 한개라면 

print(디스크 목적지{end} 이동 완료 ! ) 이때 end 인자는? 

 

# 1개를 1 출발 기둥에서 3 경유 기둥으로 이동함

else: ( 디스크 개수가 1개가 아닌 상황 )
move_d(disks -1 , start, via, end)        (3,1,2,3 )-> (2,1,3,2) 

                                출발  도착 경유         

 

# 1개를 1 출발 기둥에서 2 목적 기둥으로 이동함 

print(start에서 end로 disc개수(-1됨) 이동)  (2,1,3,2) 출력 start 인자 1 에서 end 인자 3으로 디스크 2개 이동

 

# 1개를 3 경유 기둥에서 2 목적 기둥으로 이동함  

move_d(disks-1, via, end, start)  (1,2,3,1) via 인자 1에서 end인자 3으로 (경유에서 목적으로) 디스크 1개 이동

-------------------------------------------------------------------------------------------

 

3개를 옮기는 상황은 ( 2개를 옮기는 함수 * 1 + 하나를 옮기는 함수 + 2개를 다시 옮기는 함수 * 1 ) 

# 디스크 2개를 1에서 3 경유 기동으로 이동, 2개를 옮기는 상황  

# 디스크 1개를 1에서 2 목적 기둥으로 이동

# 디스크 2개를 경유기둥(3)에서 2 목적 기둥으로 이동, 2개를 옮기는 상황 

4개 역시 

3개를 옮기는 상황 ( 2개를 옮기고 1개를 옮긴 후 2개를 옮기는 상황 ) 

+

1개를 옮기는 상황

으로 구성될 수 있다.

2개 + 2개를 옮기는 경우는 게임 특성상 불가능하다. 

 

따라서 n개의 원판을 옮길때, n-1개를 옮기는......1개를 옮기는 상황으로 generalization이 가능한 구현이다. 

 

** 기둥 숫자 대신에 원래 이름을 써서 흐름을 봐보자 .. 헷갈린다 너무

** 구조와 재귀함수의 특성을 생각하자 

1개를 옮길때 : 목적지로 

2개를 옮길때 : 1(n-1=1)남은 기둥으로 하나, 목적지로 하나, 1(n-1=1)나머지도 목적지로 

3개를 옮길때 : 2(n-1=2)개를 남은 기둥으로, 목적지로 하나, 2(n-1=2)개를 남은 기둥으로 

4개를 옮길때 : 3(n-1=3)개를 남은 기둥으로(재귀호출), 목적지로 하나, 3(n-1=3)개를 남은 기둥으로(재귀호출)

즉 n-1개를 남은 기둥으로 옮기고, 목적지로 하나를 옮기고, n-1개를 다시 기둥으로 옮기는 구조 

 

코드 흐름은 

if 조건문 통과 -> 통과 

else 조건문 통과 -> 재귀함수 실행 -> if 조건문 통과 

                                                      -> Else 조건문 통과 -> 재귀함수 실행 -> ...

                                                                                           프린트 및 재귀함수 실행

                                프린트 실행

                               재귀함수 실행