数据结构和算法——汉诺塔问题

前言

先讲个故事，传说古代印度有三根黄金柱，64个石盘，需要将石盘从第一根移动到第三根上，规定每次只能移动一片，并且小盘在放置时必须在大盘上。
当石盘移动完毕时，世界就会毁灭。

汉诺塔——递归

接下来我们用程序来模拟这个移动过程，并计算世界毁灭需要的时间。

这里使用的策略就是递归
我们将黄金柱编号为A,B,C,我们首先需要将A柱最底层的64号大石盘移动到C柱上，那么我们可以认为有一个大力士，将63号以及之前的石盘已经被放在了B柱上。B柱是辅助柱。这时，我们就可以轻松将A柱剩下的一个最大的64号石盘放到C柱上，此时我们完成了第一步。

同理，假设64号石盘已经被放在了C柱上，63号石盘此刻也需要被放在C柱上，我们也能认为，有一个大力士将62号以及之前的石盘已经被放在了B柱上。以此类推。
我们不用管大力士是如何做到的，我们每次只需要将最后一块相对最大的石盘放到C柱上就行了。这就是每一次移动石盘最终的目的。
所以，每次在C柱上能够正常进行叠放的最后一步都是，一个单独的石盘等着被放在C柱上，我们轻松的将64号，63号，62号…1号放到C柱上
而实际上，大力士是我们递归的自己，这个又该怎么理解呢？
用python写就是这样

def hanoiTower(n,source,auxiliary,target):# 如果就剩下最后一块，那么直接叠放到目标柱上，需要注意的是，目标柱并不是不变的，会变成辅助柱，因为搬运过程中，进入子递归，会把辅助柱当做目标柱，大力士需要先把63块之前的所有石盘放到辅助柱上# 每次迭代，都将最后一块设定为终极目标，搬完最后一块就表明最后一个小任务完成了if n==1:print(f"{n}号石盘搬运：{source}-->{target}")else:#大力士将n-1块石盘从源头柱放到辅助柱，这样最底层的石盘就暴露了出来# 将n-1个盘子从源柱移动到辅助柱（此时辅助柱成为子问题的目标柱）hanoiTower(n-1, source, target, auxiliary)print(f"{n}号石盘搬运：{source}-->{target}")# 大力士将n-1块石盘从辅助柱放到目标柱，就算之前的任务完成了# 将n-1个盘子从辅助柱移动到目标柱（此时源柱成为子问题的辅助柱）hanoiTower(n-1, auxiliary,source, target )
hanoiTower(3,"A","B","C")

1号石盘搬运：A-->C
2号石盘搬运：A-->B
1号石盘搬运：C-->B
3号石盘搬运：A-->C
1号石盘搬运：B-->A
2号石盘搬运：B-->C
1号石盘搬运：A-->C

计算时间复杂度，空间复杂度，距离世界毁灭剩余的时间

每次任务分解，都是两次移动n-1个盘子和一次移动单个盘子
因此T=2T(n-1)+1
根据实际情况可以将其展开，递归到第二次时T=2(2T(n-2)+1)+1
递归第三次时T=2(2*(2*T(n-3)+1))+1
一次类推展开，可以知道n=1时，就是递归结束的时候，此时T(1)=1
T=2^n-1
时间复杂度为O(2^n)

空间复杂度：
处理n个盘子时，递归调用链为n,n-1,n-2,n-3…1,最大深度所以为n,空间复杂度为O(n)

那么根据传说，算出来2^64时间长度为11698.8483亿年，这个时间说是宇宙末日，确实有可信度。
毕竟1万亿年以后的超人僧侣，1s就能抬起巨石将圆盘准确无误的放到C黄金柱上，本宇宙汉诺塔也新修建完毕，宇宙终于再次放起了烟花，大爆炸开始了。