移动步骤
三根柱子A，B，C。A杆上有N个N>1N>1穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：*
- 每次只能移动一个圆盘；
- 大盘不能叠在小盘上面。
解法一：
使用递归
分析：
- 当只有一个时，只需把第一个盘从a移到c
- 两个时，先把第一个盘从a移到b，再把第二个盘从a移到c，最后把第一个盘从b移到c
- 三个时，将1号盘移到c，2号盘移到b，1号盘移到b，（此时1,2号盘放在b），3号盘移到c，（将1,2号盘从b移到c）1号盘移到a，2号盘移到c，1号盘移到c
- 四个时，1从a到b，2从a到c，1从b到c，3从a到b，1从c到a，2从c到b，1从a到b，（此时1,2,3号盘在b），4从a到c，（将1,2,3号盘从b移到c）1从b到c，2从b到a，1从c到a，3从b到c，1从a到b，2从a到c，1从b到c
- ...可以看出从两个盘开始，都是将最后一个盘上面的盘移到b，在将最大盘移到目标柱后，再把在b的盘移动到c
- n个盘时，将n-1个盘从a移动到b，直接移动不成立，所以借助c，形成a->c->b，随后将n移动到c后，将n-1盘从b移到c——也就是先将n-2个盘从b移到a，可以将a，b，c看做一个圆圈上的三个柱子，所以这时的移动方式是b->c->a，将n-1盘放到c。
- 重复操作直到完成
思路：
- 如果只有一个盘，直接从a到c
- 按照分析，两个以上的盘的规律是：
- 将n-1个盘放到b
- 将n盘移动c
- 将n-1盘移到c（过程和上两步相同，只是起始柱从a变成了b
代码：
//设置变量接收盘数和柱的名称
var hanoi = function(n,a,b,c){
//一个盘是直接移动
if(n == 1){
console.log(`将${n}从${a}移到${c}`)
}else{
//使用递归，直到只有一个盘，然后回溯到n
//先将n-1个盘放到b
hanoi(n-1,a,c,b)
//将n盘移到c
console.log(`将${n}从${a}移到${c}`)
//将n-1盘移到c
hanoi(n-1,b,a,c)
}
}
//时间复杂度O(2^n)，随着n的增加，消耗时间成指数增长
//简化
var hanoi = function(n,a,b,c){
//一个盘是直接移动
if(n > 0){
//使用递归，直到只有一个盘，然后回溯到n
//先将n-1个盘放到b
hanoi(n-1,a,c,b)
//将n盘移到c
console.log(`将${n}从${a}移到${c}`)
//将n-1盘移到c
hanoi(n-1,b,a,c)
}
}
解法二：崩了
分析：
从解法一的分析可以看出n为偶数的移动方式
| 盘号 | 移动方式 |
|---|---|
| 1 | 1.a->b 3.b->c 5.c->a 7.a->b 9.b->c 11.c->a 13.a->b 15.b->c |
| 2 | 2.a->c 6.c->b 10.b->a 14.a->c |
| 3 | 4.a->b 12.b->c |
| 4 | 8.a->c |
奇数号盘的移动规律是a->b->c->a循环
偶数号盘是a->c->b->a循环
而n为奇数时正好相反
盘的移动顺序为1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
1盘在1,3,5,7，9,11,13,15时移动 转为二进制为1,11,101,111,1001,1011,1101,1111
2盘在2,6,10,14时移动 10,110,1010,1110
3盘在4,12时移动 100,1100
4盘在8时移动 1000
可以说奇数盘比偶数盘多移一个柱
奇数：a->b->c->a
偶数：a-b->c-a->b-c->a-b->c
循环遍历最后一个1后面0的个数
时间复杂度2^n*？
思路：
- 判断盘数的奇偶，创建数组记录盘所在的柱
- 循环2^n-1,将每一个数转换成二进制字符串，并循环遍历最后一个1后面的0的个数，根据0的个数判断移动哪个盘，并更新柱
代码：
JavaScript
python
def hanoi(n):
cols = ["A","B","C"] if n % 2 == 0 else ["A","C","B"]
pan = [0] * n #盘的id == 柱的id
for step in range(1,2**n):
idx = len(bin(step & -step)) - 3 #lowbit 转二进制，开头是0b1
old_tower = cols[golds[idx]]
golds[idx] = (golds[idx] + 1 + idx % 2) % 3 # 奇数比偶数多走一步
print(f"step{step}: 将{idx + 1}号金片从{old_tower}移到{cols[golds[idx]]}")
hanoi(4)