hanoi汉诺塔问题的真谛

首先这是个递归问题，要解决n层的汉诺塔问题需要先解决n-1层的汉诺塔问题，依次类推，最终就能解决问题n层汉诺塔问题了！他可以类比以递归的方式求解 n!  的问题。要求解 f(n)=n! 需要先求解 f(n-1)；因为 f(n) = n * f(n-1)（这样说谁都知道，价值不大，O(∩_∩)O）。

第一步：要先解决  n  层的汉诺塔问题，要将  n-1 层的汉诺塔从A柱经C柱转移到 B柱，其本身也是一个递归问题；

第二步：需要将汉诺塔的第n层从A柱转移到C柱（）（注意：是第n层，只是那一个圆饼，不是“n 层”，n个圆饼）。

第三步：现在的情况是B柱上有n-1层的汉诺塔（n-1个圆饼），C柱上只有一个，A柱为空；这就是另一个循环开始的地方（）

汉诺塔问题算法

Java版本

public class Hanoilmpl {


    public void hanoi(int n, char A, char B, char C) {
        if (n == 1) {
            move(A, C);
        } else {
            hanoi(n - 1, A, C, B);//步骤1 按ACB数序执行N-1的汉诺塔移动
            move(A, C);             //步骤2   执行最大盘子移动
            hanoi(n - 1, B, A, C);//步骤3 按BAC数序执行N-1的汉诺塔移动
        }
    }

    private void move(char A, char C) {//执行最大盘子的从A-C的移动
        System.out.println("move:" + A + "--->" + C);
    }

    public static void main(String[] args) {
        Hanoilmpl hanoi = new Hanoilmpl();
        System.out.println("移动汉诺塔的步骤：");
        hanoi.hanoi(3, 'a', 'b', 'c');
    }
}

 

Python版本

def move(n, a, b, c):
    if n == 1:
        print(a,'->',c)
    else:
        move(n-1, a, c, b) 
        print(a, '->', c) 
        move(n-1, b, a, c) 
move(3,'A','B','C')