- gf24240 的博客
《梦溪笔谈·娱乐》卷八：汉诺塔问题
-
gf24240
LV 10
@
2025-7-23 23:28:50
背景
竟然已经连续发了五篇笔记了。
这是在某站找哈夫曼树时看到的（这有什么关系吗？）
汉诺塔问题我们都熟悉：大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？
如果要输出具体操作的话，六十四还是太多了。这里是八个盘子的举例（共 步）：
详情
第 1 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 2 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 3 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 4 步：把第 3 个盘子从 A 柱子移到 B 柱子
第 5 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 6 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 7 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 8 步：把第 4 个盘子从 A 柱子移到 C 柱子
第 9 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 10 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 11 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 12 步：把第 3 个盘子从 B 柱子移到 C 柱子
第 13 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 14 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 15 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 16 步：把第 5 个盘子从 A 柱子移到 B 柱子
第 17 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 18 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 19 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 20 步：把第 3 个盘子从 C 柱子移到 A 柱子
第 21 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 22 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 23 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 24 步：把第 4 个盘子从 C 柱子移到 B 柱子
第 25 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 26 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 27 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 28 步：把第 3 个盘子从 A 柱子移到 B 柱子
第 29 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 30 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 31 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 32 步：把第 6 个盘子从 A 柱子移到 C 柱子
第 33 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 34 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 35 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 36 步：把第 3 个盘子从 B 柱子移到 C 柱子
第 37 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 38 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 39 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 40 步：把第 4 个盘子从 B 柱子移到 A 柱子
第 41 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 42 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 43 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 44 步：把第 3 个盘子从 C 柱子移到 A 柱子
第 45 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 46 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 47 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 48 步：把第 5 个盘子从 B 柱子移到 C 柱子
第 49 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 50 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 51 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 52 步：把第 3 个盘子从 A 柱子移到 B 柱子
第 53 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 54 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 55 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 56 步：把第 4 个盘子从 A 柱子移到 C 柱子
第 57 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 58 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 59 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 60 步：把第 3 个盘子从 B 柱子移到 C 柱子
第 61 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 62 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 63 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 64 步：把第 7 个盘子从 A 柱子移到 B 柱子
第 65 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 66 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 67 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 68 步：把第 3 个盘子从 C 柱子移到 A 柱子
第 69 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 70 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 71 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 72 步：把第 4 个盘子从 C 柱子移到 B 柱子
第 73 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 74 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 75 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 76 步：把第 3 个盘子从 A 柱子移到 B 柱子
第 77 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 78 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 79 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 80 步：把第 5 个盘子从 C 柱子移到 A 柱子
第 81 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 82 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 83 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 84 步：把第 3 个盘子从 B 柱子移到 C 柱子
第 85 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 86 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 87 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 88 步：把第 4 个盘子从 B 柱子移到 A 柱子
第 89 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 90 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 91 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 92 步：把第 3 个盘子从 C 柱子移到 A 柱子
第 93 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 94 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 95 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 96 步：把第 6 个盘子从 C 柱子移到 B 柱子
第 97 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 98 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 99 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 100 步：把第 3 个盘子从 A 柱子移到 B 柱子
第 101 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 102 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 103 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 104 步：把第 4 个盘子从 A 柱子移到 C 柱子
第 105 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 106 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 107 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 108 步：把第 3 个盘子从 B 柱子移到 C 柱子
第 109 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 110 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 111 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 112 步：把第 5 个盘子从 A 柱子移到 B 柱子
第 113 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 114 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 115 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 116 步：把第 3 个盘子从 C 柱子移到 A 柱子
第 117 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 118 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 119 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 120 步：把第 4 个盘子从 C 柱子移到 B 柱子
第 121 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 122 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 123 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 124 步：把第 3 个盘子从 A 柱子移到 B 柱子
第 125 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 126 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 127 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 128 步：把第 8 个盘子从 A 柱子移到 C 柱子
第 129 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 130 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 131 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 132 步：把第 3 个盘子从 B 柱子移到 C 柱子
第 133 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 134 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 135 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 136 步：把第 4 个盘子从 B 柱子移到 A 柱子
第 137 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 138 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 139 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 140 步：把第 3 个盘子从 C 柱子移到 A 柱子
第 141 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 142 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 143 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 144 步：把第 5 个盘子从 B 柱子移到 C 柱子
第 145 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 146 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 147 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 148 步：把第 3 个盘子从 A 柱子移到 B 柱子
第 149 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 150 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 151 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 152 步：把第 4 个盘子从 A 柱子移到 C 柱子
第 153 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 154 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 155 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 156 步：把第 3 个盘子从 B 柱子移到 C 柱子
第 157 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 158 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 159 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 160 步：把第 6 个盘子从 B 柱子移到 A 柱子
第 161 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 162 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 163 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 164 步：把第 3 个盘子从 C 柱子移到 A 柱子
第 165 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 166 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 167 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 168 步：把第 4 个盘子从 C 柱子移到 B 柱子
第 169 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 170 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 171 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 172 步：把第 3 个盘子从 A 柱子移到 B 柱子
第 173 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 174 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 175 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 176 步：把第 5 个盘子从 C 柱子移到 A 柱子
第 177 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 178 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 179 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 180 步：把第 3 个盘子从 B 柱子移到 C 柱子
第 181 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 182 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 183 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 184 步：把第 4 个盘子从 B 柱子移到 A 柱子
第 185 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 186 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 187 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 188 步：把第 3 个盘子从 C 柱子移到 A 柱子
第 189 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 190 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 191 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 192 步：把第 7 个盘子从 B 柱子移到 C 柱子
第 193 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 194 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 195 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 196 步：把第 3 个盘子从 A 柱子移到 B 柱子
第 197 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 198 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 199 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 200 步：把第 4 个盘子从 A 柱子移到 C 柱子
第 201 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 202 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 203 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 204 步：把第 3 个盘子从 B 柱子移到 C 柱子
第 205 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 206 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 207 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 208 步：把第 5 个盘子从 A 柱子移到 B 柱子
第 209 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 210 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 211 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 212 步：把第 3 个盘子从 C 柱子移到 A 柱子
第 213 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 214 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 215 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 216 步：把第 4 个盘子从 C 柱子移到 B 柱子
第 217 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 218 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 219 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 220 步：把第 3 个盘子从 A 柱子移到 B 柱子
第 221 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 222 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 223 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 224 步：把第 6 个盘子从 A 柱子移到 C 柱子
第 225 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 226 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 227 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 228 步：把第 3 个盘子从 B 柱子移到 C 柱子
第 229 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 230 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 231 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 232 步：把第 4 个盘子从 B 柱子移到 A 柱子
第 233 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 234 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 235 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 236 步：把第 3 个盘子从 C 柱子移到 A 柱子
第 237 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 238 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 239 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 240 步：把第 5 个盘子从 B 柱子移到 C 柱子
第 241 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 242 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 243 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 244 步：把第 3 个盘子从 A 柱子移到 B 柱子
第 245 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 246 步：把第 2 个盘子从 C 柱子移到 B 柱子
第 247 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 248 步：把第 4 个盘子从 A 柱子移到 C 柱子
第 249 步：把第 1 个盘子从 B 柱子移到 C 柱子
第 250 步：把第 2 个盘子从 B 柱子移到 A 柱子
第 251 步：把第 1 个盘子从 C 柱子移到 A 柱子
第 252 步：把第 3 个盘子从 B 柱子移到 C 柱子
第 253 步：把第 1 个盘子从 A 柱子移到 B 柱子
第 254 步：把第 2 个盘子从 A 柱子移到 C 柱子
第 255 步：把第 1 个盘子从 B 柱子移到 C 柱子
代码：
#include <iostream>
using namespace std;
int n, cnt;
void hn(int n,char a,char b,char c)
{
if (n == 0)
{
return;
}
hn(n - 1,a,c,b);
printf("第 %d 步：把第 %d 个盘子从 %c 柱子移到 %c 柱子\n",++cnt,n,a,c);
hn(n - 1,b,a,c);
}
int main()
{
cin >> n;
hn(n,'A','B','C');
return 0;
}
如果你觉得八个盘子不够多，试一下 吧。但是把每一步都输出是不可能了，也不可能递归。可以找规律。这很简单。 。直接求就好了。（ C++ 已经不够用了，用 python 吧）代码：
def fpow(a, b):
if (b == 0): return 1
if (b == 1): return a
h = fpow(a, b // 2)
if (b % 2 == 0): return h * h
else : return h * h * a
a, b = map(int, input().split())
cnt = fpow(a, b) - 1
ans = 0
print(cnt)
while (cnt != 0):
cnt //= 10
ans += 1
print(ans)
这是 时的步数： 。好像也不多，还没有我乱打的多。那试试 ？输出（实际输出应该是一整行的，这里为了方便观看）：
1071508607186267320948425049
0600018105614048117055336074
4375038837035105112493612249
3198378815695858127594672917
5531468251871452856923140435
9845775746985748039345677748
2423098542107460506237114187
7954182153046474983581941267
3987675591655439460770629145
7119647768654216766042983165
2624386837205668069375
还是不够多。 （再多的话 python 也超了）呢？
详情
1995063116880758384883742162683585083823496831
8861924548520089498529438830221946631919961684
0361945978993311294232091242715564913494137811
1759378593209632395785573004679379452676524655
1266059895520550086918193311542508608460618104
6855090748660896248880904898948380092539416332
5785062156830947390255691238806522509664387444
1046759871626985453222868538161694315775629640
7628368807607322285350916414761839563814589694
6389941084096053626782106462142733339403652556
5649530603142680234969400335934316651459297773
2796657756061725820314079941981796073782456837
6228003730288548725190083446458145465055792960
1414833921615734588139257095379769119277800826
9577356744441230620187578363255027283237892707
1037380286639303142813324140162419567169057406
1419654342324638801248856147305207431992259611
7962501309928602417083408076059323201612684922
8849625584131284406153673895148711425631511108
9745514203313820202931640957596464756010405845
8415660720449628670165150619206310041864222759
0867090057460641785695191145605506825125040600
7519842261898059237118054444788072906395242548
3392219827074044731623767608466130337787060398
0341319713349365462270056316993745550824178097
2810983291314403571877524768509857276937926433
2215993998768866608083688378380276432827751722
7365757274478411229438973381086160742325329197
4813120197604178281965697475898164531258434135
9598627841301281854062834766490886905210475808
8261582396198577012240704433058307586903931960
4603404973156583208672105913300903752823415539
7453943977152574552905102123109473216107534748
2574077527398634829849834075693795564663862187
4569499279016572103701364433135817214311791398
2229838458473344402709641828510050729277483645
5057863450110085298781238947392869954083434615
8807043959118985815145779177143619698728131459
4837832020814749821718580113890712282509058268
1743622057747592141765371568772561490458290499
2461028630081535583308130101987675856234343538
9554091756234008448875261626435686488335194637
2037729324009445624692325435040067802727383775
5376406726898636241037491410966718557050759098
1002467898801782719259533812824219540283027594
0844895501467666838969799688624163631337639390
3373455801407636741877711055384225739499110186
4682196965816514851304942223699477147630691554
6821768287620036277725772378136533161119681128
0792669481887201298643660768551639860534602297
8715575179473852463694469230878942659482170080
5112032236549628816903573912136833839359175641
8733850510970271613915439590991598154654417336
3116569360311222499379699992267817323580231118
6264457529913575817500819983923628461524988108
8960232244362173771618086357015468484058622329
7928538756234865564405369626220189635710288123
6156751254333830327002909766865056855715750551
6727518899194129711337690149916181315171544007
7286505731895574509203301853048471138183154073
2405331903846208403642176370391155063978900074
2853672196280903477974533320468368795868580237
9522186291200807428195513179481576244482985184
6150970488802727472157468813159475040973211508
0498190455803416826949787141316063210686391511
681774304792596709375
思考一下。如果每秒移动一个盘子，那么就需要（好吧，这已经不是一个可以说出来的数字了）约（而且是约掉了很多）：
才能搬完。