Send
Close Add comments:
(status displays here)
Got it! This site uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website.nbsp; Note: This appears on each machine/browser from which this site is accessed.
Towers of Hanoi: code complexity
1. Towers of Hanoi: code complexity
2. Code and output
3. Complexity
How much time (or space) does this solution require?
This is called the complexity of the solution - or algorithm.
4. Intelligent insight
Recurrence relation: (discrete form of a differential equation)
Moves(1) = 1
Moves(n) = 2 * Moves(n-1) + 1 , for n > 1
5. Solution
Solution: (guess and verify)
Moves(n) = (2 ^ n) - 1
Moves(n+1) = (2 ^ (n+1)) - 1
6. Proof
Proof: (by induction, assuming solution)
Base: Moves(1) = 1
Step: Moves(n+1) = (2 * Moves(n-1)) + 1
= 2 * ((2 ^ n) - 1) + 1
= 2 * (2 ^ n) - 2 + 1
= (2 ^ (n+1)) - 1
7. Run the code
The code is correct. Given enough time, the code will solve the problem. Right?
Do we have infinite time?
Do we have infinite space?
How do we test a program to insure it is correct?
8. Program modification
Here are some changes that could be made to the Towers of Hanoi program.
Print just the first m moves.
Return the list of moves.
Return the list of m moves.
Return the next move as each move is requested.
How might each of these changes be made. Note: Some are related but do not necessarily depend on the other changes.
9. End of page
