[算法设计与分析考点3] 递归经典案例之汉诺塔问题

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

文章目录

印度的古老传说

在世界中心贝拿勒斯在印度北部的圣庙里一块黄铜板上插着三根宝石针。

印度教的主神梵天在创造世界的时候在其中一根针上从下到上地穿好了由大到小的64片金片这就是所谓的汉诺塔。

不论白天黑夜总有一个僧侣在按照下面的法则移动这些金片一次只移动一片不管在哪根针上小片必须在大片上面。僧侣们预言当所有的金片都从梵天穿好的那根针上移到另外一根针上时世界就将在一声霹雳中消灭而梵塔、庙宇和众生也都将同归于尽

问题描述

有三根标号为A,B,C且相邻的柱子A柱子从上到下按照金字塔形状从小到大叠放着n个不同大小的圆盘现在要把所有的盘子一个一个地移动到B柱子上并且每次移动的盘子中小盘子只能在大盘子的上方请打印出具体的移动步骤。

解题思路

当n=3时具体地移动步骤是

A-->C
A-->B
C-->B
A-->C
B-->A
B-->C
A-->C

总共7步如下图所示

可以总结得到当有n个圆盘时移动的核心思想是

先把n-1个盘子从A借助C移动到B上
把第n个盘子最大的那个盘子直接移动到C上
最后再把n-1个盘子从B借助A移动到C上

递归实现

#include<iostream>
using namespace std;
int sum=0;//计数总共移动次数 
//移动函数 
void move(char start,char end){
	cout<<start<<"-->"<<end<<endl;
	sum++;
}
//递归函数
void hanoi(char A,char B,char C,int n){
	//递归终止条件 只有一个盘子时直接从A移动到C 
	if(n==1){
		move(A,C);
	}else{
		hanoi(A,C,B,n-1);//将n-1个盘子从A借助空柱子B移动到C 
		move(A,C);//此时A只剩下第n个盘子即最大的盘子直接从A移动到C放入底部 
		hanoi(B,A,C,n-1); //最后将B上的n-1个盘子借助空柱子A移动到C上 
	}
}
int main(){
	int n;
	cout<<"请输入汉诺塔的层数";
	cin>>n;
	cout<<"圆盘的移动步骤如下"<<endl;;
	hanoi('A','B','C',n);
	cout<<"一共移动了"<<sum<<"次"<<endl; 
	return 0;
}