21
*6.13 (Future tuition) Print a table that prompts the
user to enter the current tuition and displays a table that
displays how many years the tuition will be doubled if the
tuition is increased by 3%, 4%, and up to 10% annually.
Here is a sample run:
<output>
Enter the current year tuition: 15000 <enter icon>
Rate Number of Years
*6.14 (Test prefix) Write the following function that
returns true if string s1 is a prefix for string s.
public static boolean isPrefix(String s, String s1)
Write a test program that prompts the user to enter string
s and s1, and displays whether s1 is a prefix for s. Here
is a sample run:
Extra Exercise for Chapter 7
7.1
Write a program that checks if all the input numbers cover 1 to 99. Each ticket for the Pick–10 lotto
has 10 unique numbers ranging from 1 to 99. Suppose you buy a lot of tickets and like to have them
22
cover all numbers from 1 to 99. Write a program that reads the ticket numbers from a file and checks
whether all numbers are covered. Assume the last number in the file is 0. Suppose the file contains
the numbers
<video note>Lotto numbers
Your program should display
The tickets cover all numbers
*7.2 (Area of a polygon) Write a program that prompts the user to enter the points of a convex polygon and
display its area. Assume that the polygon has six end points and the points are entered clockwise. For the
definition of a convex polygon, see http://www.mathopenref.com/polygonconvex.html. Hint: the total area
of a polygon is the sum of the areas of the small triangles as shown in Figure 7.1.
p0
p1
p2
p3
p4
p5
Figure 7.1
A convex polygon can be divided into small non–overlapping triangles.
Here is a sample run of the program:
***7.3 (Game: multiple Eight Queens solutions) Exercise 7.22 finds one solution for the Eight Queens
problem. Write a program to count all possible solutions for the Eight Queens problem and
display all solutions.
**7.4 (Occurrences of each digit in a string) Write a method that counts the occurrences of each digit
in a string using the following header:
public static int[] count(String s)
The method counts how many times a digit appears in the string. The return value is an array of
ten elements, each of which holds the count for a digit. For example, after executing int[]
counts = count(“12203AB3”), counts[0] is 1, counts[1] is 1, counts[2] is 2, and
counts[3] is 2.
Write a test program that prompts the user to enter a string and displays the number of
occurrences of each digit in the string.
<end output>
**7.5 (Anagrams) Write a method that checks whether two words are anagrams. Two words are
anagrams if they contain the same letters in any order. For example, silent and listen are
anagrams. The header of the method is:
public static boolean isAnagram(String s1, String s2)
Write a test program that prompts the user to enter two strings and, if they are anagrams,
displays two strings are anagrams, and displays two strings are not anagrams if
they are not anagrams.
*7.6 (Pass a string to check palindromes) Write a program
that checks whether a string is palindrome. The string is
passed as a command-line argument.
**7.7 (Common elements) Write a program that prompts the user to enter two arrays of integers and
displays the common elements that appear in both arrays. Note that the first number in the
input indicates the number of the elements in the list. This number is not part of the list. Here is
a sample run.
25
*7.8 (Evaluate polynomial) Write a method for computing the following polynomial:
01221
01221 … xaxaxaxaxaxa
nnn
nnn ×+×+×++×+×+×
−−
−−
The header of the method is as follows:
public static double evaluatePolynomial(double[] a, double x)
Implement the method using the Horner’s approach introduced in Section 6.7. Write a
test program that prompts the user to enter the order of the polynomial n, and the
coefficients
na
,
1−n
a
,
2−n
a
, …,
1
a
, and
0
a
, and invokes the method to evaluate the
polynomial and displays its result. Here is a sample run:
<output>
7.9 Revise Extra Exercise 7.1 to display the missing numbers. Print the missing numbers in increasing
order separated by exactly one space (all in one line). Your program should ignore the input number if it is
not in the range from 1 to 99. Here are the sample runs:
<output>
Sample Run 1:
Sample Run 2:
Enter the integer numbers from 1 to 99:
26
Note that if no missing numbers, your program should display “The tickets cover all numbers”.
7.10 Revise Programming Exercise 5.39 in the text using a binary search to find the minimum sales you
have to generate in order to make $30000.
7.11 Rewrite Programming Exercise 3.4 using an array. Use an array to store the names for month.
7.12 Rewrite Programming Exercise 3.5 using an array. Use an array to store the names for days in a week.
7.13 Rewrite Programming Exercise 7.1 in the text to compute the grades and display the grade in a
horizontal histogram, as shown in the following sample rune:
<output>
7.14 Rewrite the preceding exercise to display the grade in a vertical histogram, as shown in the following
sample rune:
<output>
27
Extra Exercise for Chapter 8
8.1* (Algebra: 2×2 matrix inverse) The inverse of a square
matrix A is denoted A-1, such that A × A-1 = I, where I is
the identity matrix with all 1s on the diagonal and 0 on
all other cells. For example, the inverse of matrix
43
21
is
−
05.1
15.0
, i.e.,
The inverse of a 2×2 matrix A can be obtained using the
following formula:
=dc
ba
A
−
−
−
=
−
ac
bd
bcad
A1
1
Implement the following method to obtain an inverse of the
matrix:
28
public static double[][] inverse(double[][] A)
The method returns null if ad – bc is 0.
Write a test program that prompts the user to enter a, b,
c, d for a matrix, and displays its inverse
matrix. Here is a sample run:
<Output>
*8.2 (Algebra: solve 3 × 3 linear equations) You can use the
following computations to solve a 3 × 3 system of linear
equation:
3333231
2232221
1131211
bzayaxa
bzayaxa
bzayaxa
=++
=++
=++
29
122133322311312213322113231231332211
333231
232221
131211
|| aaaaaaaaaaaaaaaaaa
aaa
aaa
aaa
A−−−++==
.
Write a program that prompts the user to enter
11
a
,
12
a
,
13
a
,
21
a
,
22
a
,
23
a
,
31
a
,
32
a
,
33
a
,
1
b
,
2
b
, and
3
b
, and displays the result.
If
|
|A
is 0, report that “The equation has no solution”.
<Output>
*8.3 (Algebra: 3 × 3 matrix inverse) The inverse of a square
matrix A is denoted A-1, such that A × A-1 = I, where I is
the identity matrix with all 1s on the diagonal and 0 on
30
all other cells. For example, the inverse of matrix
354
132
121
is
−
−
−
5.05.11
5.05.01
5.05.02
, i.e.,
=
−
−
−
×
100
010
001
5.05.11
5.05.01
5.05.02
354
132
121
122133322311312213322113231231332211
333231
232221
131211
|| aaaaaaaaaaaaaaaaaa
aaa
aaa
aaa
A−−−++==
.
Implement the following method to obtain an inverse of the
matrix:
public static double[][] inverse(double[][] A)
Write a test program that prompts the user to enter
11
a
,
12
a
,
13
a
,
21
a
,
21
a
,
23
a
,
31
a
,
32
a
,
33
a
, for a matrix, and
displays its inverse matrix. Here is a sample
run:
31
8.4* (Statistical report) Modify Listing 8.2 GradeExam.java
to display the percentage of students whose chose A, B, C,
D, or E for each question. The output of the program is as
follows:
<output>
32
8.5* (Sort) Modify Listing 8.2 GradeExam.java to display
student numbers and scores in increasing order as follows:
Student 3: 4
8.6* (Statistical report) Modify Listing 8.2 GradeExam.java
to display the maximum, minimum, mean, and deviation of the
scores. The score is the number of correct answers for each
student. For computing mean and deviation, see Programming
Exercise 7.11 in the book.
8.7 (Average exam score) Use the scores data from Section 8.8 to write a program that
displays the average score for each exam as follows:
Extra Exercise for Chapter 9
*9.1 (Intersecting point) Write the following method that
returns the intersecting point between two lines (p1, p2)
and (p3, p4):
public static Point2D getIntersectingPoint(
Point2D p1, Point2D p2, Point2D p3, Point2D p4);
The method returns null if the two lines are parallel.
Write a test program that prompts the user to enter three
points and displays the center point. Here is a sample run.
(Hint: for finding the intersecting point between two
lines, see Programming Exercise 8.31.)
33
*9.2 (Center of a triangle) Write the following method that
returns the center of a triangle:
public static Point2D getCenterPoint(
Point2D p1, Point2D p2, Point2D p3);
Write a test program that prompts the user to enter three
points and displays the center point. Here is a sample run:
(Hint: for finding the intersecting point between two
lines, see Programming Exercise 8.31.
*9.3 (Geometry: area of a triangle) Rewrite the method for
computing the area of a triangle in Programming Exercise
8.32 using the following method:
public static double getTriangleArea(
Point2D p1, Point2D p2, Point2D p3)
Write a program that prompts the user to enter three points of a triangle and displays the
triangle‘s area. Here is a sample run of the program:
<output>
34
Extra Exercise for Chapter 10
*10.1 (Combination) Combinations in mathematics are the
ways of picking several items from a large group, where
order does not matter. For example, there are 6 ways to
pick 2 items from a group of 4 items. In mathematics, the
number of combinations of picking k items from a group of n
items is denoted as
k
n
C
,
kn C
, or
k
n
.
)!(!
!
knk
n
C
k
n
−
=
Write a method named getNumberOfCombinations(int n, int k)
for computing
k
n
C
using following header:
public static BigInteger getNumberOfCombinations(int n, int k)
Write a test program that prompts the user to enter n and k
and displays
k
n
C
as shown in the following sample run:
<Output>
Enter n: 4 <Enter icon>
*10.2 (Permutation) Permutations in mathematics are the
ways of picking several items from a large group, where
order matters. For example, there are 12 ways to pick 2
items with different orders from a group of 4 items. In
mathematics, the number of permutations of picking k items
with different orders from a group of n items is denoted as
k
n
P
,
kn
P
, or
),( knP
.
)!(
!
kn
n
Pk
n−
=
Write a method named getNumberOfPermutations(int n, int k)
for computing
k
n
P
using following header:
public static BigInteger getNumberOfPermutations(int n, int k)
35
Write a test program that prompts the user to enter n and k
and displays
k
n
P
as shown in the following sample run:
<Output>
*10.3 (Eight Queens) The Eight Queens problem is to find a solution to place a queen in each row on a
chessboard such that no two queens can attack each other. You can use a two–dimensional array to
represent a chessboard. However, since each row can have only one queen, it is sufficient to use a one–
dimensional array to denote the position of the queen in the row. Thus, you can define the queens array
as:
int[] queens = new int[8];
Assign j to queens[i] to denote that a queen is placed in row
i and column j.
Define a class named EQ to represent eight queens in a
chess board with the following members:
1. A private data field queens of the type int[].
2. A no-arg constructor that constructs an object of EQ
default queens values of -1s in the array.
3. A constructor named EQ(int[] queens) that constructs
an object of EQ with the specified queen placement.
4. A method named get(int i) that returns queens[i].
5. A method named set(int i, int j) that sets queens[i]
with j.
6. A method named isSolved() that returns true if all
queens are placed in the board correctly.
7. A method named printBoard() that displays the board
with the queens like the following:
|X| | | | | | | |
| | | | |X| | | |
| | | | | | | |X|
| | | | | |X| | |
| | |X| | | | | |
| | | | | | |X| |
36
| |X| | | | | | |
| | | |X| | | | |
Implement the class and use the following program to test
your class.
*10.4 (Sum integers) Write a program that passes an unspecified number of integers as s single string
to the main method and displays their total, as shown in Figure 10.1.
Figure 10.1
Extra Exercise for Chapter 11
37
**11.1 (Split a string) Write the following method that splits a string into substrings using delimiter
characters.
11.2 (Bin packing with largest object first) The bin packing problem is to pack the objects of various
weights into containers. Assume that each container can hold a maximum of 10 pounds. The
program uses an algorithm that places an object with the largest weight into the first bin in
which it would fit. Your program should prompt the user to enter the total number of objects
and the weight of each object. The program displays the total number of containers needed to
pack the objects and the contents of each container. Here is a sample run of the program:
<output>
Does this program produce an optimal solution, that is, finding the minimum number of
containers to pack the objects? Does the algorithm always find the optimal solution?
*11.3 (Flight time) Design two classes: Flight and Itinerary. The Flight class stores the information about a
flight with the following members:
1. A data field named flightNo of the String type with getter method.
2. A data field named departureTime of the GregorianCalendar type with getter and setter
methods.
3. A data field named arrivalTime of the GregorianCalendar type with getter and setter methods.
4. A constructor that creates a Flight with the specified number, departureTime, and arrivalTime.
5. A method named getFlightTime() that returns the flight time in minutes.
The Itinerary class stores the information about itinerary with the following members:
1. A data field named flgihts of the List<Flight> type. The list contains the flights for the itinerary in
increasing order of departureTime.
2. A constructor that creates an Itinerary with the specified fights.
3. A method named getTotalTime() that returns the total travel time in minutes from the depature
time and the first flight to the arrival time of the last flight in the itinerary.
Implement these two classes and use the follwing program to test these classes.
public static void main(String[] args) {
*11.4 (Parse arguments) Arguments for the main method are passed as strings. Strings enclosed in
quotation marks are considered as one argument. Write a program to parse arguments from a
string. Arguments are separated by spaces. Enclosed strings are considered as one argument.
Your program should prompt the user to enter a string and display the arguments, each per line,
as shown in the following sample run.
<output>
39
public static ArrayList<int[]> getCombinations(int k, int[] source)
For example, getCombination(3, new int[]{10, 20, 30, 40, 50}) returns the list that contains:
[10, 20, 30]
[10, 20, 40]
[10, 20, 50]
[10, 30, 40]
[10, 30, 50]
[10, 40, 50]
[20, 30, 40]
[20, 30, 50]
[20, 40, 50]
[30, 40, 50]
Write a test program that prompts the user to enter n, and n elements for input, and then k, and displays all
the combinations.
<output>
Enter n: 5
Extra Exercise for Chapter 12
*12.1 (Name for both genders) Write a program that prompts
the user to enter one of the filenames described in
Exercise 12.31 and displays the names that are used for
both genders in the file. Here is a sample run:
<Output>
Hint: There are many ways to get the common elements from
the two lists. Most simple way is to use the retainAll
method from an ArrayList. Please look for the information
on how to use the retainAll method from the Java API.
*12.2 (Sort names without duplicates) Write a program that
reads the names from the all the ten files described in
Exercise 12.31, sorts all names (boy and girl names
together, duplicates removed), and stores the sorted names
in one file ten per line.
*12.3 (Sort names with duplicates) Write a program that
reads the names from the all the ten files described in
Exercise 12.31, sorts all names (boy and girl names
together, duplicates allowed), and stores the sorted names
in one file ten per line.
*12.4 (Cumulative ranking) Write a program that obtains the
cumulative ranking for the names in the ten years using the
ranking for each row. The new file is named as the input
file with the extension .new.
*12.6 (Rename files using current date/time) Write a
program that renames a file name. The program checks
whether the file exists. If so, change the file name by
appending the date and time to the file. Pass the filename
from the command line. Here is a sample run:
<Output>