[Python][알고리즘] 재귀 알고리즘 - 응용

 

 

 

1. Combination 함수 만들기 - 재귀적 알고리즘 미활용

   (math 라이브러리의 factorial 활용)

from math import factorial as f

def combi(n,m):
    return f(n)/(f(m)*f(n-m))

result = combi(4,2)
print(result)
# (4*3*2*1)/{(2*1)(2*1)} = 6

 

 

 

 

2. Combination 함수 만들기 - 재귀적 알고리즘 활용

def combi2(n, m):
    if n == m:
        return 1
    else:
        return combi2(n-1,m)*n/(n-m)

 

m-1 C n = ( (m-1)! ) / ( n! * (m-n-1)! )

m C n = ( m! ) / ( n! * (m-n)! )

         = ( m * (m-1)! ) / ( n! * (m-n-1)! * (m-n) )

         = m / (m-n) * m-1 C n

 

임을 활용하여 재귀적 알고리즘으로 combination을 작성해보았습니다.

 

 

 

 

3. 하노이의 탑 - 재귀적 알고리즘 활용

재귀적 알고리즘을 활용하면 정말 쉽게 해당 소스를 작성하여 결과값을 알 수 있습니다.

# hanoitop.py
def hanoi(n):
    if n == 1:
        return 1
    else:
        return 2*hanoi(n-1) + 1

print(hanoi(1))
print(hanoi(2))
print(hanoi(3))
print(hanoi(4))
print(hanoi(5))
print(hanoi(6))
print(hanoi(7))

 

 

 

 

4. 하노이의 탑 - 수학적 결론 활용

위에서 출력된 값을 보면 (2의 n제곱) - 1 이 결과값임을 알 수 있습니다.

# hanoitop2.py
def hanoi2(n):
    return pow(2,n)-1

print(hanoi2(1))
print(hanoi2(2))
print(hanoi2(3))
print(hanoi2(4))
print(hanoi2(5))
print(hanoi2(6))
print(hanoi2(7))