汉诺塔递归思维

短命女 2021-12-03 06:37 314阅读 0赞

汉诺塔比较经典的实现是利用递归，但也可以利用堆栈。

题意理解：有A,B,C三个柱子，将A柱子上的N个盘子（从大到小排列）移到C柱子上，每次只允许移动一个盘子，并且保证每个柱子上的盘子的排列都是从大到小。

1、递归实现

假设只有一个盘子，那么只需实现 A->C 这个动作；

如果有两个盘子，那么需要

(1)A->B;

(2)A->C;

(3)B->C;

如果有三个盘子，可以将前两个盘子看作一个盘子，对两个盘子重复以上三个步骤，于是得到N个盘子的递归算法，递归结束的条件是N=1；

![复制代码][copycode.gif]

1 void Hanoi(int n,char A,char B,char C)  //A借助B,将n个盘子移到C ,递归的妙用在于不用关心具体实现的细节
     2 {
     3     if (n==1)printf("%c -> %c",A,C); //只有一个盘子，直接将其移到C
     4     else
     5     {
     6         Hanoi(n-1,A,C,B);  //第一步，A借助C，将n-1个盘子移到B;
     7         printf("%c -> %c",A,C);   //第二步，将A上剩余的一个盘移到C;
     8         Hanoi(n-1,B,A,C)  //第三步，将B上的n-1个盘子移到C。
     9     }
    10 }

![复制代码][copycode.gif]

![943171-20170202223237042-1995142481.jpg][]

可以用人脑来模拟一下该过程：

当有三个盘子时，在主函数中调用Hanoi（3，A，B，C）时，进入函数中执行else后的一句，Hanoi（2，A，C，B），并且在栈中为后续语句分配空间但不执行。接着再调用自身，Hanoi（1，A，B，C），输出A->C;函数开始“归”，即执行调用Hanoi（1，A，B，C）函数之后未执行的语句，“第二步”，由于这是在函数Hanoi（2，A，C，B），故输出A->B;接着调用Hanoi（1，C，A，B），输出C->B;接着“归”，此时回到函数Hanoi（3，A，B，C），输出A->C;接着调用函数Hanoi（2，B，A，C），在调用Hanoi（1，B，C，A）输出B->A;接着输出B->C;最后，调用Hanoi（1，A，B，C）输出A->C.

\------------------------------------------------------------------------------------------------------------------------------------------------------

以下是利用堆栈实现非递归：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<stdlib.h>
     3 #include<stdbool.h>
     4 typedef struct Problem{
     5     int n;
     6     char src,mid,dest;
     7     struct Problem *Next;
     8 }Stack;
     9 
    10 Stack *CreateStack()
    11 {
    12     Stack *S;
    13     S=(Stack*)malloc(sizeof(struct Problem));
    14     S->Next=NULL;
    15     return S;
    16 }
    17 
    18 bool IsEmpty(Stack *S)
    19 {
    20     return (S->Next==NULL);
    21 }
    22 
    23 void Push(Stack *S,int n,char A,char B,char C)
    24 {
    25     Stack *TmpCell;
    26     TmpCell=(Stack *)malloc(sizeof(struct Problem));
    27     TmpCell->n=n;
    28     TmpCell->src=A;
    29     TmpCell->mid=B;
    30     TmpCell->dest=C;
    31     TmpCell->Next=S->Next;
    32     S->Next=TmpCell;
    33 }
    34 
    35 Stack *Pop(Stack *S,Stack *curPrb)
    36 {
    37     Stack *FirstCell;
    38     FirstCell=(Stack *)malloc(sizeof(struct Problem));
    39     FirstCell=S->Next;
    40     curPrb->n=FirstCell->n;curPrb->src=FirstCell->src;curPrb->mid=FirstCell->mid;curPrb->dest=FirstCell->dest;
    41     S->Next=FirstCell->Next;
    42     free(FirstCell);
    43     return curPrb;
    44 }
    45 
    46 int main()
    47 {
    48     int n;
    49     scanf("%d",&n);
    50     Stack *S;
    51     S=CreateStack();
    52     Push(S,n,'A','B','C');
    53     while (!IsEmpty(S))
    54     {
    55         Stack *curPrb;
    56         curPrb=(Stack *)malloc(sizeof(struct Problem));
    57         curPrb=Pop(S,curPrb);
    58         if (curPrb->n==1)printf("%c -> %c\n",curPrb->src,curPrb->dest);
    59         else
    60         {
    61             Push(S,curPrb->n-1,curPrb->mid,curPrb->src,curPrb->dest);//堆栈的顺序和递归正好相反
    62             Push(S,1,curPrb->src,curPrb->mid,curPrb->dest);
    63             Push(S,curPrb->n-1,curPrb->src,curPrb->dest,curPrb->mid);
    64         }
    65         free(curPrb);
    66     }
    67     free(S);
    68     return 0;
    69 }

![943171-20170202223431183-2080596326.jpg][]

转载于:https://www.cnblogs.com/zcy773883/p/10807599.html

[copycode.gif]: /images/20211203/0d2efb22e3b64c97b80bcfd322b0e093.png
[943171-20170202223237042-1995142481.jpg]: /images/20211203/92034be771b14a8b9f164c63691e514a.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211203/3eb2442a6aaf47a6b8172680a6642571.png
[943171-20170202223431183-2080596326.jpg]: /images/20211203/72781a6ea2524f8b84c0e1ebe083ccde.png