面试题 08.06. 汉诺塔问题

n = 1 时，直接把盘子从 A 移到 C； //n > 1 时，
先把上面 n - 1 个盘子从 A 移到 B（子问题，递归）；
再将最大的盘子从 A 移到 C；
再将 B 上 n - 1 个盘子从 B 移到 C（子问题，递归）。

  1. class Solution {
  2.     public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
  3.         int n=A.size();
  4.         hannoi(n,A,B,C);
  5.     }
  7.     public void hannoi(int n, List<Integer> A, List<Integer> B, List<Integer> C){
  8.         if(n == 1){
  9.             move(A, C);
  10.         }else{
  11.             hannoi(n-1, A, C, B);
  12.             move(A, C);
  13.             hannoi(n-1, B, A, C);
  14.         }
  15.     }
  17.     public void move(List<Integer> from, List<Integer> to){
  18.         Integer item=from.get(from.size()-1);
  19.         to.add(item);
  20.         from.remove(from.size()-1);
  21.     }
  22. }