iT邦幫忙

2022 iThome 鐵人賽

DAY 27
0

https://ithelp.ithome.com.tw/upload/images/20220927/20151917lbDiiPyTYM.jpg

import java.util.Scanner;

public class TowersOfHanoi {

  /**
   * Main method
   */
  public static void main(String[] args) {
    // Create a Scanner
    Scanner input = new Scanner(System.in);
    System.out.print("Enter number of disks: ");
    int n = input.nextInt();

    // Find the solution recursively
    System.out.println("The moves are:");
    moveDisks(n, 'A', 'B', 'C');
  }

  /**
   * The method for finding the solution to move n disks from fromTower to toTower with auxTower
   */
  public static void moveDisks(int n, char fromTower,
      char toTower, char auxTower) {
    if (n == 1) // Stopping condition
    {
      System.out.println("Move disk " + n + " from " +
          fromTower + " to " + toTower);
    } else {
      moveDisks(n - 1, fromTower, auxTower, toTower);
      System.out.println("Move disk " + n + " from " +
          fromTower + " to " + toTower);
      moveDisks(n - 1, auxTower, toTower, fromTower);
    }
  }
}

時間複雜度O(2^n)
https://ithelp.ithome.com.tw/upload/images/20220927/201519176Qm8MjBUFL.png
透過第一張圖可知主要分為三個步驟:

  1. 將A柱的n-1個disk移到C柱(中繼站) => T(n-1)
  2. 將A柱最大盤子移到B柱 => T(1)
  3. 將C柱的n-1個disk移到B柱 => T(n-1)

而2^n-1可計算出當n個disk要移動2^n-1次才能完成任務


上一篇
Codewars|Find the missing letter
下一篇
Call by value|Call by reference
系列文
寫寫歷年職場經歷過的大小事或近期所學習的知識啟發30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言