递归-汉诺塔

问题描述

算法复杂度

• 2的n次方再减1
  n为盘子的个数

算法实现

#include <stdio.h>#include <stdlib.h>/**
    汉诺塔问题
*/void hanoi(int n,char A, char B, char C){    if(1==n) //如果是一个盘子，直接将盘子从A柱子移到B柱子上
        printf("将编号为%d的盘子从柱子%c移到柱子%c\n",n,A,C);    else{
        hanoi(n-1,A,C,B); //将A上的n-1个盘子借助C移到B
        printf("将编号为%d的盘子从柱子%c移到柱子%c\n",n,A,C); //直接将A柱子上的第N个盘子移到C柱子上
        hanoi(n-1,B,A,C); //将B柱子上的n-1个盘子借助A移到C
    }
}int main(){    //模拟三个柱子
    char chA='A';    char chB='B';    char chC='C';    //盘子个数
    int n;    printf("请输入需要移动盘子的个数：");    scanf("%d",&n);
    hanoi(n,chA,chB,chC);    return 0;
}

运行结果

3个盘子

2个盘子

1个盘子

5个盘子

作者：桓宇Harry
链接：https://www.jianshu.com/p/db4d6d4d6c57