DEVELOPING EFFICIENT ALGORITHMS - Introduction to Java Programming: Comprehensive Version - page 854

*22.5

( Same-number subsequence ) Write an O ( n ) program that prompts the user to
enter a sequence of integers ending with 0 and finds the longest subsequence
with the same number. Here is a sample run of the program:

Enter a series of numbers ending with 0:
2 4 4 8 8 8 8 2 4 4 0
The longest same number sequence starts at index 3 with 4 values of 8

*22.6

( Execution time for GCD ) Write a program that obtains the execution time for
finding the GCD of every two consecutive Fibonacci numbers from the index
40 to index 45 using the algorithms in Listings 22.3 and 22.4. Your program
should print a table like this:

40 41 42 43 44 45

Listing 22.3 GCD
Listing 22.4 GCDEuclid

( Hint : You can use the following code template to obtain the execution time.)

long startTime = System.currentTimeMillis();
perform the task;
long endTime = System.currentTimeMillis();
long executionTime = endTime - startTime;

**22.7

( Closest pair of points ) Section 22.8 introduced an algorithm for finding the
closest pair of points using a divide-and-conquer approach. Implement the
algorithm to meet the following requirements:

Define the classes Point and CompareY in the same way as in Programming
Exercise 20.4.

■

Define a class named Pair with the data fields p1 and p2 to represent two
points, and a method named getDistance() that returns the distance
between the two points.

■

Implement the following methods:

■

/** Return the distance of the closest pair of points */
public static Pair getClosestPair( double [][] points)

/** Return the distance of the closest pair of points */
public static Pair getClosestPair(Point[] points)

/** Return the distance of the closest pair of points
* in pointsOrderedOnX[low..high]. This is a recursive
* method. pointsOrderedOnX and pointsOrderedOnY are
* not changed in the subsequent recursive calls.
*/
public static Pair distance(Point[] pointsOrderedOnX,
int low, int high, Point[] pointsOrderedOnY)