汉诺塔递归算法Java实现

雨点打透心脏的1/2处 2023-10-17 21:47 40阅读 0赞

## 问题 ##

有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一个一个移动到柱子B上，并且每次移动后，同一根柱子上都不能出现大盘子在小盘子上方；用代码打印出移动过程。

## 1.问题分析 ##

规则：每次移动，同一根柱子上都不能出现，小盘在大盘上方；

现在假设：A柱有三个盘，按金字塔状叠放；

目标：将A柱三个盘子全部移动到B柱中；

**其中必定存在下图所示的状态：**

![c70fb15775034f0e8174aa2723a7308c.png][]

**整个问题：可以必然可以分解为下面的3过程：**

*  1、将A柱2个盘子移动到C柱；
 *  2、将A柱1个盘子移动到B柱；
 *  3、将C柱2个盘子移动到B柱；

## 2.函数表达式 ##

**将3个盘子：从A柱 移动到 B柱 借助 C柱；用函数表示：f(3,A,B,C);**

**函数各个参数含义：f(盘子数，原柱，目标柱，借助柱)；**

上面分解的过程替换成函数：

**1、将A柱2个盘子移动到C柱；**

*  f(2,A,C,B);

**2、将A柱1个盘子移动到B柱；**

*  f(1,A,B,C)；

**3、将C柱2个盘子借助A柱移动到B柱；**

*  f(2,C,B,A);

函数关系式：**f(3,A,B,C)=f(2,A,C,B)+f(1,A,B,C)+f(2,C,B,A);**

推广到n的情况：

**f(n,A,B,C)=f(n-1,A,C,B)+f(1,A,B,C)+f(n-1,C,B,A);**

代码实现：

/**A/B/C分别代表三个柱子,n代表A柱子上的盘子数*/
    	public void f(int n,char A,char B,char C) {
    		
    		if(n == 1) {
    			System.out.println("move:"+A+"->"+B);
    			return;
    		}		
    		f(n-1,A,C,B);
    		f(1,A,B,C);
    		f(n-1,C,B,A);		
    	}

这个解法到现在看来仍然觉得很巧，虽然效率不高也可能stackOverflow，但这种解法本身是极具美感的。

[c70fb15775034f0e8174aa2723a7308c.png]: https://img-blog.csdnimg.cn/c70fb15775034f0e8174aa2723a7308c.png

发表评论取消回复

表情：

评论列表（有 0 条评论，40人围观）

还没有评论，来说两句吧...

相关阅读

相关汉诺塔递归算法Java实现

问题有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一个一个移动到柱子B上，并且每次移动后，同一根柱子上都不能出现大

雨点打透心脏的1/2处/ 2023年10月17日 21:47/ 0 赞/ 41 阅读

相关递归实现汉诺塔程序

\[将汉诺塔\]这不是线性递归，这是个非线性递归! n=1 1 n=2 3 n=3 7 .................

小鱼儿/ 2023年03月13日 03:45/ 0 赞/ 74 阅读

相关递归算法与汉诺塔

递归算法与汉诺塔递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归算法是一种直接或者间接调

灰太狼/ 2023年02月14日 07:44/ 0 赞/ 15 阅读

相关 JAVA 递归汉诺塔

<strong><span style="font-size:18px;">汉诺塔：</span></strong> <strong><span style=

一时失言乱红尘/ 2022年07月19日 02:11/ 0 赞/ 223 阅读

相关【数据结构算法】递归：汉诺塔

汉诺塔游戏在汉诺塔游戏中，我们发现可以将问题简化，这是一种利用递归解决问题的思路，我们不需要具体解决问题的方法是什么，但仍然可以解决该问题，因此这种方法思想简单，但计算

你的名字/ 2022年05月21日 03:11/ 0 赞/ 205 阅读

相关 python实现汉诺塔(递归实现)

1. `def Hanoi(n,x,y,z):n为个数,xyz为盘子名称,x终点,y过程,z目的` 2. ` if n == 1:` 3. ` print(x,"--

布满荆棘的人生/ 2022年05月13日 10:44/ 0 赞/ 220 阅读

相关递归（汉诺塔）

> 算法思路：略 > > > > \ include <stdio.h> > void hanoi ( int n, char a, char b, char

àì夳堔傛蜴生んèń/ 2022年03月24日 21:10/ 0 赞/ 283 阅读

相关汉诺塔与递归算法

[http://www.cnblogs.com/zhangqqqf/archive/2008/09/12/1289730.html][http_www.cnblogs.com_

缺乏、安全感/ 2022年03月09日 05:20/ 0 赞/ 273 阅读

相关【Java】汉诺塔问题递归实现

import java.util.Scanner; public class 汉诺塔 { static void hannu

￡神魔★判官ぃ/ 2022年02月16日 07:31/ 0 赞/ 231 阅读

相关非递归&递归汉诺塔算法实践

汉诺塔算法是很多公司的面试题，经常会让手写，这里总结了一下 ![汉诺塔][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_

比眉伴天荒/ 2021年12月07日 10:17/ 0 赞/ 361 阅读