汉诺塔1到9最快分别是几次。可以告诉我计算方法吗？
2019-10-22
汉诺塔是一个迭代问题，我们先假设x层汉诺塔从第一根柱子移动到最后一根柱子（目标柱子）的最快次数是f(x)次 显然f(1)=1 f(2)=3 然后看3层的，我们可以把整个过程分解为三个部分 一，把第一第二层移动到中间的柱子（过渡柱子），最快f(2)步 二，把第三层移动到最后一根柱子（目标柱子），最快1步 三，把刚才移动到中间柱子的第一第二层移动到最后一根柱子，最快f(2)步 所以f(3)=f(2)+1+f(2)=7 然后以此类推 f(4)=f(3)+1+f(3)=15 f(5)=f(4)+1+f(4)=31 f(6)=f(5)+1+f(5)=63 f(7)=f(6)+1+f(6)=127 f(8)=f(7)+1+f(7)=255 f(9)=f(8)+1+f(8)=511 PS.如果学习过数列的话，这个其实可以得到更为一般的递推公式 f(x+1)=2*f(x)+1 再进一步，可以得到通项公式为 f(x)=2^x-1
大家都在看
本站系本网编辑转载，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与本网联系，我们将在第一时间删除内容！本站文章版权归原作者所有，内容为作者个人观点。本站只提供参考并不构成任何投资及应用建议。本站拥有对此声明的最终解释权。