一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 581|回复: 5
收起左侧

[CareerCup] 【第四轮】4.13 - 4.19 Career Cup 3.4

[复制链接] |试试Instant~ |关注本帖
pure0909 发表于 2015-4-14 10:56:34 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
3.4 In the classic problem of the Towers of Hanoi, you have 3 towers and N disks of
different sizes which can slide onto any tower. The puzzle starts with disks sorted
in ascending order of size from top to bottom (i.e., each disk sits on top of an
even larger one). You have the following constraints:
(1) Only one disk can be moved at a time.
(2) A disk is slid off the top of one tower onto the next tower.
(3) A disk can only be placed on top of a larger disk.
Write a program to move the disks from the first tower to the last using stacks.

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link]
【test case】(optional,如果觉得比较好,欢迎贴出来分享)

Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎探讨各种follow up questions,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改


A30041839 发表于 2015-4-16 13:16:39 | 显示全部楼层
[solution]
use the standard recursive solution for Hanoi problem. First Move n - 1 plates from tower1 to tower2 using tower3 as an intermediate. then move the largest plate of tower1 to tower3. Finally move n - 1 plates from tower2 to tower3 using tower1 as an intermediate.
[time]
T(n)=2T(n-1)+1
O(2^n)
[space]
O(n)
[gist]
https://gist.github.com/A30041839/b66a5f6a4356f3fc1c10
回复 支持 反对

使用道具 举报

iker01 发表于 2015-4-16 21:46:40 | 显示全部楼层
【解题思路】
# solution
# use the traditional Hanoi recursive solution to move the disk
【时间复杂度】
O(2**n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/zhangjiang2013/11cd967e0c146eb13876
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-4-18 21:34:26 | 显示全部楼层
【解题思路】
use basic solution for solving Towers of Hanoi, we define three towers as origin, destination and buffer, in the buffer tower, we can treat it as middle status and transfer it to other status.
Thus we can write a recursive solution
【时间复杂度】
T(n) = 2T(n-1) +n
【空间复杂度】
O(n)
【gist link]
https://gist.github.com/JamesJi9277/99caad2644c621a98407
【test case】
回复 支持 反对

使用道具 举报

alikewmk 发表于 2015-5-1 13:21:10 | 显示全部楼层
本帖最后由 alikewmk 于 2015-5-1 13:22 编辑

【解题思路】
递归:
移动前n-1个盘子到缓冲塔上
移动第n个盘子到目标塔
从缓冲塔移动前n-1个盘子到目标塔
【时间复杂度】
如果盘子的数量是n,那么时间复杂度是O(2^n-1)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/alikewmk ... 3-4-hanoitower-java


回复 支持 反对

使用道具 举报

Godbless 发表于 2015-6-5 10:49:11 | 显示全部楼层
【解题思路】Use base case and build approach to recursively complete complicate case based
        on easier case.
【时间复杂度】O(2^n)
【空间复杂度】O(n)
【gist link] https://github.com/StephenWeiXu/ ... aster/Chap3/3_4.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 22:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表