遞迴—河內塔 - 筆記長也

遞迴—河內塔

2018-03-04 14:33:17   資料結構

河內塔

一般河內塔有三個柱子,與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
        }
    }
    
  }
}

關於作者


長也

資管菸酒生,嘗試成為網頁全端工程師(laravel / React),技能樹成長中,閒暇之餘就寫一些筆記。 喔對了,也愛追一些劇,例如火神跟遺物整理師,推推。最愛的樂團應該是告五人吧(?)