【第三轮】6.30-7.6 CareerCup 3.4

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、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

【解题思路】
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

============================================================================
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
============================================================================

【解题思路】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

【解题思路】
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.

【解题思路】
Recursion

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

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

【gist link】
https://gist.github.com/JoyceeLee/b06e4f5d40a8a3314a85

【解题思路】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
【解题思路】
使用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。

【解题思路】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)