怎么证明汉诺双塔问题的解决步数是2^(n+1)-2题目是vijos的1354题不要程序要证明转帖不介意但要清楚是每个大小的盘子有两个

Question

怎么证明汉诺双塔问题的解决步数是2^(n+1)-2
题目是vijos的1354题
不要程序
要证明
转帖不介意
但要清楚
是每个大小的盘子有两个

Answer 1

那就当同样大小的盘子只有一个，因为两个的话就是原来的移动方法中，每次移两个而已，最后结果也是乘以2
汉诺塔的移动方法是一个递归的过程，如果当前有n个盘子在1号柱子，要移到3号柱子，那么先移动上面的（n-1）个盘子到2号柱子，然后把底下最大的那个移到3号柱子，再把2号柱子上的（n-1）个盘子移到3号柱子。这期间，n-1个盘子的移动方法和前面叙述的是一样的，先移动上面n-2个盘子，再……以此类推，递归到n等于1的时候就停止了，因为1个盘子显然只要直接移动就可以了
好了，现在就有了一个递推方程，f(n)=f(n-1)+1+f(n-1);f(1)=1,解这个方程，就能得到f(n)=2^n-1