The knights are numbered from 1 to n in order around the table. The knights agree that they will leave the table using the following algorithm. The knights pick a number p between 1 and n, inclusive. Then starting with knight #1, p knights are skipped and the next knight leaves the table. For example, if there are 12 knights as in the picture and p = 6, then knights 1,2,3,4,5,6 are skipped and knight #7 leaves. After the knight leaves, the knights repeat the previous step again starting with the next knight. Continuing the example, knights 8,9,10,11,12,1 are skipped and knight #2 leaves next. This repeats until all of the knights have left the table. For this example, with n = 12 and p = 6, then the knights leave in the following order: [7, 2, 10, 6, 4, 3, 5, 9, 1, 8, 11, 12].
You can model this problem using a queue. First put the numbers from 1 to n into the queue in order. Then remove and insert p times to skip p knights. Then remove once from the queue (but don't re-insert) to find out which knight leaves next. Repeat this process until the queue is empty.
-
Compute the order that the knights leave the table if there are 10 knights
around the table and p = 5. Show the contents of the queue after each
knight leaves the table. (You should have 10 pictures of queues.)
- Write a method that has two parameters, n and p, that returns an ArrayList of integers that gives the order that the knights leave the table for the given values of n and p. You may assume that n > 0 and 1 ≤ p ≤ n. Your method must use a FIFOQueue to compute the solution.
public static void reverse(FIFOQueue<String> q) {
}
-
Rewrite the dequeue operation so that it removes and returns the
largest element of the queue. You may assume that type E
implements Comparable.
- What is the runtime complexity of your new dequeue method if there are n elements in the queue? Explain your answer.
-
Write a method that has one parameter,
an ArrayList<String>. This method should
use an enhanced for-loop (implicit iterator)
to print out all of the strings
in this array list that are longer than 10 characters.
You may assume that all string references in the array list
are non-null.
- Repeat part (a) using an explicit iterator
(instead of using the enhanced for-loop).
- Write a method that has one parameter, an ArrayList<String>. This method should use an iterator to remove all of the strings in this array list that contain the character '!'.
public class Worker {
private String name;
private double rate; // hourly wage (e.g. 12.25)
private static final double minimumHourlyWage = 7.25;
/**
* Creates a new worker given the name and initial pay rate.
* If the initial rate is less than the current minimum hourly wage,
* the rate for this worker is set to the minimum hourly wage.
* @param workerName The name for this worker.
* @param initRate The initial hourly pay rate for this worker.
*/
public Worker(String workerName, double initRate) {
name = workerName;
if (initRate < minimumHourlyWage)
rate = minimumHourlyWage;
else
rate = initRate;
}
/**
* Returns the current weekly salary for this worker. The
* salary is computed as a flat salary assuimng 40 hours of
* work regardless of hours actually worked.
* @return The current weekly salary for this worker.
*/
public double getSalary() {
return rate * 40.0;
}
/**
* Returns the name of this worker.
* @return The name for this worker.
*/
public String getName() {
return name;
}
/**
* Sets the hourly pay rate for this worker to the new rate given.
* If the new rate is less than the current minimum hourly wage,
* the rate for this worker is set to the minimum hourly wage.
* @param newRate The new rate for this worker.
*/
public void setRate(double newRate) {
if (newRate < minimumHourlyWage)
rate = minimumHourlyWage;
else
rate = newRate;
}
}
-
Add equals and toString methods to the
Worker class so that they override the methods inherited from
Object. Two workers are considered equal if their pay rates
are the same.
-
Create a subclass of Worker
named HourlyWorker that has an additional
int field named hoursWorked. An hourly worker is
paid at the worker's pay rate for up to the first 40 hours and 1.5 times
the pay rate for any additional hours worked beyond 40 hours.
Two workers are considered equal if they have the
same rate AND they work the same number of hours. This class should
provide the ability to set the hourly rate to a new value and to set the
hours worked to a new value.
The constructor for your subclass should contain three parameters to set the name, rate and hours worked. (If the hours worked is less than 0, set the hours worked to 0.) Override any methods that need to be overridden and add any new methods that are absolutely necessary. Do not add any additional fields or methods that are not necessary. Do not change any part of the original Worker class except for code you need for part (a).
public boolean add(E element) {
add(element); // add to parent array list
remove(0); // remove last element from parent array list
return true;
}
Explain why this implementation is incorrect. What happens if he tries to run this method?
LIFOStack<Integer> s; s = new ArrayStack<Integer>(); s.push(1); s.push(2); s.push(3); s = new ListStack<Integer>(); s.push(4); s.push(5); s.push(6);
