한노타 문제-귀속(9개월 만에 깨달음)

내가 처음으로 한노타라는 문제를 풀었을 때가 2017년 11월이었던 것을 기억한다.당시 나는 산대청도교구 도서관 3층에 앉아서 왠지 이 문제를 보았다.
그리고 하루 종일 생각했어요.
물론 비극은 내가 당시에 하루 동안 이 문제의 귀착된 사고방식을 진정으로 이해하지 못했다는 것이다.
이제야 알았어, 헤헤헤.
 
귀환에 관하여: 대형 귀환의 과정을 추적하려 하지 마세요!귀환을 쓰려면 관건은 귀환의 귀환 방정식을 찾아내는 것이다. 즉, 마지막 단계를 완성하려면 마지막 단계의 앞단계에서 무엇을 해야 하는가이다.
 
반복 정보:
(1) f(n,other variables)를 구할 때 f(n-1,other variables)가 이미 구해졌다는 것을 묵인한다. 어떻게 구했는지는 컴퓨터가 거슬러 올라가서 구한 것이다.
PS:여기 창고(stack)라는 선진적인 후출 데이터 구조를 사용했기 때문에 귀속 출력의 답은 일반적으로 아래에서 위로 올라간다.
(2) 귀속은 두 갈래 나무와 밀접한 관계가 있다.두 갈래 나무의 데이터 구조를 통해 귀속이 어떻게 한 문제를 몇 개의 하위 문제로 나누는지 이해하고 다시 거슬러 올라갈 수 있다.여기에 다음과 같은 빠른 정렬(Quick Sort)의 과정을 참고할 수 있다(빠른 정렬의 핵심 사상은 분리, 분리는 분리, 분리를 통해 원문제를 몇몇 쉽게 풀 수 있는 자문제로 분해한 다음에 분리를 통해 이 자문제를 연결시키고 두 갈래 나무의 상층으로 거슬러 올라가 최종적으로 원문제를 풀 수 있다)
 
 
귀환의 관건은 두 가지가 있다.
(1) 반복되는 종료 조건(쓰지 않으면 순환이 멈추고 TLE)
(2) 마지막 층과 다른 관계가 있는 층의 관계를 비귀속 함수로 어떻게 표현하는가
예를 들어 피보나치아 수열은 (1) n==1과 n==2일 때 f(n)=1이다. 이것이 바로 귀속의 종지 조건이다.종지 조건을 주어야만 컴퓨터가 서브 문제를 풀고 거슬러 올라가 최종적으로 f(n)를 구할 수 있다.
 
이 한노타 문제에 대해 귀환을 쓸 때 우리는 단지 두 가지 조건을 확정할 수 있다.
1.귀환은 언제 끝납니까?
2. 귀속의 핵심 공식은 무엇입니까?즉,
어떻게 n개의 접시를 모두 C기둥 위로 이동합니까?
즉, n개의 접시를 모두 C기둥으로 옮기면 그 다음에는 무엇을 해야 합니까?
 

다음은 본격적으로 이 문제에 들어갑니다.

한노타 문제는 고전적인 문제다.하노이타워(Hanoi Tower)는 하노이타워라고도 하는데 인도의 오래된 전설에서 기원한다.대범천이 세계를 창조할 때 세 개의 금강석 기둥을 만들었는데 한 기둥에 아래에서 위로 크기순으로 64개의 황금 원반이 쌓여 있었다.대범천은 브라만에게 원반을 아래에서부터 크기순으로 다른 기둥에 다시 놓으라고 명령했다.또 언제든지 작은 원반에서 원반을 확대할 수 없으며 세 기둥 사이에서 한 번에 한 원반만 이동할 수 있도록 했다.-- 어떻게 해야 하나.
 
다음은 우리가 귀속 함수를 쓸 것이다.
우선, 제목이 요구하는 것은 어떻게 조작하는가이다. 그러면 우리는 반드시 출력 조작 문장의 함수를 써야 한다.
이 조작 문장은 반드시 설명해야 한다. 몇 번째 단계는 어느 접시를 어느 기둥에서 어느 기둥으로 옮기는지 (이렇게 해야 사람이 접시를 어떻게 움직이는지 알 수 있잖아)
여기에서, 우리는 이 함수의 함수를 모브라고 정의한다.
다음에, 우리는 이 함수의 매개 변수 목록을 확정할 것이다.
분명히 몇 번째 단계에서 어느 접시를 어느 기둥에서 어느 기둥으로 이동하는지 설명하기 위해서, 우리의 매개 변수 목록은 적어도 다음과 같아야 한다.
id, 이동된 접시의 번호를 표시합니다.
from, 어느 기둥에서 이 번호가 id인 접시를 이동하는지 표시합니다
기둥
그러면 이 함수의 함수 헤더는 확정된다.
void move(int id,char from,char to)//인쇄 이동 방식: 번호, 어느 접시에서 어느 접시로 이동
 
