Java教程

用递归的办法神奇的解决汉诺塔问题

本文主要是介绍用递归的办法神奇的解决汉诺塔问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

汉诺塔问题

汉诺塔问题
汉诺塔问题,这个名词我们可能不熟悉,但是观看上图我们很可能都曾经了解过甚至玩过,他的规则就是有3根柱子A,B,C。A柱子上由上至下依次由小至大排列的圆盘。把A柱子上的圆盘借B柱子全部移动到C柱子上,并且移动的过程始终是小的圆盘在上,大的在下。
我们用递归的方式来解这道题,先来定义一个函数

public void hanoi(int n, char A, char B, char C)

他表示的是把n个圆盘从A借助B成功的移动到C。
递归的条件,一个是终止条件,一个是递归调用自己。
首先是终止条件:当n等于1的时候,也就是A柱子上只有一个圆盘的时候,我们直接把A柱子上的圆盘移动到C柱子上即可。

if(n==1){
            System.out.println("从"+A+"移动到"+C);
            return;
        }

然后是递归调用自己
如果n不等于1,我们要分3步,
1、先把n-1个圆盘从A借助C成功的移动到B
2、然后再把第n个圆盘从A移动到C
3、最后再把n-1个圆盘从B借助A成功的移动到C

hanoi(n, ‘A’, ‘B’, ‘C’)表示的是把n个圆盘从A借助B成功的移动到C
所以hanoi(n-1, ‘A’, ‘C’, ‘B’)就表示的是把n-1个圆盘从A借助C成功的移动到B
hanoi(n-1, ‘B’, ‘A’, ‘C’)就表示的是把n-1个圆盘从B借助A成功的移动到C
所以上面3步如果用代码就可以这样来表示
1,hanoi(n-1, ‘A’, ‘C’, ‘B’)
2,System.out.println(“从” + A + “移动到” + C);
3,hanoi(n-1, ‘B’, ‘A’, ‘C’)
最终代码如下:

public static void hanoi(int n,char A,char B,char C){
        if(n==1){
            System.out.println("从"+A+"移动到"+C);
            return;
        }
        hanoi(n-1,A,C,B);
        System.out.println("从"+A+"移动到"+C);
        hanoi(n-1,B,A,C);
    }

然后实际测试:
在这里插入图片描述
测试结果:
在这里插入图片描述
你可以实操一下,一定是可以成功的。
一个自己可能玩很久都成功不了的游戏,只要了解递归,就能用计算机轻松完成,是不是很神奇!

这篇关于用递归的办法神奇的解决汉诺塔问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!