CS100A Fall 1998 Assignment 5 Due beginning of lecture, Thursday, October 15 Array, while loops, and loop invariants
The assignment can be handed in earlier at Carpenter. Type your name, id, and section day/time/instructor at the top of your assignment.
Working with others Practice question What to do for this assignment
Working with others.
You may work with one other person. If you do, then you must do the work together. It is not proper for one person to do the work and then to add someone else's name to it. If you work with someone, hand in only one assignment; put both persons' names, id's, and section days/times/instructors on it.Practice questions. The solutions appear at the end of this handout. Note: Although you are not handing in these practice questions, start getting in the habit now of writing loop invariants.
1. Write a procedure
to print the maximum number in a nonempty array of double's.
2. Write a function practiceReverse
that has a parameter k that is an array of ints and returns a new array with
contents equal to the reversal of k; do NOT modify k. For example,
if
k is the array [13 7 -42 0 21 -3 7],
then your function should return the array [7 -3 21 0 -42 7 13].
3. Write a function that has a parameter x that is an array of double's and that returns a new array s of the same length such that s[i] is the average of x[i] and its "circular neighbors". We define this term; while reading the definition, think of joining the ends of x[] to form a circle, making the original ends neighbors.
*For j in the range 0..x.length-2, x[j+1] is
the right neighbor of x[j]. The right neighor of x[x.length-1] is x[0].
*For j in the range 1..x.length-1,
x[j-1] is the left neighbor of x[j]. The left neighor of x[0] is x[x.length-1].
Examples:if x = [], s = [] if x = [2], s = [2] since (2+2+2)/3 = 2 if x = [0 9], s = [6 3] since (9+0+9)/3 = 6 and (0+9+0)/3 = 3 if x = [1 2 3 4.5 -6], s = [-1 2 3.1666 0.5 -0.1666]
Hint: You might find the remainder operator % useful, but you are not required to use it.
4. Write a method main that reads a sequence of positive integers followed by -1. The program should print the numbers read from the input, but when duplicate copies of a number appear ANYWHERE in the input, the number should be printed only once. There are at most 100 distinct numbers in the input. For example, if the input is
input: 5 3 3 3 12 7 7 3 3 3 8 7 5 1327 5 -1 duplicates: x x x x x x x x x
the output should be 5 3 12 7 8 1327
Hint:
You will need to store the numbers previously read in and printed.What to do for this assignment. Write and hand in answers to the following 6 questions. You may do the assignment with paper and pencil. However, it will be useful for you to put code you write into a Codewarrior project (using the CUCSApplication stationery) and test it --this will uncover mistakes. Test the code by placing suitable calls to it (and other code) in the beginning of method main.Note that testing in this fashion is not necessary.
1. Write a function with two parameters --both arrays of ints-- that returns true if the arrays are equivalent (i.e. have the same numbers in the same positions) and false otherwise. Note that this requires the arrays to be equally long, otherwise one will have numbers in positions that the other does not. For example, arrays x and y below are equivalent to each other, but no other pair of arrays are equivalent:
v: [3 5] w: [3 5 3 0 0] x: [3 5 3 0] y: [3 5 3 0] z: [0 3 5 3]
2. Write a procedure (not a function) named reverse that has a parameter h that is an array of int's and an int j and that reverses the contents of h[0..j]. For example, if h is
h: [13 7 -42 0 21 -3 7]
then reverse (h, 3) would change array h to:
h: [0 -42 7 13 21 -3 7].
Notes: Unlike the practice question, your code must work in place, i.e. modify h without using any other arrays. Unlike the practice question, you do not reverse the entire array: only h[0..j]. You are to write a procedure that changes the parameter, not a function.
3. Write a function to find the second largest number in its parameter, which is an array x of length at least 2 and which contains distinct integers. For example, the second largest number in [2 48 -28 -1000] is 2. You may use the following invariant:
// invariant: 2 <= i <= x.length and b is the largest number in x[0..i-1] and c is the second largest distinct number in x[0..i-1]
4. Write a method that has an array t of integers as its parameter and that prints (after computing) the following:
Your code should print brief but meaningful labels with the numbers and give sensible results. For example, the average is not defined if there are no numbers, so print a little message to this effect. Note that if there are no even numbers, then the product of the even numbers is 1.
For example, for t = [1 -2 3 3], you could print "average:
(1-2+3+3)/4 = 1.25, 3 odd numbers, product of the even numbers is -2".
5. Write a procedure to change its parameter (an array x[]
of integers) so that all negative numbers appear before all non-negative numbers. You may
NOT use another array and must not lose any elements of x. For example, if x is
[3 -2 0 4 -17 24 82],
then two equally valid outcomes for x are
[-2 -7 3 0 4 24 82] and [-7 -2 0 3 4 24 82].
You must use the following invariant, which we first depict pictorially:
0 i j n=x.length _________________________________________ x | negative | unprocessed | non-negative | ----------------------------------------- // invariant: 0 <= i <= j <= n = x.length // x[0..i-1] contains negative, processed numbers // x[i..j-1] contains unprocessed numbers // x[j..n-1] contains non-negative, processed numbers
Hint: At each iteration, process x[i] --if it is non-negative, add it to the
non-negative region; if it is negative, add it to the negative region.
Hint: You do not need a loop to move x[i] to the negative region (just adjust i)
Hint: You do NOT need a loop to move x[i] to the non-negative region.
6. Write a function that has a parameter d that represents a day within the year 1998 and that returns the corresponding date. For example,
for d = 2, return the String "2 January 1998" and
for d = 35, return the String "4 February 1998".
Use an array months and an array daysInMonth, which are declared as follows.
static
String[ ] months= {"January", "February", "March", ...,
"December"};
static int
[ ] daysInMonth= {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
You should use a loop to search for the right month. For the loop, use two int variables m and days and use the invariant
Invariant: day d occurs in or after
month m and
days is the number of days in months 1..(m-1).
Answers to practice problems
1. // Print the penultimately large value in b
// It is assumed that b has at least one value
public static void maxi(double[ ] b) {
int c= b[0];
int i= 1;
// Invariant: 0<=i<=b.length
and
//
c is the largest value in b[0..i-1]
while (i < b.length)
{
if (b[i] > c) {c= b[i];}
i= i+1;
}
System.out.println("Max
number in array is " + c);
}
2. // Return the reverse of k
public static int[] practiceReverse(int[] k) {
int[ ] r= new
int[k.length];
int i= 0;
// Inv: r[0..i-1] =
rev. of k[k.length-i..k.length-1]
while (i <
k.length)
{r[i]= k[k.length-i-1]; i= i+1;}
return r;
3. // See assignment 5 for the specification
public static double[] f(double[ ] x) {
int[ ] s= new
double[x.length];
int i= 0;
// Invariant: s[0..i-1]
= contains its final values
while (i <
x.length) {
s[i]= (s[(i-1+ x.length) % x.length] +
s[i] + r[(i-1) % x.length])/3.0;
i= i+1;
}
return s;
}
4. // See assignment 5 for the specification
public static void main(String[] args) {
TokenReader in= new TokenReader(System.in);
int g= in.readInt( );
int[] nd= new int[100];
int k= 0;
// Inv: g is the last number read,
// all distinct nos. before g
are printed,
// all distinct nos. before g
are in nd[0..k-1];
while (g != -1) {
if (! inarray(nd, g) ) {
System.out.println(g);
nd[k]= g; k= k+1;
}
i= i+1;
}
}
// Return value of "c is in b"
static public bool inArray(int[ ] b, int c) {
int i= 0;
// Invariant: c is not in b[0..i-1]
while (i < b.length && c != b[i])
i= i+1;
return i < b.length;
}