Day45. 알고리즘 (6)

재귀 - 실습

• 재귀 알고리즘(실습)

• 실습
  
  
  재귀 알고리즘을 이용한 최대 공약수 계산
  
  
  ㆍ유클리트 호제법
  ㆍㆍ두 자연수 n1, n2에 대하여(n1 > n2) n1를 n2로 나눈 나머지를 r이라고 할 때,
  ㆍㆍn1과 n2의 최대공약수는 n2와 r의 최대공약수와 같다

# 재귀함수를 사용하지 않은 것!

def greatestCommonDevide(n1, n2):

    maxNum = 0
    for i in range(1, (n1 + 1)):
        if n1 % i == 0 and n2 % i == 0:
            maxNum = i

    return maxNum

print(f'greatestCommonDevide(82, 32) : {greatestCommonDevide(82, 32)}')
print(f'greatestCommonDevide(96, 40) : {greatestCommonDevide(96, 40)}')

# 재귀함수를 사용한 것!
def gcd(n1, n2):

    if n1 % n2 == 0:
        return n2

    else:
        return gcd(n2, n1 % n2) # 다시 호출 할 때 n2를 r로 나누는 조건으로 부른다!

print(f'gcd(82, 32) : {gcd(82, 32)}')
print(f'gcd(96, 40) : {gcd(96, 40)}')

하노이의 탑 - 이론

• 하노이의 탑

• 원판을 옮기자!
  
  
  퍼즐 게임의 일종으로 세 개의 기둥을 이용해서 원판을 다른 기둥으로 옮기면 되고, 제약 조건은 다음과 같다!
  
  
  ㆍ한 번에 한개의 원판만 옮길 수 있다!
  ㆍ큰 원판이 작은 원판 위에 있어서는 안 된다!

하노이의 탑 - 실습

• 하노이의 탑(실습)

자주 복습할 것!

• 재귀함수를 사용해야 한다!
  
  
  원판을 옮기자!

def moveDisc(discCnt, fromBar, toBar, viaBar):  # 원판 개수, 출발 기둥, 도착 기둥, 경유 기둥
    if discCnt == 1:
        print(f'{discCnt}disc를 {fromBar}에서 {toBar}(으)로 이동!')

    else:
        # (discCnt-1)개들을 경유 기둥으로 이동
        moveDisc(discCnt - 1, fromBar, viaBar, toBar)   # 얘들이 경유지로 가는게 중요!

        # discNo를 목적 기둥으로 이동
        print(f'{discCnt}disc를 {fromBar}에서 {toBar}(으)로 이동!')

        # (discCnt-1)개들을 도착 기둥으로 이동
        moveDisc(discCnt - 1, viaBar, toBar, fromBar)

moveDisc(3, 1, 3, 2)

(3, 1, 3, 2) 2, 1, 2, 3


(2, 1, 2, 3) 1, 1, 3, 2 -> 2disc를 1에서 2으로 이동!(2)


(1, 1, 3, 2) -> 1disc를 1에서 3으로 이동!(1) 출력후 다시 위로!


(2, 1, 2, 3) 1, 3, 2, 1


(1, 3, 2, 1) -> 1disc를 3에서 2으로 이동!


(3, 1, 3, 2)

복습이 매우매우매우 필요하다!