|
Figure 4-2. An incomplete checkerboard, to be covered by L-shaped tiles. The tiles may be rotated, but they may not overlap
1
This is actually Exercise 2-10, but you can still have a go at that, if you want. Try to solve it without using induction.
2
Actually, the solution idea presented in the following will work for a checkerboard where an arbitrary square is missing.
I recommend you verify that for yourself.
Chapter 4
■
InduCtIon and reCursIon ... and reduCtIon
71
Placing a single tile and assuming that we can solve the rest or assuming that we’ve solved all but one and then
placing the last one—that’s certainly a reduction. We’ve transformed the problem from one to another, but the catch
is that we have no solution for the new problem either, so it doesn’t really help. To use induction (or recursion), the
reduction must (generally) be between instances of the same problem of different sizes. For the moment, our problem
is defined only for the specific board in Figure
4-2
, but generalizing it to other sizes shouldn’t be too problematic.
Given this generalization, do you see any useful reductions?
The question is how we can carve up the board into smaller ones of the same shape. It’s quadratic, so a natural
starting point might be to split it into four smaller squares. The only thing standing between us and a complete
solution at that point is that only one of the four board parts has the same shape as the original, with the missing
corner. The other three are complete (quarter-size) checkerboards. That’s easily remedied, however. Just place a
single tile so that it covers one corner from each of these three subboards, and, as if by magic, we now have four
subproblems, each equivalent to (but smaller than) the full problem!
To clarify the induction here, let’s say you don’t actually place the tile quite yet. You just note which three corners to
leave open. By the inductive hypothesis, you can cover the three subboards (with the base case being four-square boards),
and once you’ve finished, there will be three squares left to cover, in an L-shape.
3
The inductive step is then to place this
piece, implicitly combining the four subsolutions. Now, because of induction, we haven’t only solved the problem for the
eight-by-eight case; the solution holds for any board of this kind, as long as its sides are (equal) powers of two.
Note
■
We haven’t really used induction over all board sizes or all side lengths here. We have implicitly assumed that
the side lengths are 2k, for some positive integer k, and used induction over k. the result is perfectly valid, but it is
important to note exactly what we’ve proven. the solution does not hold, for example, for odd-sided boards.
This design was really more of a proof than an actual algorithm. Turning it into an algorithm isn’t all that hard,
though. You first need to consider all subproblems consisting of four squares, making sure to have their open corners
properly aligned. Then you combine these into subproblems consisting of 16 squares, still making sure the open
corners are placed so that they can be joined with L-pieces. Although you can certainly set this up as an iterative
program with a loop, it turns out to be quite a bit easier with recursion, as you’ll see in the next section.
Mirror, Mirror
In his excellent web video show, Ze Frank once made the following remark: “‘You know there’s nothing to fear but
fear itself.’ Yeah, that’s called recursion, and that would lead to infinite fear, so thank you.”
4
Another common piece of
advice is, “In order to understand recursion, one must first understand recursion.”
Indeed. Recursion can be hard to wrap your head around—although infinite recursion is a rather pathological
case.
5
In a way, recursion really makes sense only as a mirror image of induction (see Figure
4-3
). In induction, we
(conceptually) start with a base case and show how the inductive step can take us further, up to the full problem
size, n. For weak induction,
6
we assume (the inductive hypothesis) that our solution works for n–1, and from that, we
deduce that it works for n. Recursion usually seems more like breaking things down. You start with a full problem, of
size n. You delegate the subproblem of size n–1 to a recursive call, wait for the result, and extend the subsolution you
get to a full solution. I’m sure you can see how this is really just a matter of perspective. In a way, induction shows us
why recursion works, and recursion gives us an easy way of (directly) implementing our inductive ideas.
3
An important part of this inductive hypothesis is that we can solve the problem no matter which corner is missing.
4
the show with zefrank, February 22, 2007.
5
Ever tried to search for recursion with Google? You might want to try it. And pay attention to the search suggestion.
6
As mentioned in Chapter 3, in weak induction the induction hypothesis applies to n–1, while in strong induction it applies to all
positive integers k < n.
Chapter 4
■
InduCtIon and reCursIon ... and reduCtIon
72
Take the checkerboard problem from the previous section, for example. The easiest way of formulating a solution
to that (at least in my opinion) is recursive. You place an L-piece so that you get four equivalent subproblems, and
then you solve them recursively. By induction, the solution will be correct.
Do'stlaringiz bilan baham: |
