Java Reference
In-Depth Information
else
{
if
(n > 2)
turnOff(n - 2)
Turn off light
n
if
(n > 2)
turnOn(n - 2)
turnOff(n - 1)
}
Algorithm
turnOn(n)
//
Turns on
n
lights that are initially off.
if
(n == 1)
Turn on light 1
else
{
turnOn(n - 1)
if
(n > 2)
turnOff(n - 2)
Turn on light
n
if
(n > 2)
turnOn(n - 2)
}
a.
Implement these algorithms in Java. Use the results in a program to display directions to turn off
n
lights
that initially are on.
b.
What recurrence relation expresses the number of times that lights are switched on or off during the course
of solving this problem for
n
lights?
11.
Consider a maze made up of a rectangular array of squares, such as the following one:
X X X X X X X X X X X X X
X X X X X X
X X X X X
X X X X X X X X
X X X X X
X X X X X X X
X X X X X X X X X X X X X
The Xs represent a blocked square and form the walls of the maze. Let's consider mazes that have only one
entrance and one exit on opposite sides of the maze, as in our example. Beginning at the entrance at the top left
side of the maze, find a path to the exit at the bottom right side. You can move only up, down, left, or right.
Each square in the maze can be in one of four states: clear, blocked, path, or visited. Initially, each square is
either clear or blocked. If a square lies on a successful path, mark it with a period. If you enter a square but it does
not lead to a successful path, mark the square as visited.
Let a two-dimensional array represent the maze. Use a recursive algorithm to find a path through the maze.
Some mazes might have more than one successful path, while others have no path.
A
NSWERS
TO
S
ELF
-T
EST
Q
UESTIONS
1.
public
static
void
skipLines(
int
givenNumber)
{
if
(givenNumber >= 1)
{
System.out.println();
skipLines(givenNumber - 1);
}
// end if
}
// end skipLines
