Java基础语法（汉罗塔）

• 1 起源
• 2 需求
• 3 分析
• • 3.1 1个碟子
  • 3.2 2个碟子
  • 3.3 3个碟子
  • 3.4 4个碟子
  • 3.5 规律
• 4 代码实现：直接算法
• 5 代码实现封装：栈的思想

汉罗塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

将汉罗塔问题抽象到数学：

• 1.有三根杆子 A,B,C；
• 2.A 杆上有若干大小不同的碟子，从上往下越来越大；
• 3.每次移动一块碟子,小的只能叠在大的上面；
• 4.把所有碟子从 A 杆全部移到 C 杆上。

• 确定 A 柱子上的初始碟子：int disks = 3;
• 确定三个容器 char ‘A’、char ‘B’、char ‘C’；
• 初始确定移动方法，从 from --> to：hanrotaMove(int disks, char from, char index, char to)。

A 柱子上只有一个碟子时，直接移动到 C：

在上述前 4个下不难发现有规律存在：
A 柱子上有 n 个碟子，移动步骤便以 n 分为上下两部分，且上部分移动的数与下部分移动的数相同，此处便有递归分治的思想，解析 4 个碟子：

在初始入参：from ‘A’ - index ‘B’ - to ‘C’ 下，每一级都做为下一级分支的入参，且每个分支的上部都有相同的步骤“换”：from-to-index，每个分支的下部也都有相同的步骤“换”：index-from-to，可将此图看为完全二叉树。

代码常规实现：Hanrota.java

public class Hanrota {
    
    public static void main(String[] args) {
        // 初始化一个 A 柱子上碟子数
        int disks = 4;
        hanrotaMove(disks, 'A', 'B', 'C');
    }

    
    public static void hanrotaMove(int disks, char from, char index, char to){
        if (disks <= 0){
            System.out.println("碟子数量不足");
        } else if (disks == 1) {
            System.out.println("Disk " + disks + " from " + from + " to " + to);
        } else {
            // 递归上部分
            hanrotaMove(disks - 1, from, to, index);
            // 中间分隔点
            System.out.println("Disk " + disks + " from " + from + " to " + to);
            // 递归下部分
            hanrotaMove(disks - 1, index, from, to);
        }
    }
}

运行结果：

Disk 1 from A to B
Disk 2 from A to C
Disk 1 from B to C
Disk 3 from A to B
Disk 1 from C to A
Disk 2 from C to B
Disk 1 from A to B
Disk 4 from A to C
Disk 1 from B to C
Disk 2 from B to A
Disk 1 from C to A
Disk 3 from B to C
Disk 1 from A to B
Disk 2 from A to C
Disk 1 from B to C

汉罗塔的移动存储很像栈的思想：先进后出。

就是在上一步的代码实现：直接算法上封装一下。

首先要 java 实现一个栈，再递归分治解决汉罗塔移动：MyStack.java

package com;


public class MyStack {
    
    private int maxSize;
    
    private long[] stackArray;
    
    private int top;

    
    public MyStack(int s) {
        maxSize = s;
        stackArray = new long[maxSize];
        top = -1;
    }

    
    public void push(long j) {
        stackArray[++top] = j;
    }

    
    public long pop() {
        return stackArray[top--];
    }

    
    public long peek() {
        return stackArray[top];
    }

    
    public boolean isEmpty() {
        return (top == -1);
    }

    
    public boolean isFull() {
        return (top == maxSize - 1);
    }

    
    public int size(){
        return top + 1;
    }

    
    public static void main(String[] args) {
        // 初始化栈空间
        int topN = 3;
        // 初始化 A 栈空间
        MyStack A = new MyStack(topN);
        // 初始化 B 栈空间
        MyStack B = new MyStack(topN);
        // 初始化 C 栈空间
        MyStack C = new MyStack(topN);

        // 给 A 栈添加汉罗塔数
        A.push(13);
        A.push(9);
        A.push(4);

        // 汉罗塔移动
        hanrotaMove(A.size(),A,B,C);

        // 打印 C 栈元素
        while (!C.isEmpty()){
            System.out.print(C.pop() + " ");
        }

    }

    
    public static void hanrotaMove(int disks, MyStack A, MyStack B, MyStack C){
        if (disks <= 0){
            System.out.println("A 柱子上没有数据");
        } else if (disks == 1) {
            // A 中出栈
            long value = A.pop();
            System.out.println("Disk " + value + " from " + A + " to " + C);
            // C 中入栈
            C.push(value);
        } else {
            // 递归上部
            hanrotaMove(disks - 1, A, C, B);
            // A 中出栈
            long value = A.pop();
            System.out.println("Disk " + value + " from " + A + " to " + C);
            // C 中入栈
            C.push(value);
            // 递归下部
            hanrotaMove(disks - 1, B, A, C);
        }
    }
}

运行结果：

Disk 4 from com.MyStack@74a14482 to com.MyStack@1540e19d
Disk 9 from com.MyStack@74a14482 to com.MyStack@677327b6
Disk 4 from com.MyStack@1540e19d to com.MyStack@677327b6
Disk 13 from com.MyStack@74a14482 to com.MyStack@1540e19d
Disk 4 from com.MyStack@677327b6 to com.MyStack@74a14482
Disk 9 from com.MyStack@677327b6 to com.MyStack@1540e19d
Disk 4 from com.MyStack@74a14482 to com.MyStack@1540e19d
4 9 13