汉诺塔递归算法Java实现

雨点打透心脏的1/2处 2023-10-17 21:47 111阅读 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 条评论，111人围观）

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

相关阅读

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

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

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

相关汉诺塔——递归算法

一．起源：　　汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天

﹏ヽ暗。殇╰゛Y/ 2023年06月05日 08:21/ 0 赞/ 23 阅读

相关递归实现汉诺塔程序

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

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

相关递归---汉诺塔

【题目描述】约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移

怼烎@/ 2023年02月14日 13:12/ 0 赞/ 62 阅读

相关递归算法与汉诺塔

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

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

相关 JAVA 递归汉诺塔

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

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

相关递归（汉诺塔）

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

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

相关汉诺塔与递归算法

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

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

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

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

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

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

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

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