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);
}
}
网友评论