數據結構與算法之漢諾塔問題（Java遞歸）

yuxue 發布于2019-08-16 15:51 / 725人閱讀

摘要：漢諾塔問題有三根柱子，源桿，暫存桿，目的桿上有層盤子，由小到大向下排列，現需要將桿的盤子移到桿中要求大的盤在下面，小的盤在上面一次只能移動一個盤子個人思路先分析問題，用數學的歸納法當只有一個盤時，直接移動當有兩個盤時，先將小的移到暫存桿，再

漢諾塔問題：

有三根柱子，源桿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語言講解

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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