评论详情-牛客网

汉诺塔问题跟树的LDR遍历一个道理

1.对于单个情形，也就是最大的圆盘的情形，直接从A移动到C，因此直接打印移动的方法即可，并且返回

2.对于两个圆盘的情形，分为三步进行：

（1）从A移动到B一个

（2）从A移动到C一个

（3）将B中暂存的移动到C

因此跟BST的递归LDR遍历非常像，此时我们的调用打印应该为三步：

（1）打印A-B

（2）打印A-C

（3）打印B-C

因此我的递归为:

hanoi(n-1,A,C,B)；
printf当前A-C;
hanoi(n-1,B,A,C);

void hanoi(int n,char A,char B,char C){
    if(n<=1){
        printf("1 move %c to %c\n",A,C);
        return;
    }
    hanoi(n-1,A,C,B);
    printf("%d move %c to %c\n",n,A,C);
    hanoi(n-1,B,A,C);
}

这样可以输出每一次的移动情况，如果只需要次数，不输出，累加个数即可