汉诺塔

2023-05-26

hanoi

最近儿子小学在教汉诺塔，在旁边看着他一遍遍的挑战，让我回想起了这是刚学编程时经典的算法问题。为了在儿子小小的心灵埋下编程思想的种子，就抽时间写了个解决汉诺塔问题的网页。

规则

汉诺塔有三个塔柱，我们分别命名为A、B、C，初始A柱上有n个圆盘，圆盘从上向下由小到大堆放，目的是要把A塔上的圆盘全部移到C塔上，一次只能移动一个圆盘，并且始终只能小的圆盘放在大的圆盘上

汉诺塔问题其实很像把大象装进冰箱分几步这个问题

  1. 打开冰箱门
  2. 把大象放进去
  3. 关上冰箱门

解决汉诺塔问题也分为三步

  1. 把A塔从上到下的n-1个圆盘当作一个整体移动到B塔
  2. 把A塔上第n个圆盘移动到C塔
  3. 把B塔上的圆盘整体移动到C塔 然后在移动n-1这个整体的时候，就把它看成和初始状态一样，重复这三个步聚，直至上面n-1个圆盘为1时，直接移动即可

为了更容易理解，我以三个圆盘为例，用图形来表示上述过程

初始目标

20230526171151

步骤1

20230526162734

步骤2

20230526162714

步骤3

20230526162643

但其中步骤一和步骤三都是把多个圆盘看成一个整体，因此不能直接移动，需要对这两个步骤继续拆分

步骤1目标

20230526165348

步骤1.1

20230526164828

步骤1.2

20230526165513

步骤1.3

20230526172640

步骤3目标

20230526172124

步骤3.1

20230526172101

步骤3.2

20230526162734

步骤3.3

20230526172139

然后我们把拆分后的步骤依次代入步骤1 -> 步骤2 -> 步骤3

步骤1

  1. A -> C
  2. A -> B
  3. C -> B

步骤2

  1. A -> C

步骤3

  1. B -> A
  2. B -> C
  3. A -> C

所以最终的结果就是

  1. A -> C
  2. A -> B
  3. C -> B
  4. A -> C
  5. B -> A
  6. B -> C
  7. A -> C

用typescript简单实现了一下

export interface IStep<T> {
  source: T;
  dest: T;
}
export interface IResult<T> {
  totalSteps: number;
  steps: IStep<T>[];
}

export default class TowerOfHanoi<T> {
  protected numOfDisks: number;
  protected towerA: T;
  protected towerB: T;
  protected towerC: T;
  protected totalSteps: number;
  protected steps: IStep<T>[];

  constructor (numOfDisks: number, towerA: T, towerB: T, towerC: T) {
    this.numOfDisks = numOfDisks
    this.towerA = towerA
    this.towerB = towerB
    this.towerC = towerC
    this.totalSteps = 0
    this.steps = []
  }

  start (): IResult<T> {
    this.reset()
    this.next(this.numOfDisks, this.towerA, this.towerB, this.towerC)

    return {
      totalSteps: this.totalSteps,
      steps: this.steps
    }
  }

  protected reset (): void {
    this.totalSteps = 0
    this.steps = []
  }

  protected next (numOfDisks: number, source: T, helper: T, dest: T): void {
    if (numOfDisks === 1) {
      this.move(source, dest)
      return
    }
    this.next(numOfDisks - 1, source, dest, helper)
    this.move(source, dest)
    this.next(numOfDisks - 1, helper, source, dest)
  }

  protected move (source: T, dest: T): void {
    this.totalSteps += 1
    this.steps.push({ source, dest })
  }
}

用vue写了个图形化的示例，代码仓库https://github.com/tonliver/fun/tree/master有兴趣的同学可以自行去看

|- src
|-- views
|--- hanoi
|---- index.vue 图形界面
|---- TowerOfHanoi.ts 汉诺塔算法类

hanoi-demo