| CPSC 124 | Introduction to Programming | Spring 2008 |
Write a program called PrintReverse.java, which reads in integers from the user until the user enters a negative integer, and then prints those integers to the screen in reverse order (excluding the negative integer). Below is an example run (user input is in bold):
Enter a sequence of integers >= 0. Enter a negative integer to stop. Enter number: 12 Enter number: 2 Enter number: 5 Enter number: -1 Your numbers in reverse order: 5 2 12
Note: you cannot make any assumptions about the number of integers that the user will enter. To do this, you will need to conservatively size your array and if your array is ever filled, you will have to resize your array as discussed in class and in Section 7.3.2 of the book. You will also need to keep track of the portion of the array that is currently being used. For example, if your array has size 100 and the user enters only 7 non-negative integers then only the first 7 entries in the array are used (in this case, you should print out 7 numbers not 100 numbers!). You may also want to test your program using a small initial size for your array so that you can verify that your resizing works.
Write a program called PrintMatrix.java that reads in 9 integers from the user and then prints them out in a 3x3 matrix. It should also print out the sum of each row and column. Below is an example run (user input is in bold):
Enter number 1: 8 Enter number 2: 3 Enter number 3: 9 Enter number 4: 0 Enter number 5: 10 Enter number 6: 3 Enter number 7: 5 Enter number 8: 17 Enter number 9: 1 Matrix: Row 1: 8 3 9 Row 2: 0 10 3 Row 3: 5 17 1 Row totals: 20 13 23 Column totals: 13 30 13
You may want to use a multi-dimensional array for this problem, although you are not required to so long as the program works correctly.
Answer:
/* Class for reading numbers into 3x3 array and
printing them out along with row and column totals.
Author: Marc Corliss
*/
class PrintMatrix {
// main() method
public static void main(String[] args) {
// array where we store numbers
int[][] matrix;
// array where we store row sums of matrix
int[] rowTotals;
// array where we store column sums of matrix
int[] colTotals;
// initialize arrays
matrix = new int[3][3];
rowTotals = new int[3];
colTotals = new int[3];
// read in 9 integers from user and store in matrix
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
System.out.print("Enter number " + (i*3+j+1) + ": ");
matrix[i][j] = TextIO.getlnInt();
}
}
// add a blank line between reading and writing matrix
System.out.println();
// print out matrix
System.out.println("Matrix:");
// loop through each row
for (int i = 0; i < 3; i++) {
System.out.print("Row " + (i+1) + ":");
// loop through each column
for (int j = 0; j < 3; j++) {
System.out.print(" " + matrix[i][j]);
// keep track of row and column sums
// rowTotals indexed with i since i represents current row
rowTotals[i] += matrix[i][j];
// colTotals indexed with j since j represents current column
colTotals[j] += matrix[i][j];
}
// print new line for each row
System.out.println();
}
// add a blank line between writing matrix and writing row/col totals
System.out.println();
// print out row totals
System.out.print("Row totals:");
for (int i = 0; i < 3; i++)
System.out.print(" " + rowTotals[i]);
// print new line after print out all 3 row totals
System.out.println();
// print out column totals
System.out.print("Column totals: ");
for (int i = 0; i < 3; i++)
System.out.print(" " + colTotals[i]);
// print new line after print out all 3 column totals
System.out.println();
}
}
A prime number is a number which is only (evenly) divisible by itself and 1. In this exercise you will use the Sieve of Eratosthenes algorithm for finding prime numbers. Note: you may not use the algorithm for finding prime numbers that was presented in class. You must use the algorithm described below.
To use the sieve, write down all of the numbers from 2 to some number n and then apply the following (partial) algorithm:
for each number from 2 to n do
if the number hasn't been crossed off,
it is a prime
cross off all multiples of that number
As an example, let's use the sieve to find the prime numbers between 2 and 15. We start with all the numbers listed:
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
An array can be very handy for implementing this algorithm. The idea is to use an array of booleans to keep track of what numbers have and haven't been crossed off. We'll use a value of false in slot k to indicate that the number k hasn't been crossed off, and a value of true to indicate that the number has been crossed off. At the beginning all of the slots are initialized to false. Now, apply the algorithm above starting with slot 2 - if the number hasn't been crossed off, then the value stored in its slot is false; crossing off a number means setting the value in the appropriate slot to true. (The values in slots 0 and 1 will never be used.)
Your task is to write a program called FindPrimes.java to find prime numbers using the Sieve of Eratosthenes, using a boolean array as outlined above. The program should prompt the user for a number n which is the upper end of the range, and should then print all of the prime numbers between 2 and n (including n if it is prime). Make sure your array is large enough to have a slot numbered n.
Answer:
/* A class for finding primes from 2 to n using the Sieve
of Eratosthenes algorithm.
Author: Marc Corliss
*/
class FindPrimes {
// main() method
public static void main(String[] args) {
// array indicating which numbers are primes
// (true means prime, false means non-prime)
boolean[] primes;
// n is the size of the array, read from the user
int n;
// some error checking, n must be >= 2
n = 0;
while (n < 2) {
// prompt the user for n and read it in
System.out.print("Enter a number >= 2: ");
n = TextIO.getlnInt();
// check that it's greater than 2
if (n < 2) {
// if not >= 2, print error message
System.out.println("Error: input < 2");
}
}
// construct the primes array using size n+1,
// must use size n+1 since array we'll need to be able to
// access from 0 to n (n+1 total elements). Note: we could
// shift left by two since ignoring 0 and 1, however, by not
// doing this if primes[i] is true, then i is prime (not i+2)
primes = new boolean[n+1];
// initialize all elements to true, at the
// beginning all elements are considered prime
for (int i = 2; i <= n; i++) {
primes[i] = true;
}
// loop from 2 to n checking if numbers are prime
for (int i = 2; i <= n; i++) {
// if primes[i] is true, then found a prime
if (primes[i]) {
// print out prime (i.e., index of the array)
System.out.println(i);
// loop from 2i to n, crossing off multiples of this
// prime (i.e., setting elements in the array to false)
for (int j = i*2; j <= n; j += i) {
primes[j] = false;
}
}
}
}
}