数据结构与算法@汉诺塔

发表于 | 分类于 | 评论数： | 阅读次数：

概述

有三根相邻的柱子，标号为 A,B,C，A 柱子上从下到上按金字塔状叠放着 n 个不同大小的圆盘，要把所有盘子一个一个移动到柱子 B 上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动，设移动次数为 H(n）。
汉诺塔玩具模型图

详述

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
function towerOfHanoi(
  plates,
  source,
  helper,
  dest,
  sourceName,
  helperName,
  destName,
  moves = []
) {
  if (plates <= 0) {
    return moves;
  }
  if (plates === 1) {
    dest.push(source.pop());
    const move = {};
    move[sourceName] = source.toString();
    move[helperName] = helper.toString();
    move[destName] = dest.toString();
    moves.push(move);
  } else {
    towerOfHanoi(
      plates - 1,
      source,
      dest,
      helper,
      sourceName,
      destName,
      helperName,
      moves
    );
    dest.push(source.pop());
    const move = {};
    move[sourceName] = source.toString();
    move[helperName] = helper.toString();
    move[destName] = dest.toString();
    moves.push(move);
    towerOfHanoi(
      plates - 1,
      helper,
      source,
      dest,
      helperName,
      sourceName,
      destName,
      moves
    );
  }
  return moves;
}

function hanoiStack(plates) {
  const source = new Stack2();
  const dest = new Stack2();
  const helper = new Stack2();

  for (let i = plates; i > 0; i--) {
    source.push(i);
  }

  return towerOfHanoi(plates, source, helper, dest, "source", "helper", "dest");
}

// function hanoi0(plates, source, helper, dest, moves = []) {
//   if (plates <= 0) {
//     return moves;
//   }
//   if (plates === 1) {
//     moves.push([source, dest]);
//   } else {
//     hanoi(plates - 1, source, dest, helper, moves);
//     moves.push([source, dest]);
//     hanoi(plates - 1, helper, source, dest, moves);
//   }
//   return moves;
// }

function hanoi(n, x, y, z, moves = []) {
  let move = function(id, from, to) {
    console.log(id + "号盘从" + from + "移动到" + to);
    moves.push([from, to]);
  };
  if (n > 0) {
    hanoi(n - 1, x, z, y, moves);
    move(n, x, z);
    hanoi(n - 1, y, x, z, moves);
  }
  return moves;
}

console.log(hanoiStack(3));
console.log(hanoi(3, "A", "B", "C"));

参考