한 로 타 재 귀적 실현 에 대한 사고 (C 언어)

한 로 타 는 고대 인도 신화 에서 만들어 진 지적 장난감 이다. 그의 게임 방법 은 세 개의 기둥 이 각각 A, B, C, A 기둥 위 에 n 개의 접시 위 에 작은 아래 에 크게 쌓 여 있다 는 것 이다. 지금 은 A 기둥 의 접 시 를 모두 C 기둥 위로 옮 기 고 한 번 에 한 개의 접시 만 옮 길 수 있 으 며 작은 접시 가 큰 접시 위 에 있어 야 한다.지금 은 C 언어 로 재 귀적 으로 완성 하고 재 귀적 호출 횟수 를 집계 해 야 한다.
이 실현 은 재 귀적 인 강력 한 기능 의 구현 입 니 다. 쓸데없는 말 은 하지 않 겠 습 니 다. 소스 코드 를 보십시오.

#include<stdio.h>
void move(int n,int *cnt,char A,char B,char C)
{
    if(n==1)
    {
        printf("%d  ：%c-->%c
",n,A,C);     //               ，   1    C 
        (*cnt)++;       //       1
    }

    else
    {
        move(n-1,cnt,A,C,B);       // n-1   A     C   B  
        printf("%d  ：%c-->%c
",n ,A,C);    //  n-1    B       A      C 
        move(n-1,cnt,B,A,C);        //   n-1   B     A   C  
        (*cnt)++;          //       1
    }

}
int main(void)
{
    int h;
    int cnt = 0;
    printf("
input number:
");
    scanf("%d",&h);
    printf("the step to moving %2d diskes:
",h);
    move(h,&cnt,'A','B','C');
    printf("     %d ！
",cnt);
}

내 가 여기 서 제시 한 소스 코드 는 매우 간단 하지만 매우 건장 하 다!현재 분석 은 다음 과 같다.
먼저, 생각 을 정리 하고 재 귀적 으로 실현 하 는 전 제 는 문제 의 규모 가 더욱 큰 해결 은 문제 의 규모 가 더욱 작은 해결 에 의존 하 는 것 이다. 즉, n 개의 접 시 를 이동 하려 면 n - 1 개의 접 시 를 먼저 이동 해 야 한다. 이때 재 귀적 인 기초 이다.그럼 지금 기둥 이 세 개 있 는데 어떻게 움 직 여야 하나 요?비교적 좋 은 해결 방안 은 n - 1 개의 접 시 를 C 기둥 을 중심 으로 B 기둥 으로 옮 길 수 있다 는 것 이다. 그러면 A 기둥 위의 맨 아래 에 있 는 접 시 는 C 기둥 으로 자 유 롭 게 이동 한 다음 에 n - 1 개의 접 시 를 A 기둥 을 중심 으로 C 기둥 으로 이동 할 수 있다. 이것 이 바로 상기 코드 핵심 의 해결 알고리즘 이다.
이 를 보고 많은 사람들 이 의문 을 가지 고 이 해결 방안 을 이해 한 것 같 기도 하고 이해 하지 못 한 것 같 기도 하 다. 이때 어떻게 된 일 인가?사실 이것 이 바로 재 귀적 인 이해 문제 다.이 문제 에서 n 개의 접 시 는 항상 이 알고리즘 에 따라 실 행 됩 니 다. n = 1 까지 실 행 될 때 한꺼번에 돌아 가 고 겹 쳐 서 최종 결 과 를 되 돌려 줍 니 다.
이 안에 또 하나의 재 미 있 는 문제 가 있 는데, 바로 재 귀 호출 된 매개 변 수 는 변수 이다. 예 를 들 어

move(n-1,cnt,A,C,B);

이 단계 에서 그 는 C 를 B 에 게 주 었 고 B 는 C 에 게 주 었 다. 이것 은 교환 이 고 n = 1 일 때 재 귀적 으로 호출 되 지 않 기 때문에 접시 수가 홀수 일 때 두 개의 수 는 교환 되 고 짝수 일 때 교환 되 지 않 는 다. 예 를 들 어 다음 과 같다.

#include <iostream>
using namespace std;
void swap (int n,int a,int b)
{
    if (n == 1)
    {
        cout << "a="<< a << "\tb=" << b << endl;
        return;
    }
    else
    {
        swap(n-1,b,a);
    }
}
int main (void)
{
    int a = 1;
    int b = 2;
    swap(3,a,b);
}

이 예 에서 main 함수 에서 매개 변수 가 홀수 일 때 a, b 는 교환 하지 않 고 짝수 일 때 교환 합 니 다. 이것 도 숫자 를 교환 하 는 알고리즘 입 니 다!허허!
예외 적 으로 한 로 타의 재 귀 호출 개 수 는 2 의 n 차방 에서 1 을 줄 이 는 것 입 니 다. 그러므로 여러분 이 시험 할 때 너무 큰 n 값 을 입력 하지 마 세 요. DOS 에서 전체 결 과 를 보지 않도록!