登入
首頁 所有文章 資料結構 遞迴—河內塔
長也   2018-03-04 14:33:17(1年前)    686點閱   0喜歡  0收藏
遞迴—河內塔  

河內塔

一般河內塔有三個柱子,與N個碟盤,要將N個碟盤由A柱移動至C柱,其規則如下:

1.一次只能搬動一個盤子

2.大盤子不可以疊在小盤子上面 (小盤子必須在大盤子上)

演算法

假設要移動n個碟盤:

a.當 n=1時,直接將碟盤由A移動至C

b.否則:

1.搬移n-1個碟盤,由A至B藉由C

2.搬移第n個碟盤,由A至C

3.搬移n-1個碟盤,由B至C藉由A

範例程式碼

import java.util.Scanner;
public class Basic_Hanoi {

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int inpui=input.nextInt();
        hanoi(inpui,'A','C','B'); //呼叫A 到 C
    }
    
    public static void  hanoi (int n,char from,char to,char aux){
        if (n==1){
            System.out.printf("Move %d from %c to %c\n",n,from,to); //一塊的時候直接移到C
        }
        else{
            hanoi(n-1,from,aux,to);//N-1盤子由A到B藉由C
            System.out.printf("Move %d from %c to %c\n",n,from,to); //
            hanoi(n-1,aux,to,from);//n-1個盤子由B藉由A到C
        }
    }
    
  }
}

本文作者:長也

糾結與想不開的資管系學生,之前常碰PHP,現在常碰到的是Python,閒暇之餘就記錄一些筆記。

             

如要發表回覆,請先 登入

  1則回覆
長也   回覆於2018-12-08 12:36:38
回覆  #1

補上Python程式碼:

def hanoi(n, a, b, c):

    if(n == 1):    # disk == 1, a to c

        print("Move {0} from {1} to {2}".format(n, a, c))

    else:

        hanoi(n - 1, a, c, b)    # a to b aux c
        print("Move {0} from {1} to {2}".format(n, a, c))
        hanoi(n - 1, b, a, c)    # b to c aux a


if __name__ == "__main__":
    hanoi(3, "A", "B", "C")     # call a to c aux b

我的思考方式:

函式的參數:(n, a, b, c),其中n是碟盤,a, b, c代表柱子,而呼叫該函式的意思是:從 a 藉由 b 到 c,所以一開始呼叫這個。

進入函式之後,若只有一個碟盤,則直接移動至c,若否:

  1. 我們看到a柱,可以發現要移動第三個碟盤時,要先將n - 1 及 n - 2 個碟盤移動至b,所以呼叫由 a 藉由 c 至 b
  2. 此時第三個碟盤可以直接由a移動至c
  3. 此時看到b柱會有兩個碟盤,若要將第二個碟盤移動至c,要先將第一個碟盤移動至a,因此呼叫b 至 c 藉由 a
  4. 我們再看到a柱,發現只有一個碟盤,可以直接移動至c。若只呼叫三個碟盤,動作已結束,若超過三個,則重複動作1.即可。