汉诺塔的由来
法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。
印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。
汉诺塔的规则:
1、有三根相邻的柱子,标号为A,B,C。
2、A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘。
3、现在把所有盘子一个一个移动到柱子B上,并且每次移动同一根柱子上都不能出现大盘子在小盘子上方。
算法过程原理:
- n个盘子时:
- 把n-1个圆盘从A经过C移到B上
- 把第n个圆盘从A移到C上
- 把n-1个小圆盘经过A从B移到C上
图片来自:汉诺塔三层图解,汉诺塔6层步骤,汉诺塔图片_大山谷图库 (dashangu.com)http://www.dashangu.com/postimg_17430370.html
算法实现:
#include<iostream>
using namespace std;
//汉诺塔问题
int sum;//设置常变量 总共需要走的步数sum
void hanoi(int n,char x,char y,char z){
void move(char X,int N,char Y);
if(n==1)
move(x,1,z);//直接从x移到z上
else
{
hanoi(n-1,x,z,y);// 把上面的n-1个圆盘,从A经过C移动到B
move(x,n,z);// 把第n个圆盘从A移动到C
hanoi(n-1,y,x,z);// 把那n-1块个圆盘,从B经过A移动到C
}
}
void move(char X,int N,char Y){
cout<<N<<"从"<<X<<"->"<<Y<<endl;
sum++;//每移动一次sum加一
}
int main(){
int n=0;
char A,B,C;
cout<<"请为n赋值:";
cin>>n;
hanoi(n,'A','B','C');//实参盘子数n 柱子A,B,C
cout<<"总共需要走的步数为:"<<sum<<endl;
return 0;
}
当圆盘数为3时的结果: 文章来源:https://www.toymoban.com/news/detail-722565.html
文章来源地址https://www.toymoban.com/news/detail-722565.html
到了这里,关于C++实现汉诺塔问题(递归实例)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!