하노이 탑의 경로와 이동 횟수를 알기 위해선 시작점과 끝점 뿐만 아니라 어디를 거쳐서 이동하는지도 고려해야한다. n
번 원판이 가장 아래 있기 때문에 이 원판을 옮기기 위해선 그 위에 있는 n-1
개의 원판을 다른 곳으로 이동 시켜야 한다.
a
(파이썬에서 from
이미 모듈을 가져오는데 사용되므로 a
로 변수명을 정하였다.) by
to
알고리즘은 다음과 같다.
n-1
개의 원판을 by
에 옮긴다.n
번째 원판을 to
로 옮긴다.by
에 있는 n-1
개의 원판을 to
로 옮긴다.이 알고리즘을 바탕으로 다음과 같이 코드를 작성해 볼 수 있다.
def hanoi (a ,by,to,n):
if n==1:
print("1: "+a+" --> "+to)
return 1
ans=0
ans+=hanoi(a,to,by,n-1)
ans+=1
print(str(n)+": "+a + " --> "+ to)
ans+=hanoi(by,a,to,n-1)
return ans
print(hanoi("1","2","3",3))
[Python] N개의 수의 최대 공약수, 최소 공배수 구하기 (0) | 2020.03.25 |
---|