Java Reference
In-Depth Information
public static void fun(int m, int n) {
if (n > 0) {
fun(m-1, n-1);
System.out.printf("%d ", m);
fun(m+1, n-1);
}
}
17.
What is returned by the call
test(7, 2)
of the following recursive function?
public static int test(int n, int r) {
if (r == 0) return 1;
if (r == 1) return n;
if (r == n) return 1;
return test(n-1, r-1) + test(n-1, r);
}
18.
Consider points (
m
,
n
) in the usual Cartesian coordinate system where
m
and
n
are positive
integers
. in a
north-east
path from point a to point B, one can move only
up
and only
right
(no
down
or
left
movements are allowed). Write a function that, given the coordinates of any
two points a and B, returns the
number
of north-east paths from a to B.
19.
the 8-queens problem can be stated as follows: place 8 queens on a chess board so that
no two queens attack each other. two queens attack each other if they are in the same row,
same column or same diagonal. Clearly, any solution must have the queens in different rows
and different columns.
We can solve the problem as follows. place the first queen in the first column of the first row. next, place
the second queen so that it does not attack the first. if this is not possible, go back and place the first
queen in the next column and try again.
after the first two queens have been placed, place the third queen so that it does not attack the first two.
if this is not possible, go back and place the second queen in the next column and try again. and so on.
at each step, try to place the next queen so that it does not conflict with those already placed. if you
succeed, try to place the next queen. if you fail, you must
backtrack
to the previously placed queen and
try the next possible column. if all columns have been tried, you must backtrack to the queen before
this
queen and try the next column for
that
queen.
the idea is similar to finding a path through a maze. Write a program to solve the 8-queens problem. use
recursion to implement the backtracking.
20.
Write a program to read
n
(<= 10) and print every possible combination of
n
items. For
example, if
n
=
3
, you must print the following:
1
1 2
1 2 3
1 3
2
2 3
3
Search WWH ::
Custom Search