#牛客堂视频直播#汉诺塔问题（2015.7.15）

【题目】 给定一个整数n，代表汉诺塔游戏中从小到大放置的n个圆盘，假设开始时所有圆盘都放在左边的柱子上，想按照汉诺塔游戏的要求把所有圆盘都移到右边的柱子上。实现函数打印最优移动轨迹。 【举例】 n=1时，打印： move from left to right n=2时，打印： move from left to mid move from left to right move from mid to right 【进阶题目】 给定一个整型数组arr其中只含有1、2和3，代表所有圆盘目前的状态，1代表左柱，2代表中柱，3代表右柱，arr[i]的值代表第i+1个圆盘的位置。比如，arr=[3,3,2,1]，代表第1个圆盘在右柱上、第2个圆盘在右柱上、第3个圆盘在中柱上、第4个圆盘在左柱上。如果arr代表的状态是最优移动轨迹过程中出现的状态，返回arr这种状态是最优移动轨迹中的第几个状态。如果arr代表的状态不是最优移动轨迹过程中出现的状态，则返回-1。 【举例】 arr=[1,1]。两个圆盘目前都在左柱上，也就是初始状态，所以返回0。 arr=[2,1]。第一个圆盘在中柱上、第二个圆盘在左柱上，这个状态是2个圆盘的汉诺塔游戏中，最优移动轨迹的第1步，所以返回1。 arr=[3,3]。第一个圆盘在右柱上、第二个圆盘在右柱上，这个状态是2个圆盘的汉诺塔游戏中，最优移动轨迹的第3步，所以返回3。 arr=[2,2]。第一个圆盘在中柱上、第二个圆盘在中柱上，这个状态是2个圆盘的汉诺塔游戏中，最优移动轨迹从来不会出现的状态，所以返回-1。 【进阶题目要求】 如果arr长度为N，请实现时间复杂度O(N)，额外空间复杂度O(1)的方法。 【难度】 校★★★☆ 【解答】 原问题。假设有from柱子、mid柱子和to柱子，都在from的圆盘1~i完全移动到to，最优过程为。步骤1为圆盘1~i-1从from移动到mid，步骤2为单独把圆盘i从from移动到to，步骤3为把圆盘1~i-1从mid移动到to。如果圆盘只有1个，直接把这个圆盘从from移动到to即可。打印最优移动轨迹的方法参见如下代码中的hanoi方法。 public void hanoi(int n) { if (n > 0) { func(n, "left", "mid", "right"); } } public void func(int n, String from, String mid, String to) { if (n == 1) { System.out.println("move from " + from + " to " + to); } else { func(n - 1, from, to, mid); func(1, from, mid, to); func(n - 1, mid, from, to); } } 进阶题目。首先求都在from柱子上的圆盘1~i，如果都移动到to上的最少步骤数，假设为S(i)。根据上面的步骤，S(i)=步骤1的步骤总数+1+步骤3的步骤总数=S(i-1)+1+S(i-1)，S(1)=1。所以S(i)+1=2*(S(i-1)+1)，S(1)+1==2。根据等比数列求和公式得到S(i)+1=2^i，所以S(i)=2^i-1。 对于数组arr来说，arr[N-1]表示最大圆盘N在哪个柱子上，情况有以下三种： 1，圆盘N在左柱上，说明步骤1或者没有完成或者已经完成，需要考察圆盘1~N-1的状况。 2，圆盘N在右柱上，说明步骤1已经完成，起码走完了2^(N-1)-1步。步骤2也已经完成，起码又走完了1步，所以当前状况起码是最优步骤的2^(N-1)步，剩下的步骤怎么确定还得继续考察圆盘1~N-1的状况。 3，圆盘N在中柱上，这是不可能的，最优步骤中不可能让圆盘N处在中柱上，直接返回-1。 所以整个过程可以总结为，对于圆盘1~i来说，如果目标为从from到to，那么情况有三种： 1，圆盘i在from上，需要继续考察圆盘1~i-1的状况，圆盘1~i-1的目标为从from到mid。 2，圆盘i在to上，说明起码走完了2^(i-1)步，剩下的步骤怎么确定还得继续考察圆盘1~i-1的状况，圆盘1~i-1的目标为从mid到to。 3，圆盘i在mid上，直接返回-1。 整个过程参看如下代码中的step1方法。 public int step1(int[] arr) { if (arr == null || arr.length == 0) { return -1; } return process(arr, arr.length - 1, 1, 2, 3); } public int process(int[] arr, int i, int from, int mid, int to) { if (i == -1) { return 0; } if (arr[i] != from && arr[i] != to) { return -1; } if (arr[i] == from) { return process(arr, i - 1, from, to, mid); } else { int rest = process(arr, i - 1, mid, from, to); if (rest == -1) { return -1; } return (1 << i) + rest; } } step1方法是递归函数，递归最多调用N次，并且每步的递归函数再调用递归函数的次数最多一次。在每个递归过程中，除去递归调用的部分，剩下过程的时间复杂度为O(1)，所以step1方法的时间复杂度为O(N)。但是因为递归函数需要函数栈的关系，step1方法的额外空间复杂度为O(N)，所以为了达到题目的要求，需要将整个过程改成非递归的方法，具体请参看如下代码中的step2方法。 public int step2(int[] arr) { if (arr == null || arr.length == 0) { return -1; } int from = 1; int mid = 2; int to = 3; int i = arr.length - 1; int res = 0; int tmp = 0; while (i >= 0) { if (arr[i] != from && arr[i] != to) { return -1; } if (arr[i] == to) { res += 1 << i; tmp = from; from = mid; } else { tmp = to; to = mid; } mid = tmp; i--; } return res; }

 错过了。。。。郁闷啊，请问什么时候再开？

请问您的书什么时候出版？现在貌似还买不到。。如果有kindle版的就好了，因为我不在国内，没有也不要紧，我让国内的朋友买了再邮到我这边

视频漏掉讲述step2代码的部分啊。虽然也能自己看懂，但理解不够深。。。

请问当圆盘i在to上时，最起码已经走完了2^(i-1)步，但是为什么返回2^i?