目录一、汉罗塔问题1.介绍2.讲解二、编程中的汉罗塔问题1.代码概览2.详解代码一、汉罗塔问题1.介绍汉诺塔问题是一个经典的问题。汉诺塔Hanoi Tower又称河内塔源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把所有圆盘移到另一根柱子上。并且规定任何时候在小圆盘上都不能放大圆盘且一次只能搬动一个圆盘。问应该如何操作搬动次数最少2.讲解假设我们有A、B、C三根石柱其中A为起始石柱B为中转石柱C为目的石柱。如果A上有一个圆盘我们可以直接将A上圆盘移到C上即A-C共1步如果A上有两个圆盘我们需要借助中转石柱即B石柱先将A上小圆盘移到B上再将A上大圆盘移到C上最后将之前移到B上的小圆盘移到C上即A-B A-C B-C共3步如果A上有三个圆盘我们首先将小圆盘移到C上接着中圆盘移到B后小圆盘再次移到B然后大圆盘移到C接着小圆盘移到A后中圆盘移到C最后小圆盘移到C即A-C A-B C-B A-C B-A B-C A-C共7步。…以此类推最小移动次数总为2^n-1n为圆盘总个数。需注意为取最小移动次数在实际移动时当圆盘总数为偶数时我们将第一个圆盘即最小圆盘先移到B当圆盘总数为奇数时则先移到C。二、编程中的汉罗塔问题现在我们想要编写一个程序输入n值代表起始石柱上圆盘总数然后让程序打印出移动步骤来帮助我们完成搬运工作。1.代码概览#includestdio.hMove(charpos1,charpos3)//打印移动步骤{printf(%c-%c ,pos1,pos3);}Hanio(intn,charpos1,charpos2,charpos3)//pos1起始石柱pos2中转石柱pos3目的石柱{if(n1){Move(pos1,pos3);}else{Hanio(n-1,pos1,pos3,pos2);//交换pos2,pos3Move(pos1,pos3);Hanio(n-1,pos2,pos1,pos3);//交换pos1,pos2}}intmain(){intn0;scanf(%d,n);Hanio(n,A,B,C);return0;}运行结果2.详解代码我们来看看这段代码是如何实现的先来看一张动图以4个圆盘为例上图可以分为三个阶段借pos3将pos1最上面3个圆盘转移到pos2交换pos1、pos3将最大的圆盘从pos1移至pos3借pos1将pos2上3个圆盘移至pos3上。其实到此我们已经说出了这段代码的精髓了。上面我们提到1个圆盘是A-C2个圆盘是A-B | A-C | B-C3个圆盘是A-C A-B C-B | A-C | B-A B-C A-C4个圆盘是A-B A-C B-C A-B C-A C-B A-B | A-C | B-C B-A C-A B-C A-B A-C B-C…易知除了1个圆盘外我们都可以用|划分出这三个阶段。1Hanio(intn,charpos1,charpos2,charpos3)2{3if(n1)4{5Move(pos1,pos3);6}7else8{9Hanio(n-1,pos1,pos3,pos2);10Move(pos1,pos3);11Hanio(n-1,pos2,pos1,pos3);12}13}所以我们构造分支如果n1则直接将圆盘从A搬到C如果n1,则else第9行为第一阶段第10行为第二阶段第11行为第三阶段。以n3为例运行逻辑如下所谓大事化小事这是递归的意义所在可以化繁为简。而图片中的’小事‘就是前文的三个阶段即第一层递归的三个支线其中的两个Hanio支线又可以细分、往复下去。可以发现一开始从外到内Hanio函数一直都是在传递形参即‘递’ 直到n1时才进入‘归’这时这种循环往复从内到外继续进行。再深思这种循环往复归根其实是pos1、pos2、pos3的循环往复。建议大家对着运行逻辑图拿纸笔将每一次交换都按顺序写下来用心领悟试着去分析一下个例搞透了整体思想也就容易理解了最终递归我们也就拿捏了。其实简单地讲递归无非就是一个从外‘递’至内从内‘归’回外的过程我们需要的只是明确递的是什么归的是什么这样就很容易理解汉罗塔问题了。