TIL) 1914 하노이의 탑

🎈재귀함수 규칙찾기

💈 원반의 이동 횟수만 고려하기

규칙 찾는데 오랜 시간이 걸렸다😣
원반이 이동하는 위치는 고려하지 않고 횟수만 생각해서 규칙을 찾기 시작했다.

hanoi(1) = 1
hanoi(2) = hanoi(1) + 1 + hanoi(1)
hanoi(3) = hanoi(2) + 1 + hanoi(2)
hanoi(4) = hanoi(3) + 1 + hanoi(3)
hanoi(5) = hanoi(4) + 1 + hanoi(4)
...
hanoi(n) = hanoi(n-1) + 1 + hanoi(n-1)

재귀함수를 상향식으로 분석할 때 사용하는 점화식을 먼저 찾은 후 코드로 변환하면

def hanoi_count(no):

    if no > 1 :
        return hanoi(no-1) * 2 + 1
    else:
        return 1

이렇게 원반을 움직인 횟수가 나오는 알고리즘을 완성했다.

💈 원반이 이동하는 위치 고려하기

이제 원반의 시작점(from), 목표점(to), 나머지(other)를 함께 고려해야한다.

1. 먼저, 마지막 원반을 제외한 나머지 원반이 시작점(from)에서 나머지(other)로 이동
2. 마지막 원반이 시작점(from)에서 목표점(to)으로 이동
3. 나머지 원반을 나머지(other)에서 목표점(to)로 이동

이러한 규칙을 코드로 변환하면

def hanoi_move(no, from, to, other):
    
    if no > 1:
        move(no -1, from, other)
    
    print(str(x) +" "+str(y))
    
    if no > 1:
        move(no - 1, other, to)

👽 문제상황

점화식을 가지고 그대로 코드로 옮겼을 때 문제가 발생했다.

잘못된 코드

def hanoi_count(no,from,to, other):
    if no > 1 :
        return hanoi(no-1, from, other, to) + 1 + hanoi(no-1, other, to, from)
    else:
        return 1
    print(str(from) +" "+str(to))

이렇게 코드를 짜면 횟수는 맞지만 이동하는 막대기의 번호의 순서는 제대로 출력되지 않는다.
이동하는 원반이 어디에서 어디로 이동하는지 까지 규칙을 찾아야한다.