Let's look at the problem this way. I need to move N disks from A to B; I can use C if I want.
If I have one disk, that's easy: I just move it from A to B. Done, and I didn't need C. (That's the first part.)
If I have two, then I have to move the smaller disk out of the way (to peg C), move the biggest disk to peg B, then move the smallest disk to peg B again. Generalizing, I need to move the disks on A that are "in the way" to C (thereby getting them "out of the way"), using B as a workspace if I need it, move the disk I actually want to move to B, then move the stack on C to B using A for workspace if I need it. It might be clearer like this:
my ($n, $peg_a, $peg_b, $peg_c) = @_;
if ($n == 1)
print "Move disk #1 from $peg_a to $peg_b.\n";
+a, $peg_c, $peg_b);
print "Move disk #$n from $peg_a to $peg_b.\n";
+c, $b, $peg_a);
Notice that we have the necessary criteria in place for a recursive algorithm: we have a bottom-out condition (when $n == 1, move the single disk), and we have a recursive call that guarantees we reach bottom ($n is decremented on each subsequent call). This only partly solves the problem, though: the recursive algorithm has moved N-1 disks "out of the way", and we have to move them all again
to put them in their final position; this is why we need the second call. This call is also guaranteed to bottom out, because it decrements $n each time it is re-called.
The four-disk solution visualization here should help a lot: the target peg in this visualization is #3; note how we have to move the top 3 disks out of the way, then put them back, and that we have to repeat this for each successively-higher layer.
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags:
Outside of code tags, you may need to use entities for some characters:
- a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.
| & || & |
| < || < |
| > || > |
| [ || [ |
| ] || ] ||