美文网首页
2.2 递归经典问题:汉诺塔问题

2.2 递归经典问题:汉诺塔问题

作者: Aurochsy | 来源:发表于2019-03-22 14:11 被阅读0次

    Chapter2: 时间复杂度分析、递归、查找与排序

    2. 递归经典问题:汉诺塔问题

    问题

    有A,B,C三个柱子,在A柱上有1N个圆盘,将1N个圆盘从A柱移动到C柱,移动过程中始终保持小盘在上,大盘在下

    算法

    递归思路

    一次递归调用执行了以下操作:

    • 先将顶上的 N-1 个盘子从A柱移到B柱上,借助C柱
    • 再将底下最大的盘子从A柱移到C柱上
    • 将这 N-1 个盘子从B柱移到C柱上,借助A柱

    代码

    int main(){
        int n=4;
        char a='a',b='b',c='c';
        hanoi(n,a,b,c);
        return 0;
    } 
    
    void hanoi(int n,char a,char b,char c){
        if(n==1){
            printf("move %d from %c to %c\n",n,a,c);
        }
        else{
            hanoi(n-1,a,c,b);
            printf("move %d from %c to %c\n",n,a,c);
            hanoi(n-1,b,c,a);
        }
    } 
    

    相关文章

      网友评论

          本文标题:2.2 递归经典问题:汉诺塔问题

          本文链接:https://www.haomeiwen.com/subject/wdnlvqtx.html