Proof of the thinking of Hanoi Tower problem

Preface

Problem description ： On a copper plate device , There are three rods ( Number A、B、C), stay A From the bottom up 、 Place in order from large to small 64 A gold plate ( Pictured 1). The goal of the game ： hold A All the gold plates on the pole are moved to C On the pole , And still keep the original order . Operating rules ： Only one plate can be moved at a time , And keep the big plate down all the time during the moving process , Small in , The plate can be placed during the operation A、B、C On any pole .

Problem analysis

In fact, the idea of the answer is very simple ：

• set up A There are n Disc
  • If n=1, Just put A->C ,Move( A, C);
  • If it's something else
    • Before A Upper n-1 A disk moves to B On ,Hanoi(n - 1, A, C, B)
    • then A The last disc on the moves to C On ,Move(A, C)
    • The final will be B Upper n-1 A disc moves C On ,Hanoi(n - 1, B, A, C)

But why is this feasible ？ This comparison is puzzling . Here I offer you an idea ： Using mathematical induction .
Prove :
hypothesis f(n) Operation representative handle n A disk from A The rod moves to C rod
Be careful , take n A disc, whether it's for A->C、B->C、A->B、C->B,B->A、C->A, These operations are completely equivalent

First ,f(1) The operation must be feasible
Now suppose f(n) Feasible operation , be f(n+1) The operation representative should put n+1 A disk from A The rod moves to C rod .

because f(n) Feasible operation , So you can put n A disk from A The rod moves to B rod , take A The last remaining disc of the rod is directly placed C rod .
Then it's because f(n) feasible , So you can put B Of the pole n A disk moves to C rod
Thus we can see that f(n+1) The operation of is feasible .

Obtain evidence ： When n∈{1,2,3,…} when , f(n) Feasible operation

Here is C Complete case of language version ,P121_6 Representative question number , This code is written when I brush questions . The only real operation to start is P121_6 This function , Other functions are used to output relevant information , It's convenient for us to observe what happened .

typedef struct {
    
       int *A;
       int *B;
       int *C;
       int top[3];
}s_Hannoi,*p_hannoi;

//  Hanoi Tower stack initialization 
void P121_6_init(s_Hannoi& h, int n)
{
    
       int i = n-1;
       h.A = (int*)malloc(sizeof(int) * n);
       h.B = (int*)malloc(sizeof(int) * n);
       h.C = (int*)malloc(sizeof(int) * n);
       h.top[0] = i;
       h.top[1] = -1;
       h.top[2] = -1;
       for (;i >= 0;i--) {
    
              h.A[i] = i;
       }
}

void P121_6_Move(s_Hannoi& h,char out,char in)
{
    
       int temp = -1,i,j;
       printf("%c->%c:\n", out, in);
       switch (out) {
    
       case 'A': 
              temp = h.A[h.top[0]];
              --h.top[0];
              break;
       case 'B':
              temp = h.B[h.top[1]];
              --h.top[1];
              break;
       case 'C':
              temp = h.C[h.top[2]];
              --h.top[2];
              break;
       }
       switch (in) {
    
       case 'A':
              ++h.top[0];
              h.A[h.top[0]] = temp;
              break;
       case 'B':
              ++h.top[1];
              h.B[h.top[1]] = temp;;
              break;
       case 'C':
              ++h.top[2];
              h.C[h.top[2]] = temp;
              break;
       }
       //  Print the current structure 
       printf("\tA:");
       for (i = 0;i < h.top[0]+1;i++) {
    
              printf("%d,", h.A[i]);
       }
       printf("\n\tB:");
       for (i = 0;i < h.top[1]+1;i++) {
    
              printf("%d,", h.B[i]);
       }
       printf("\n\tC:");
       for (i = 0;i < h.top[2]+1;i++) {
    
              printf("%d,", h.C[i]);
       }
       printf("\n");
}

//  The hanotta problem 
void P121_6(s_Hannoi& h,int n,char A,char B,char C)
{
    
       if (n == 1) {
    
              P121_6_Move(h, A, C);
       }
       else {
    
              P121_6(h, n - 1, A, C, B);
              P121_6_Move(h, A, C);
              P121_6(h, n - 1, B, A, C);
       }
}

int main()
{
    
       printf("***********************\n");
       s_Hannoi h;
       P121_6_init(h, 6);
       P121_6(h, 6, 'A', 'B', 'C');
}