그럼 함수체는요?
유일한 난점은 이것이 조작의 몇 번째 단계인지를 어떻게 기록하는가이다.
매번 조작할 때마다 이동 방식을 출력해야 하고 한 번만 출력할 수 있다는 것을 알아차리면, 분명히 우리는 이미 printf의 현재 총 수량이 몇 번째 조작이 아닌가
저희가 전역 변수를 켜서 printf의 횟수를 기록하면 돼요.
그래서 함수체에는 이 문만 있다.

printf ("step %d: move %d from %c->%c
", ++cnt, id, from, to);

통합하면 다음과 같습니다.

void move(int id, char from, char to) //  ： ， 
{
    printf ("step %d: move %d from %c->%c
", ++cnt, id, from, to);
}

 
칠판을 두드리다
역귀함수는 어떻게 씁니까?
우리 인류가 어떻게 조작해야 할지 먼저 생각해 봅시다.
우리는 매번 조작할 때마다 이렇게 자신에게 묻는다. 우리는 어느 기둥 위의 몇 개의 접시를 어느 기둥을 통해 어느 기둥으로 이동해야 합니까?
우리는 반드시 이렇게 몇 개의 매개 변수만 사용할 수 있어야 한다.
이동해야 할 접시의 총수, 기둥 3개.
그래서 함수 헤더는 다음과 같다.

void hanoi(int n, char x, char y, char z)

그중 n은 접시 총수, x, y,z는 기둥을 대표한다
한오(n,x,y,z)의 뜻은 n개의 x 기둥에 있는 접시를 y라는 기둥을 통해 z라는 기둥으로 이동시키는 것이다.
그럼 끝이잖아!
한오(n,'A','B','C')가 바로 이 문제의 답이다!
 
그러면 이 단계의 앞단계는 무엇입니까?
f(n,other variables)를 풀 때 f(n-1,other variables)가 이미 끝났다는 것을 묵인하면 된다는 것을 기억하세요!이것은 앞에서 이미 설명했으니, 여기서 더 이상 서술하지 않겠다.
우리는 n-1개의 접시를 하나의 전체로 여긴다. 이것이 바로 분해구해자 문제와 유사한 사상이다
그러면 앞의 단계인 f(n-1,other variables)는 분명히 A기둥에 있는 n-1개의 접시를 C기둥을 통해 B기둥으로 옮긴 다음에 A기둥에 있는 번호가 n인 접시를 C기둥으로 옮긴 다음에 B기둥에 있는 n-1개의 접시를 A기둥을 통해 C기둥으로 옮긴 오버.
 
C++ 코드는 다음과 같습니다.

void hanoi(int n, char x, char y, char z)
{
    if (n == 0)
        return;
    hanoi(n - 1, x, z, y);
    move(n, x, z);
    hanoi(n - 1, y, x, z);
}

한노타 전체 코드:

#include 
#include 
using namespace std;

int cnt;

void move(int id, char from, char to) //  ： ， 
{
    printf ("step %d: move %d from %c->%c
", ++cnt, id, from, to);
}

void hanoi(int n, char x, char y, char z)
{
    if (n == 0)
        return;
    hanoi(n - 1, x, z, y);
    move(n, x, z);
    hanoi(n - 1, y, x, z);
}

int main()
{
    int n;
    cnt = 0;
    scanf ("%d", &n);
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

 

사용자 친화적 버전:

#include 
#include 
using namespace std;

int cnt;

void move(int id, char from, char to) //  ： ， 
{
    ++cnt; //  
    printf ("step %d: move %d from %c->%c
", cnt, id, from, to);
}

void hanoi(int n, char x, char y, char z)
{
    if (n == 0)
        return;
    hanoi(n - 1, x, z, y);
    move(n, x, z);
    hanoi(n - 1, y, x, z);
}

int main()
{
    int n;
    printf("Please enter the number of the plates:");
    while (~scanf ("%d", &n) && n)
    {
        cnt = 0;
        printf ("The following are the steps for the question
");
        hanoi(n, '1', '2', '3');
        printf ("There are %d steps in all.
You have solved the hanoi problems, congratulations!
", cnt);
        printf ("Would you like to continue?(y/n)");
        char ch; scanf (" %c", &ch);
        if (ch == 'y' || ch == 'Y')
            printf("Please enter the number of the plates:
");
        else
        {
            printf ("Here comes the end of the program. Bye
");
            break;
        }
    }
    return 0;
}