Here's a complete working implementation in C. You have to learn to trust that it works for n-1. Where people get into trouble is trying to hold every single iteration in their head at once. You know this is guaranteed to work, because you can define n-1 in terms of n-2, which you can define in terms of n-3, and so on until you eventually get to one disk, which is trivial. For n disks, you first move a stack of n-1 disks, then the n th disk, then you move the stack on top of it. You move a stack of two to a temporary location, move the n th disk to its destination, then move the stack of two on top of it. The next iteration is harder, but the trick here is to recognize that you already have proved you can move a stack of two disks, so you can abstract that away. First you move one disk to a temporary spot, you move the second to the destination, then you move the first disk to the destination. Then you make it slightly larger, and slightly larger, and look for patterns.įor Towers of Hanoi, what is the simplest possible problem? One disk, moved straight to its destination.
Divide and conquer is about making the problem so small that it is absolutely trivial to solve.
0 kommentar(er)
