遞迴—河內塔

河內塔

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