对于传统的汉诺塔游戏我们做一个拓展，我们有从大到小放置的n个圆盘，开始时所有圆盘都放在左边的柱子上，按照汉诺塔游戏的要求我们要把所有的圆盘都移到右边的柱子上，请实现一个函数打印最优移动轨迹。
给定一个int n，表示有n个圆盘。请返回一个string数组，其中的元素依次为每次移动的描述。描述格式为： move
from [left/mid/right] to [left/mid/right]。
测试样例：
1
返回：move from left to right
import java.util.*;
public class Hanoi {
private String[] pos = {"left", "mid", "right"};
public ArrayList getSolution(int n) {
return getSolution(n, 0, 2);
}
public ArrayList getSolution(int n, int from, int to) {
if(n==0) return new ArrayList();
ArrayList list = getSolution(n-1, from, 3-from-to);
list.add("move from "+pos[from]+" to "+pos[to]);
list.addAll(getSolution(n-1, 3-from-to, to));
return list;
}
}
先把三个柱子编码0，1，2。
假设我们从柱子x向柱子y移动n个盘，由于大的不能放小的上面，所以移动最下面一个的时候前面n-1个一定按顺序排在第三个柱子（编码为3-x-y）上，将最后一个从x移到y，再把3-x-y上的全移动到y。递归得到答案。
