java递归思想之---汉诺塔
2021-07-20 09:08
标签：最大 param 日本 struct 针对 些许 程序语言 分析 程序设计 目前看过的书籍中分析递归最好的是日本人吉城浩写的《程序员的数学》 总结： 汉诺塔 ??现在我们先不需要知道递归是什么，也没必要，我们先来看一个非常经典的游戏—汉诺塔，该游戏是数学家爱德华卢卡斯于1883年发明的，游戏的规则如下，有三根细柱（A、B、C），A柱上套着6个圆盘，圆盘的大小都不一样，它们按照从大到小的顺序自下而上地摆放，现在我们需要把A柱上的圆盘全部移动到B柱上去，并且在移动时有如下约定： 此时约定将一个圆盘从一根柱子移动另一根柱子算移动“1”次，那么将6个圆盘全部从A移动到B至少需要移动多少次呢？模型如下图： 整个过程如下图所示： ??从上图中，我们很容易理解3层汉诺塔的解法，但是细想一下会发现这7次动中我们好像在做重复的事情：移动圆盘，只不过方向时而不同罢了。重新回顾一下①②③④⑤⑥⑦的移动过程，然后把它们分为如下3种情况： ??我们发现这个过程移动的操作是几乎一样的，只不过是移动的方向不同了，A->C和C->B两种，其过程如下图： ??从图确实可以看出虽然两次移动的目的地不相同，但是两次移动的操作却是非常相似的，而且我们发现如果把3次移动看成是“移动2个圆盘”的操作就是“2层汉诺塔的解法”，也就是说在解决3层汉诺塔的过程中，我们使用了“2层汉诺塔的解法“。既然如此，那是不是意味着解决”4层汉诺塔“的过程中可以使用解决”3层汉诺塔的解法“呢？嗯，确实是如此的，这就是汉诺塔的解法规律，没错，我们已经发现这种规律！这样的话，我们解决前面的6层汉诺塔的问题时，只需要先解决5层汉诺塔的问题，然后利用5层汉诺塔的解法来解决6层汉诺塔的问题即可！我们来看看利用5层汉诺塔解出6层汉诺塔的过程，如下： ??从图中我们可以看出（a）和（c）就是5层汉诺塔的解法，为了解出6层汉诺塔需要使用到5层汉诺塔的解法，因此只要5层汉诺塔被解出，6层汉诺塔也就迎刃而解了。而5层汉诺塔的解法呢？没错利用我们前面发现的规律，用4层汉诺塔的解法去解出5层汉诺塔，如下过程： 这样5层汉诺塔就被解出了，而4层汉诺塔则可以利用同样的解法即使用3层汉诺塔的解法，3层汉诺塔再利用2层汉诺塔的解法……..依次类推即可，到此便已解出6层汉诺塔，实际上我们知道有了6层汉诺塔的解法自然就可以很轻松地解出7层汉诺塔，8层汉诺塔…….N层汉诺塔，也很容易发现这种利用已知的N-1层的解法来解决N层的问题的解题方式，它们每一层的解法结构都是相同即利用前一个已解决的问题结果来解决后一个问题。通过这种思考的方式，我们来总结一下N层汉诺塔的解法，不再使用具体的ABC三根柱子，而是将它们设为x、y、z。这样的话，x、y、z在不同的情况下会不固定对应ABC中的某一根。这里以x为起点柱，y为目标柱，z为中转柱，然后给出解出N层汉诺塔的过程。利用z柱将n个圆盘从x柱转移到y柱的解法如下： ??从上述过程可知为了解出n层汉诺塔，我们同样需要先解出n-1层汉诺塔，为更通用地表示解出n层汉诺塔的移动次数，将其设为H(n)。利用上述步骤，则有如下关系： ??这样我们也就知道了6层次汉诺塔的最少移动次数为63次（关于2^n-1的公式只是总结出更为简单的计算方式摆了）。到此我们来重新梳理一下汉诺塔的整个解题过程，在解出6层汉诺塔前，我们由于一时找不到解决的方法，因此先尝试解出更为简单3层汉诺塔的，而在这个过程中，我们慢慢发现了解决汉诺塔问题的通用规律，即使用n-1层的解法来解决n层汉诺塔的思考方式,通过这种思考方式最终成功地解决了6层汉诺塔的问题。而实际上我们利用的这种思考方式的本质就是将复杂的问题转换为较为简单的同类问题(回忆一下汉诺塔的问题解法)然后再找出解决方法最终利用简单同类问题解出复杂问题的过程，而这种思维的方式就是递归！！是的，没错！递归不是算法而是一种思考的思维方式，只不过我们将这种递归思维方式采用程序来解决时，该程序被称为递归算法罢了，而递归本身是一种思考问题的思维方式！到此我们对递归是否有些焕然大悟的感觉呢？或对递归有些许的理解了吧？ ??有了上述的分析，我们就可以这样去理解和使用递归，假设现在碰到了一个很复杂的难题，我们也明白‘简单问题易解’的道理，那么此时就可以利用类似于汉诺塔的解题的思考方式，即判断能否将目前复杂的问题转换为较为简单的同类问题呢？可以的话，就先转换为简单同类的问题来解决，然后再利用简单的同类问题解法来解决复杂的同类问题，这就恰恰就是递归思维方式的精髓所在，嗯，这就是递归！大家现在是不是已开始理解递归了呢？我们在回顾一下汉诺塔问题的解法，以便加深对递归的理解，如下图： ??上图很清晰表现出n层汉诺塔的解法过程，通过复杂问题化为同类简单问题来求解，上述的图形还有一个名称叫做递归结构，根据该结构我们就可以建立起之前H(n)递推公式了，很显然发现递归结构并建立递推公式的过程十分重要，这样有助于我们把握本质问题即通过n-1层汉诺塔的解法来解决n层汉诺塔的问题，这样的发现能力需要我们有比较敏锐的洞察力和思维能力，这就需要我们再遇到复杂问题时，多采用递归的思维（复杂问题简单化）方式去思考，去挖掘规律。ok~，到此相信我们对递归已有比较清晰的了解了吧。接下来我们看看如何使用程序来实现递归算法并解决汉诺塔的问题。 ??通过前面的分析，我们明白所谓的递归不过就是把复杂问题简单化的思维方式，而这种思维方式从程序语言的角度出发则称为递归算法，它通过程序的函数方法直接或者间接调用函数自身的过程，回忆一下前面分析汉诺塔的递推公式：H(n)=H(n-1)+1+H(n+1) 我们通过程序的递归算法实现汉诺塔如下： 从代码可以发现递归算法的踪影： ??因此到此我们也就明白了，递归思维在程序中的体现即为递归算法，而递归算法本身在程序内部的实现就是函数调用自身函数，这样大家总该理解递归算法了吧。这里有点要提醒大家的是，不要陷入程序递归的内部去思考递归算法，记住要从递归思维的本质(复杂问题简单化)出发去理解递归算法，千万不要去通过试图解析程序执行的每一个步骤来理解递归（解析程序的执行是指给函数一个真实值，然后自己一步步去推出结果，这样的思考方式是错误的！），那样只会让自己得到伪理解(没有真正理解)的结果。记住！递归并不是算法，是一种复杂问题简单化的思维方式，而这种思维方式在程序中的体现就递归算法！递归算法在实现上就是函数不断调用自身的过程！ ??通过前面大篇幅的分析，到此我们总算是理解递归了，那么接下来我们给出递归的正式定义，相信有了上述基础，理解递归的正式定义还是比较轻松的，递归其实是数学中一种重要的概念定义方式，而递归算法则是针对程序设计而言的，即不同角度的两种称呼但本质是一样的。 java递归思想之---汉诺塔 标签：最大 param 日本 struct 针对 些许 程序语言 分析 程序设计 原文地址：https://www.cnblogs.com/Darkqueen/p/9517726.html汉诺塔的问题
??图虽然很清晰，但我们依然无法立即找到特别清晰的解法，既然如此，我们就尝试先把问题的规模缩小点，把6个圆盘改为3个圆盘，先找出3层汉诺塔的解法，模型变为下图: 
??3层汉诺塔的解法就相对来说简单多了，我们要把3个圆盘全部从A移动到B，只需要先将最小的圆盘从A移动到B，然后将次小的圆盘从A移动到C，接着再把最小的圆盘从B移动到C，然后把最大的圆盘从A移动到B，接着把最小盘从C移动到A，在把次小盘从C移动到B，最后把最小盘从A移动到B即可，这样我们就完成了3此汉诺塔的解法了。这里我们把3个圆盘从小到大分别设为a,b,c，那么其移动过程如下：/**
元素 过程
a A->B
b A->C
a B->C
c A->B
a C->A
b C->B
a A->B
移动7次完结..
**/
Blog :http://blog.csdn.net/javazejian[原文地址]
/**
当 n=0时，无需任何移动
当 n>0时，
①将n-1个圆盘从x柱，经y柱中转，移动到z柱(即解出n-1层汉诺塔)
②然后将1个圆盘从x柱移动到y柱(最大的圆盘)
③最后将n-1个圆盘从z柱，经x中转移动到y柱(即解出n-1层汉诺塔)
**/
??在数学上我们将这种H(n)和H(n-1)的关系式取了个名称，叫做递推公式，即已知H(0),由H(n-1)构成H(n)的方法也必然是已知的，只要依次计算便可以得出，如6层汉诺塔的递推过程如下：Blog :http://blog.csdn.net/javazejian[原文地址]
/**
H(0)=0 = 1-1
H(1)=H(0)+1+H(0) = 1 = 2-1
H(2)=H(1)+1+H(1) = 3 = 4-1
H(3)=H(2)+1+H(2) = 7 = 8-1
H(4)=H(3)+1+H(3) = 15 = 16-1
H(5)=H(4)+1+H(4) = 31 = 32-1
H(6)=H(5)+1+H(5) = 63 = 64-1
....... = .........
H(n)=H(n-1)+1+H(n-1) = 2^n -1
**/
递归的思维方式
汉诺塔的递归算法程序实现
package com.zejian.structures.recursion;
/**
* Created by zejian on 2016/12/11.
* Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
* 汉诺塔的递归算法实现
*/
public class HanoiRecursion {
/**
* @param n 汉诺塔的层数
* @param x x柱 起点柱(A)
* @param y y柱 目标柱(B)
* @param z z柱 中转柱(C)
* 其中 A B C 只是作为辅助思考
*/
public void hanoi(int n, char x ,char y ,char z){
//H(0)=0
if (n==0){
//什么也不做
}else {
//递推公式：H(n)=H(n-1) + 1 + H(n-1)
//将n-1个圆盘从x移动到z,y为中转柱
hanoi(n-1,x,z,y); //----------------------->解出n-1层汉诺塔:H(n-1)
//移动最大圆盘到目的柱
System.out.println(x+"->"+y);//------------> 1
//将n-1个圆盘从z移动到y,x为中转柱
hanoi(n-1,z,y,x);//------------------------>解出n-1层汉诺塔:H(n-1)
}
}
/**
* @param n 汉诺塔的层数
* @param x x柱 起点柱(A)
* @param y y柱 目标柱(B)
* @param z z柱 中转柱(C)
* 其中 A B C 只是作为辅助思考
*/
public int hanoiCount(int n, char x ,char y ,char z){
int moveCount=0;
//H(0)=0
if (n==0){
//什么也不做
return 0;
}else {
//递推公式：H(n)=H(n-1) + 1 + H(n-1)
//将n-1个圆盘从x移动到z,y为中转柱
moveCount += hanoiCount(n-1,x,z,y); //------------->解出n-1层汉诺塔:H(n-1)
//移动最大圆盘到目的柱
moveCount += 1; //---------------------------------> 1
//将n-1个圆盘从z移动到y,x为中转柱
moveCount +=hanoiCount(n-1,z,y,x);//--------------->解出n-1层汉诺塔:H(n-1)
}
return moveCount;
}
//测试
public static void main(String[] args){
HanoiRecursion hanoi=new HanoiRecursion();
System.out.println("moveCount="+hanoi.hanoiCount(6,‘A‘,‘B‘,‘C‘));
hanoi.hanoi(3,‘A‘,‘B‘,‘C‘);
}
}/**
*Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
*/
public void hanoi(int n, char x ,char y ,char z){
//H(0)=0
if (n==0){
//什么也不做
}else {
//调用自身函数hanoi()
hanoi(n-1,x,z,y);
//移动最大圆盘到目的柱
System.out.println(x+"->"+y);
//调用自身函数hanoi()
hanoi(n-1,z,y,x);
}
}递归的定义
递归的定义(从数学的角度)：用一个概念的本身直接定义自己。如阶乘函数F(n)=n!可以定义为： 
上一篇：内排序算法的整理（一）
下一篇：python3学习(1)