Python 재 귀 알고리즘 한 노 타 문제 풀이

3827 단어 python
문제 설명
고대 에는 범 탑 이 있 었 는데 탑 안에 세 개의 받침대 가 있 었 다 고 한다. A, B, C, A 자리 에는 64 개의 접시 가 있 었 고 접시 의 크기 가 같 지 않 았 으 며 큰 것 은 아래 에 있 고 작은 것 은 위 에 있 었 다.한 스님 이 이 64 개의 접 시 를 A 자리 에서 C 자리 로 옮 기 려 고 했 지만, 매번 한 개의 접 시 를 옮 길 수 밖 에 없 었 다.접 시 를 옮 기 는 과정 에서 B 자 리 를 이용 할 수 있 지만, 언제나 3 자리 의 접 시 는 큰 접시 가 아래 에 있 고 작은 접시 가 위 에 있 는 순 서 를 유지 해 야 한다.접시 가 하나 밖 에 없다 면 B 자 리 를 이용 하지 않 고 A 에서 C 로 접 시 를 옮 기 면 된다.스님 은 이 임무 의 상세 한 이동 절차 와 순 서 를 알 고 싶 어 한다.
수학 지식 에 따 르 면 n 개의 접 시 를 옮 기 려 면 2 ^ n - 1 단계 가 필요 하고 64 개의 접 시 는 18446744073709551615 단계 가 필요 하 다 는 것 을 알 수 있다.한 걸음 에 1 초가 필요 하 다 면 584942417355.072 년 이 필요 하 다.
재 귀 알고리즘 해결
def hannoi(num, src, dst, temp=None):
    global times
    assert type(num) == int, 'num must be integer'
    assert num > 0, 'num must > 0'    
    if num == 1: 
        print('The {0} Times move:{1}==>{2}'.format(times, src, dst))
        times += 1
    else:
        hannoi(num-1, src, temp, dst)
        hannoi(1, src, dst)
        hannoi(num-1, temp, dst, src)


times = 1
hannoi(3, 'A', 'C', 'B')  #A           ,C     ,B     

좋은 웹페이지 즐겨찾기