数据结构与算法之汉诺塔问题（Java递归）

yuxue 发布于2019-08-16 15:51 / 657人阅读

摘要：汉诺塔问题有三根柱子，源杆，暂存杆，目的杆上有层盘子，由小到大向下排列，现需要将杆的盘子移到杆中要求大的盘在下面，小的盘在上面一次只能移动一个盘子个人思路先分析问题，用数学的归纳法当只有一个盘时，直接移动当有两个盘时，先将小的移到暂存杆，再

汉诺塔问题：

有三根柱子，源杆A，暂存杆temp，目的杆C A上有n层盘子，由小到大向下排列，现需要将A杆的盘子移到C杆中

       要求：1）大的盘在下面，小的盘在上面
             2）一次只能移动一个盘子
             
         个人思路：先分析问题，用数学的归纳法
                 当只有一个盘时，直接移动；
                 当有两个盘时，先将小的移到暂存杆，再将大的移到目的杆C，最后将暂存杆temp的小盘移到目的杆C中；
                 当有三个盘时，在下面的代码中的注释中写有详细步骤
                 ......
                 n个盘时，把它看做两部分一是上面的（n-1）盘，二是第n个盘，先将（n-1）首先将上面的（n-1）个盘子从A杆借助C杆移至temp杆，其次剩下第n个盘，直接放至C杆，最后一次递归调用解决即可。
                 
                 其中汉诺塔层数可以由程序内存储读取或者键盘输入，c为程序计数器，计算移动盘的次数

import java.util.Scanner;

public class Hanoi {
    int c=0;//计数器，计算移动的次数
    public void moveone(int n, String A, String C) {
        System.out.println("move  " + n + "  from  " + A + "     to  " + C);
    }

    public void movesome(int n, String A, String temp, String C) {

        c++;
    
        if (n <= 0) {
            System.out.println("number error");
            return;
        } else if (n == 1) {
            moveone(n, A, C);
        } else {
            movesome(n - 1, A, C, temp);
            // 首先将上面的（n-1）个盘子从A杆借助C杆移至temp杆
            moveone(n, A, C);
            // 然后将编号为n的盘子从A杆移至C杆
            movesome(n - 1, temp, A, C);
//            将剩下的（n-1）个盘子从temp杆借助A杆移至C杆
        }
        //草稿纸上手写汉诺塔三层的实现
//        moveone(1,A,C);
//        moveone(2,A,temp);
//        moveone(1,C,temp);
//        moveone(3, A, C);
//        moveone(1, temp, A);
//        moveone(2, temp, C);
//        moveone(1, A, C);

    }

    public static void main(String[] args) {
       //层数
        System.out.println("请输入汉诺塔层数:");
        Scanner input =new Scanner(System.in);
                int  in=input.nextInt();
                int l = 3;

        Hanoi h = new Hanoi();
        //    h.moveone(l,A,C);//程序内存储读取
        h.movesome(in, "初始位置", "临时存放地", "目的地址");
        System.out.println("汉诺塔的实现需要的移动次数:"+h.c);

//        h.movesome(l, "初始位置", "临时存放地", "目的地址");

    }
}

程序运行结果：

GPU云服务器云服务器简单汉诺塔c语言算法汉诺塔汉诺塔 python 汉诺塔c语言讲解

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73732.html

经典算法：汉诺塔

摘要：学编程，学，算法也是必不可缺的，这一次给大家带来一个经典的递归算法题，汉诺塔。当我们把层都搬到了中间柱的时候，只需要把最大的那个盘，从搬到柱就好了，剩下的怎么办呢柱永远是目标柱，我们不需要去移动它。学编程，学IT，算法也是必不可缺的，这一次给大家带来一个经典的递归算法题，汉诺塔。算是算法的入门小题目之一吧~ 视频教程什么是汉诺塔？我这里直接拉来一个图解释一下（挂了请联系我）sho...

Lin_R 2019-07-31 11:17 评论0 收藏0
经典算法：汉诺塔

摘要：学编程，学，算法也是必不可缺的，这一次给大家带来一个经典的递归算法题，汉诺塔。当我们把层都搬到了中间柱的时候，只需要把最大的那个盘，从搬到柱就好了，剩下的怎么办呢柱永远是目标柱，我们不需要去移动它。学编程，学IT，算法也是必不可缺的，这一次给大家带来一个经典的递归算法题，汉诺塔。算是算法的入门小题目之一吧~ 视频教程什么是汉诺塔？我这里直接拉来一个图解释一下（挂了请联系我）sho...

AWang 2019-08-23 12:40 评论0 收藏0
汉诺塔问题

摘要：概述汉诺塔是一个经典的递归问题，虽说看人家写好的算法程序就那么几行，但着实理解有一定的难度。查阅了一些资料，参阅别人的思路，对汉诺塔算法进行一番梳理。问题来源有一个梵塔，塔内有三个座，座上有若干个盘子，盘子大小不等，大的在下，小的在上如图。概述汉诺塔是一个经典的递归问题，虽说看人家写好的算法程序就那么几行，但着实理解有一定的难度。查阅了一些资料，参阅别人的思路，对汉诺塔算法进行一番...

RayKr 2019-08-14 15:11 评论0 收藏0
递归就这么简单

摘要：那么，有了循环，为什么还要用递归呢在某些情况下费波纳切数列，汉诺塔，使用递归会比循环简单很多很多话说多了也无益，让我们来感受一下递归吧。递归介绍本来预算此章节是继续写快速排序的，然而编写快速排序往往是递归来写的，并且递归可能不是那么好理解，于是就有了这篇文章。在上面提到了递归这么一个词，递归在程序语言中简单的理解是：方法自己调用自己递归其实和循环是非常像的，循环都可以改写成递归...

dreamtecher 2019-08-15 14:51 评论0 收藏0
从“数学归纳法”到理解“递归算法”！

摘要：前言相信大家在面试或者工作中偶尔会遇到递归算法的提问或者编程，我们今天来聊一聊从数学归纳法到理解递归算法。这种广义的数学归纳法应用于数学逻辑和计算机科学领域，称作结构归纳法。 showImg(https://img-blog.csdnimg.cn/20190426221838971.gif);showImg(https://img-blog.csdnimg.cn/20190429222...

oogh 2019-08-16 17:05 评论0 收藏0