하노이 타워 문제에 대한 재귀 알고리즘과 비재귀 알고리즘이 실제로 동일한 것임을 증명

증명: 하노이탑 문제를 푸는 함수를 하노이(n, A, B, C)라고 하자

위 문제는 수학적 귀납법으로 증명 가능

n=1이고 n=2인 경우 쉽게 직접 확인할 수 있습니다. k<=n-1일 때 재귀 알고리즘과 비재귀 알고리즘이 정확히 동일한 이동 시퀀스를 생성한다고 가정합니다. k=n일 때의 상황을 살펴보세요.

움직임을 시계 방향 움직임(S), 반시계 방향 움직임(N), 최소 디스크 타워 사이의 움직임(F)의 세 가지 상황으로 나눕니다.

(1) n이 홀수일 때 시계방향 비재귀 알고리즘에 의해 생성된 이동 시퀀스는 S, F, S, F,······S이고 다음과 같이 생성된 시퀀스는 다음과 같다. 시계 반대 방향 비재귀 알고리즘은 N,F,N,F,······N입니다.

n이 짝수일 때 시계방향 비재귀 알고리즘에 의해 생성된 이동 시퀀스는 N,F,N,F,······N이고 반시계방향 비재귀 알고리즘에 의해 생성된 시퀀스는 -재귀 알고리즘은 S,F,S,F,······S입니다.

(2) n이 홀수인 경우 시계 방향 재귀 알고리즘 하노이(n, A, B, C)에 의해 생성된 이동 시퀀스는

하노이(n-1, A, C, B)에 의해 생성된 이동 시퀀스, F, 하노이에 의해 생성된 이동 시퀀스(n-1, C, B, A)

어디, 하노이(n-1, A, C, B) 하노이(n-1, C, B, A)는 모두 짝수 원반이 시계 반대 방향으로 움직이는 문제입니다. 수학적 귀납법에 따르면 이들이 생성하는 동작 시퀀스는 모두 S, F, S, F,······S입니다. 따라서 하노이(n, A, B, C)에서 생성된 이동 시퀀스는 S, F, S, F,······S이다.

n이 짝수인 경우 시계 방향 재귀 알고리즘 하노이(n, A, B, C)에 의해 생성된 이동 시퀀스는

하노이(n-1, A, C)입니다. , B ), F, 하노이(n-1, C, B, A)에서 생성된 이동 시퀀스

여기서, 하노이(n-1, A, C, B) 하노이(n-1, C, B, A)는 모두 홀수 디스크의 시계 반대 방향 이동 문제입니다. 수학적 귀납법에 따르면 이들이 생성하는 동작 시퀀스는 모두 N, F, N, F,······N입니다. 따라서 하노이(n, A, B, C)에서 생성된 이동 시퀀스는 N, F, N, F,······N이다.

n이 홀수일 때와 짝수일 때 반시계방향 재귀 알고리즘도 비슷합니다.

재귀 알고리즘과 비재귀 알고리즘이 동일한 이동 시퀀스를 생성한다는 것을 수학적 귀납법을 통해 알 수 있습니다.