算法分析与设计-四杆汉诺塔问题C++

《算法分析与设计-四杆汉诺塔问题C++》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计第二次作业_黄俊23220111153229算法分析题2-3：Java实现代码：Junit单元测试：测试结果：i=2j=3算法分析题2-4解：当m比n小很多时，可以将v进行拆分，拆分成n/m块，这样至少有(n/m-1)块有m位，当y=n%m>0时，有一块将小于m位。这样计算uv就需要(n/m)次m位的乘法运算。根据大整数的乘法T(m)=O(m^log3)，那么拆分后的时间复杂度为O((n/m)m^log3)4塔座的Hanoi问题，写出程序并计算最小移动次数解：考虑了很久，递归思路能想出，但不会计算最小移动次数

2、。最后参考网上的一个大牛的博客，理解了，自己用C++实现了一下。Hanoi4问题：将A塔座上n个盘子借助B、C塔座不改变大小顺序的移动到D塔座上。Hanoi4递归思路：1、将A柱上n个盘子寻找一个最佳的分割数k，划分为上下两部分，下方部分共有k个盘子，上方共有n-k个盘子。2、将A柱上面部分的n–k个盘子使用Hanoi4算法经过C、D柱移至B柱。3、将A柱剩余的k个盘子使用经典的Hanoi3算法经过C柱移至D柱。4、将B柱上的n–k个盘子使用Hanoi4算法经过A、C柱移至D柱。Hanoi4最小移动次数计算：已知Hanoi

3、3移动次数g(k)=2g(k-1)+1=2^k-1采用上述Hanoi4算法，设Hanoi4最少移动次数为f(i)，由于每次移动先采用Hanoi4移动上方(i-k)个盘子需要移动次数f(i-k)，然后采用Hanoi3移动剩余的k个盘子需要移动次数g(k)，由于不同的k(1<=k<=i)移动次数不同，这里要求其最小的移动次数min。综上，根据分治法时间复杂度公式，可知：程序代码：（C++）程序运行截图：