欢迎来到天天文库
浏览记录
ID:38187488
大小:127.81 KB
页数:4页
时间:2019-05-24
《算法分析与设计-四杆汉诺塔问题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最小移动次数计算:已知Hanoi3移动次数g
3、(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++)程序运行截图:
此文档下载收益归作者所有