Java Reference
In-Depth Information
Write a recursive function that takes as input the number of rows
n
and outputs
the total number of pins that would exist in a pyramid with
n
rows. Your program
should allow for values of
n
that are larger than 5.
4. The game of “Jump It” consists of a board with
n
positive integers in a row except
for the first column, which always contains zero. These numbers represent the cost
to enter each column. Here is a sample game board where
n
is 6:
0
3
80
6
59
10
The object of the game is to move from the first column to the last column in the
lowest total cost. The number in each column represents the cost to enter that
column. Always start the game in the first column and have two types of moves. You
can either move to the adjacent column or jump over the adjacent column to land
two columns over. The cost of a game is the sum of the costs of the visited columns.
In the board shown above, there are several ways to get to the end. Starting in the
first column, our cost so far is 0. We could jump to 80, then jump to 57, then
move to 10 for a total cost of 80
+
57
+
10
=
147. However, a cheaper path would
be to move to 3, jump to 6, then jump to 10, for a total cost of 3
+
6
+
10
=
19.
Write a recursive solution to this problem that computes the cheapest cost of the
game and outputs this value for an arbitrarily large game board represented as an
array. Your program does not have to output the actual sequence of jumps, only
the cheapest cost of this sequence. After making sure that your solution works on
small arrays, test your solution on boards of larger and larger values of
n
to get a
feel for how efficient and scalable your solution is.
5. Write a recursive method definition for a static method that has one parameter
n
of type
int
and that returns the
n
th Fibonacci number. The Fibonacci numbers
are
F
0
is 1,
F
1
is 1,
F
2
is 2,
F
3
is 3,
F
4
is 5, and in general
F
i
+
2
=
F
i
+
F
i
+
1
for
i
=
0, 1, 2, …
Place the method in a class that has a
main
that tests the method.
6. The formula for computing the number of ways of choosing
r
different things from
a set of
n
things is the following:
C
(
n, r
)=
n!/
(
r!*
(
n
-
r
)
!
)
The factorial method
n!
is defined by
n!
=
n*
(
n
-
1
)
*
(
n
-
2
)
*
…
*
1
Discover a recursive version of the formula for
C
(
n
,
r
) and write a recursive
method that computes the value of the formula. Place the method in a class that
has a
main
that tests the method.
7 .
Towers of Hanoi.
There is a story about Buddhist monks who are playing this
puzzle with 64 stone disks. The story claims that when the monks finish moving
the disks from one post to a second via the third post, time will end.
