遞迴—河內塔 - notesHazuya筆記長也

遞迴—河內塔

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
        }
    }
    
  }
}


長也

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