Java Reference
In-Depth Information
Exercise 7.30 describes a method that returns all the sums that can be
formed from a collection of items. Implement method getOriginalItems ,
which takes as parameter a List representing all the sums and returns
back the original input. For instance if the parameter to getOriginalItems
is [ 0, 3, 4, 7, 7, 10, 11, 13 ], then the return value is a list containing [ 3,
4, 7 ]. You may assume that there are no negative items in the output (and
thus the input).
7.43
Repeat Exercise 7.43, handling the case where there are negative
items. This is a much harder version of the problem.
7. 4 4
Let A be a sequence of N distinct sorted numbers with
. Let B be a sequence of numbers, defined by
( i < j ). Let D be the sequence obtained by sorting B .
Both B and D may contain duplicates. Example: A = 0, 1, 5, 8. Then
D = 1, 3, 4, 5, 7, 8. Do the following.
a.
A 1 A 2
,
,
,
A N
7. 4 5
A 1
=
0
NN 1
(
-
)
2
B ij
=
A j A i
-
,
Write a program that constructs D from A . This part is easy.
b.
Write a program that constructs some sequence A that corresponds
to D . Note that A is not unique. Use a backtracking algorithm.
Consider an N × N grid in which some squares are occupied. Two
squares belong to the same group if they share a common edge. In
Figure 7.30 there is one group of four occupied squares, three groups
of two occupied squares, and two individual occupied squares.
Assume that the grid is represented by a two-dimensional array. Write
a program that
7. 4 6
figure 7.30
Grid for Exercise 7.46
Search WWH ::




Custom Search