一亩三分地论坛

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

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

[CareerCup] 【第三轮】6.30-7.6 CareerCup 3.4

[复制链接] |试试Instant~ |关注本帖
wrj5518 发表于 2014-6-29 21:15:14 | 显示全部楼层 |阅读模式

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

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

x
3.4 In the classic problem of the Towers of Hanoi, you have 3 towers and Ndisks 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】
---------------optional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】


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




grassgigi 发表于 2014-7-2 11:09:59 | 显示全部楼层
【解题思路】
Data structure - List of stacks as tower, push/pop when sliding disks between towers

Algo - Recursion
To move N disks from tower A to tower B:
1. move top N -1 disks from tower A to tower C
2. move N'th disk from tower A to tower B
3. move top N-1 disks from tower C to tower B

【时间复杂度】
Solving recursion tree : O(n) = 2O(n-1) + 1
we got O(2^n)...holy crap:(

【空间复杂度】
O(n) - all towers and disks
O(2^m) - recursion call stack size m

【gist link】
https://gist.github.com/chrislukkk/9e479f22da6165f83b9d
回复 支持 1 反对 0

使用道具 举报

ryancooper 发表于 2014-7-2 11:49:05 | 显示全部楼层
本帖最后由 ryancooper 于 2014-7-2 11:53 编辑

【解题思路】
I assume that the question want me to explicitly use the stack. The process is similar to inorder traversal of binary tree.

【时间复杂度】
O(2^n)

【空间复杂度】
O(n)

【gist link】
https://gist.github.com/ryancooper/f27e2c3e2556543209c9You can test this in your Python Interpreter like this:

Hanoi(3, 'A', 'C', 'B'), which means to move 3 plates from 'A' pillar to 'C' pillar using 'B' as auxillary pillar.

回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-7-3 14:28:19 | 显示全部楼层
【解题思路】
Recursion

【时间复杂度】
O(n) = 2O(n-1) + 1
∴ O(2^n)

【空间复杂度】
O(n) - all towers and disks

【gist link】
https://gist.github.com/JoyceeLee/b06e4f5d40a8a3314a85
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-7-4 05:20:27 | 显示全部楼层
【解题思路】recursion   move from tower source to tower des,  give a tower tool   size = N
1)   move N-1 disks  from source  to tool      des tower as buffer
2)  move  the last one to des
3)  move the N-1 disks from tool  to des     source tower as a buffer

【时间复杂度】O(2^n)

【空间复杂度】
O(n)

【gist link】  https://gist.github.com/jyhjuzi/b70ef4fa1bda7240fcfc
回复 支持 反对

使用道具 举报

头像被屏蔽
serolins 发表于 2014-7-4 05:42:19 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

ryancooper 发表于 2014-7-4 09:36:11 | 显示全部楼层
serolins 发表于 2014-7-4 05:42
【解题思路】
使用recursion的思想。

You can solve this recurrence as follow:

O(n)+1 = 2O(n-1)+1+1 = 2*( O(n-1)+1 ), then sequence { O(n)+1 } can be viewed as a geometric sequence。
回复 支持 反对

使用道具 举报

头像被屏蔽
serolins 发表于 2014-7-4 12:18:16 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

habina 发表于 2014-7-4 13:42:38 | 显示全部楼层
============================================================================
Question        : 3.4 In the classic problem of the Towers of Hanoi, you have 3 towers and
                                        Ndisks 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.
Solution        : Use Recursion
Time Complexity : O(N)
Space Complexity: O(N)
Gist Link       : https://gist.github.com/habina/3de54124f370cbd1be2b
============================================================================
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-7-5 02:03:09 | 显示全部楼层
【解题思路】3 Stacks, 1 is source, 1 is buffer, 1 is destination
Recursion
To move N disks from src to dst:
1. move top N -1 disks from src to buffer(via)
2. move the largest one from src to dst
3. move N-1 disks to dst use src as buffer

【时间复杂度】
O(N^2), arithmetic arithmetic
【空间复杂度】
O(n)
【gist link】https://gist.github.com/bitcpf/f13146e8c0283da3e4ba

补充内容 (2014-7-5 09:38):
时间复杂度错了,应该是O(2^N)
回复 支持 反对

