인도의 오래된 전설 에서 기원 되 었 다.대 범 천 은 세 계 를 만 들 때 세 개의 금강석 기둥 을 만 들 었 고 한 기둥 에 아래 에서 위로 크기 순 으로 64 개의 황금 원반 을 쌓 았 다.대 범 천 은 브라만 에 게 원반 을 아래 부터 크기 순 으로 다른 기둥 위 에 다시 놓 으 라 고 명령 했다.또한 작은 원반 에 서 는 원반 을 확대 할 수 없고 세 기둥 사이 에 서 는 한 번 에 한 개의 원반 만 이동 할 수 있 도록 규정 하고 있다.-- 어떻게 조작 해 야 하나.
사상: 귀속
귀납 적 추리: 기둥 을 설치 하 는 번 호 는 A, B, C 이다.원반 의 원래 위 치 는 A 이 고 목표 위 치 는 C 이다.원반 개 수 는 n 이다.
n = 1. 직접 조작 A---->C, steps = 1
n = 2. 첫 번 째 조각 을 B: A-->B 로 옮 긴 다음 에 두 번 째 조각 을 C: A-->C 로 옮 기 고 마지막 으로 B-->C, steps = 1 + 1 + 1 = 3
n = 3. 첫 번 째 조각 과 두 번 째 조각 을 하나의 전체 로 하고 지난 단계 의 조작 을 통 해 B 로 옮 길 수 있 으 며 그 다음 에 세 번 째 조각 은 C 로 옮 길 수 있다.마지막 으로 이전 단계 와 유사 한 역 조작 으로 첫 번 째 조각 과 두 번 째 조각 에서 C 로 이동 합 니 다.steps =3+1+3=7
상기 조작 과 유사 하여 쉽게 관찰 할 수 있 고 전체 절 차 는 사실은 세 단계 로 나 뉘 어 완성 된다.
A 추출 전 n - 1 조각 을 B 로 옮 기기;
A 중의 n 번 째 조각 을 C 로 옮 깁 니 다.
B 의 앞 n - 1 조각 을 C 로 옮 기기;
n = 4 일 때 첫 번 째 단 계 는 7 단계 로 이동 해 야 하고 두 번 째 단 계 는 한 단계 가 필요 하 며 세 번 째 단계 도 7 단계 가 필요 하 다.따라서 steps = 7 + 1 + 7 = 15
귀납 을 통 해 그 중의 규칙 을 발견 하기 어렵 지 않 음 이 분명 하 다.
따라서 전체적인 절 차 는 S (n) = 2 n - 1 S (n) = 2 ^ n - 1 S (n) = 2 n - 1
이다. 코드 구현
구체 적 인 이동 절 차 는 python 으로 인쇄 되 고 전체 절 차 는 직접 공식 으로 계산 할 수 있다.
defhanoi(n, a, b, c):if n ==1:print(a,'-->', c)else:#A n-1 B
hanoi(n-1, a, c, b)# n Cprint(a,'-->', c)# B n-1 C
hanoi(n-1, b, a, c)if __name__=="__main__":
hanoi(5,'A','B','C')
참고 문헌:https://baike.baidu.com/item/한 노 타 / 3468295?fr=aladdin
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
