Java Reference
In-Depth Information
We generalize to the task of tiling a
2
n
by
2
n
square, in which one square is
already covered. This is for some
n≥0
:
/**
Tile the
2
n
by
2
n
square with upper left corner
(x,y)
. One
square foot of it is already covered.
*/
public static void
tile(
int
n,
int
x,
int
y)
We develop a recursive procedure to tile the kitchen. Part of our resulting
program is in English, rather than Java, so that we can hide unimportant details.
For example, we are not explicit about where the refrigerator is. This way, the
beautiful idea behind the tiling is most easily seen.
We take
n=0
as the base case. Since
2
0
=1
, a
1
by
1
square has to be tiled.
But it is already covered, so no tiling needs to be done.
We want to solve the case
n>0
using recursion. That requires finding the
same problem on a smaller scale, and the obvious thing to consider is a
2
n-1
by
2
n-1
kitchen. The way to get such a kitchen is to split the
2
n
by
2
n
kitchen into
four quadrants, but then we have four
2
n-1
by
2
n-1
kitchens. One of them con-
tains a covered square, but the other three do not. But we can place one tile so
that it covers one square of each of these three quadrants (see the diagram on the
right in Fig. 15.4). Now, all four quadrants can be tiled using recursive calls to
procedure
tile
. The procedure is given in Fig. 15.5.
Isn't it a neat algorithm? And the key to its development was so simple. In
the recursive case, consciously look for the same problem on a smaller scale.
See lesson
page 15.3 to
get the method
from the CD.
Computing x
y
We develop a recursive function that computes
x
y
for
y≥0
:
/** = x
y
. Precondition:
y≥ 0 */
public static int
exp(
int
x,
int
y)
If
y=0
, then
x
y
=1
, so we use
y=0
as the base case.
15.2.2
Activity
15-3.2
/**
Tile the
2
n
by
2
n
square with upper left corner
(x, y)
.
One sub-square is already covered.
*/
public static void
tile(
int
n,
int
x,
int
y) {
if
(n == 0)
{
return
; }
Place a tile so that each quadrant has one covered square
;
tile(n - 1, x, y);
tile(n - 1, x + 2
n-1
, y);
tile(n - 1, x, y + 2
n-1
);
tile(n - 1, x + 2
n-1
, y + 2
n-1
);
}
Figure 15.5:
Tiling Elaine's kitchen
Search WWH ::
Custom Search