使用道具 举报

donnice 发表于 2014-7-5 06:29:02 | 显示全部楼层
【解题思路】
经典算法了不再赘述,具体请百度“汉诺塔”
【时间复杂度】
O(2^n)(我很想知道大家的O(N)是怎么出来的)
【空间复杂度】
O(N)
【gist】
https://github.com/donnice/donni ... 455e6761ba7c6007cf3
回复 支持 反对

使用道具 举报

Neal 发表于 2014-7-5 14:06:52 | 显示全部楼层
【解题思路】Recursion
【时间复杂度】O(2^n)
【空间复杂度】O(N)
【gist】https://gist.github.com/nealhu/f8d39eba344cfe8bda81
回复 支持 反对

使用道具 举报

pud 发表于 2014-7-6 02:04:47 | 显示全部楼层
【解题思路】Recursion
【时间复杂度】O(2^n)
【空间复杂度】O(N)
【gist】https://gist.github.com/yokiy/ceee7892798ca326a0e7
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-6 14:21:02 | 显示全部楼层
【解题思路】C.f. wikipedia: Tower of Hanoi
1. Recursive
2. Iterative: Alternate moves between the smallest piece and a non-smallest piece. When moving the smallest piece, always move it to the next position in the same direction (to the right if the starting number of pieces is even, to the left if the starting number of pieces is odd).
3. Simple iterative: for an even number of disks repeat legal moves between AB, AC and BC; for an odd number of disks repeat legal moves between AC, AB and BC, until the first two stacks are all empty. (OR until a total of 2^n-1 moves are made.)
【时间复杂度】
O(2^N) // minimum 2^n-1 moves
【空间复杂度】
O(N) if count on the via stack
【gist link】
https://gist.github.com/d945badeffb473c1fd12
回复 支持 反对

使用道具 举报

chouclee 发表于 2014-7-6 21:46:55 | 显示全部楼层
【解题思路】
用stack模拟递归, 参考http://hawstein.com/posts/3.4.html
【时间复杂度】
O(2^n) (具体为2^n - 1)
【空间复杂度】
O(n)  (具体为2n-1)
【gist link】
https://gist.github.com/chouclee/97dbc195b1c92b7b1418
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-7-6 23:54:26 | 显示全部楼层
【解题思路】
recursive:
1. move n-1 disks to the Temp stack
2. move the last disk from From stack to To stack
3. move n-1 disks from Temp stack to To stack
【时间复杂度】
O(2^N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/iwilbert/9ab3ff91d4730f3b1dd0
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-7-7 05:05:38 | 显示全部楼层
【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】

这两天补
回复 支持 反对

使用道具 举报

jason51122 发表于 2014-7-7 13:33:21 | 显示全部楼层
【解题思路】An recursion problem. Move n-1 from tower 0 to tower 1. Then move 1 from tower 0 to tower 2. Move n-1 from tower 1 to tower 2.
【时间复杂度】O(2^N)
【空间复杂度】O(N)
【gist link】https://gist.github.com/jason51122/009c4fa7f4166bc59906
回复 支持 反对

使用道具 举报

jason51122 发表于 2014-7-7 13:41:11 | 显示全部楼层
本帖最后由 jason51122 于 2014-7-7 13:42 编辑
chouclee 发表于 2014-7-6 21:46
【解题思路】
用stack模拟递归, 参考http://hawstein.com/posts/3.4.html
【时间复杂度】

Why the space complexity is 2n-1? We have n disks in total and move them within 3 towers. The maximum # of disks is n-1 for tower 2 and n for tower 0 and tower 2. So I think the space complexity is 3n-1, which is O(n). Thanks.
回复 支持 反对

使用道具 举报

aloncgo 发表于 2014-7-7 13:57:39 | 显示全部楼层
【解题思路】
an classic recursion problem
for n-order Hanoi Tower:
1. move n - 1 disks from tower A to tower B
2. move the biggest disk N from A to C
3. move n - 1 disks from B to C
if n==1 move the only disk from A to C directly
【时间复杂度】O(2^n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/weazord/2b605eb3bf24e9468467
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 02:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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