- Hanoi towers big oh proof by induction how to#
- Hanoi towers big oh proof by induction full#
- Hanoi towers big oh proof by induction code#
Lastly, it is funny how explaining a problem to a colleague, your wife/husband or even the dog (even it they not listening) can cement enlightenment.Īfter reading all these explanations I thought I'd weigh in with the method my professor used to explain the Towers of Hanoi recursive solution. The final number of moves for n discs is 2^n - 1 the move n disc to destination is halfway through the process. Then move the top disc to the source peg, make the next legal move(nittd).īest done by always holding the top disc with the same hand and always moving that hand in the same direction. Then move the top disc to the spare peg, make the next legal move(nittd). if odd, move the first disc to the destination peg, make the next legal move (not involving the top disc).Then move the top disc to the source peg, make the next legal move(nittd). Then move the top disc to the destination peg, make the next legal move(nittd). if even, move the first disc to the spare peg, make next legal move (not involving the top disc).Incidently, to solve the problem by hand is quite satisfying. The solution also conveys the power of proof by induction and a warm glow to all programmers who have wrestled with conventional control structures. However it is the displaying of the function parameters which is the solution to the problem and crucially understanding the double tree like structure of the calls. moving the remaining tower on the spare peg to the destination peg.moving the last disc to the destination peg.moving a smaller tower to the spare peg.Yes the problem is really in three parts: The magic occurs in the succesive rearrangment of the function parameters. In the Tower of Hanoi, the answer is not in the returned result per se, but in the observation of the returned result. However, this teaches the reader to use the results of the returned result in the next recursive call. After that, the remaining disc will be moved to the destination peg and afterwards the second recursion compeltes the moving of the entire tower, by moving the n − 1 tower from the temp peg to the destination peg, above disc n.Īlthough this is an old post, I think what one really needs to understand, is not the "move this to that" approach but that the answer involves using the side-effect of the recursion.Ī invaluable help to me was the "The Little Schemer" which teaches one to think and write recursive functions. The one before the writeln will move n − 1 discs onto the temporary peg, using the destination peg as temporary storage (the arguments in the recursive call are in different order).
The recursion happens actually twice, there, once before the writeln, once after.
Hanoi towers big oh proof by induction code#
The code in your post has three arguments, besides the number of discs: A source peg, a destination peg and a temporary peg on which discs can be stored in between (where every disc with size n − 1 fits).
Hanoi towers big oh proof by induction full#
And that you have to move them first to another peg than where you want the full tower to appear. It's pretty clear that you first have to remove n − 1 discs to get access to the nth one. move n−1 discs from B to C so they sit on disc #n.Basic programming knowledge is necessary as some quizzes require programming in Python.Actually, the section from where you took that code offers an explanation as well:
Hanoi towers big oh proof by induction how to#
We assume only basic math (e.g., we expect you to know what is a square or how to add fractions), common sense and curiosity.Ģ. In the online course, we use a try-this-before-we-explain-everything approach: you will be solving many interactive (and mobile friendly) puzzles that were carefully designed to allow you to invent many of the important ideas and concepts yourself.ġ. We will use these tools to answer typical programming questions like: How can we be certain a solution exists? Am I sure my program computes the optimal answer? Do each of these objects meet the given requirements? In this course, we will learn the most important tools used in discrete mathematics: induction, recursion, logic, invariants, examples, optimality. Mathematical thinking is crucial in all areas of computer science: algorithms, bioinformatics, computer graphics, data science, machine learning, etc.
0 kommentar(er)
