Java程序辅导
C C++ Java Python Processing编程在线培训 程序编写 软件开发 视频讲解
C C++ Java Python Processing编程在线培训 程序编写 软件开发 视频讲解
Fall 2021
CS159 - Advanced Programming
Programming Assignment 5
1. Learning Objectives
This assignment is designed to help you learn to think recursively and to write recursive methods. It may also
give you some experience with test-driven development (TDD).
2. Overview
Nearby is a (fictitious) company that designs and develops software and hardware for
use in personal navigation systems, en-route and mobile commerce applications,
location-based services, and geographic tracking/location services.
You have been tasked with helping them develop the soon-to-be-released product named
AnimalTracz.
2.1. About the Product
AnimalTracz is a remote sensing system that can be used to locate wayward pets. The hardware consists of a
chip and a sensor. Each animal of concern has a small chip inserted under its skin. The sensor can then be
instructed to scan a square grid (of any size) to determine if a particular animal is in the grid.
The sensor has one significant limitation, it can only perform 50 scans on a single charge. Hence, since the
typical grid has 512x512 cells (i.e., 262,144 cells in total), the algorithm they originally thought they would use
to locate an animal (i.e., using a nested loop that scans all 262,144 of the 1x1 cells) does not work.
2.2. About the Current Assignment
As a result, Nearby has asked you to design and implement an algorithm (and encapsulate it in a class named
Locator) that can identify the cell that contains a particular animal. (Note: A particular animal can be in at
most one cell.)
2.3. Existing Code
The classes that comprise the GUI are available for download from the following URL:
-1-
https://w3.cs.jmu.edu/bernstdh/web/cs159/pa 5 /pa 5 widgets.jar
The source code for the main class is available for download from the following URLs:
https://w3.cs.jmu.edu/bernstdh/web/cs159/pa 5 / AnimalTracz .java
If you have trouble downloading from the links above, you can try using the links at
https://w3.cs.jmu.edu/bernstdh/web/cs159/pa 5 /downloads.php
instead.
3. Background Information
The graphical user interface (GUI) team, working with the hardware team, has created some simple prototype
"widgets" and a main class (named AnimalTracz.java) that can be used for system testing. You must not
change the main class.
The relationships between all of the components are illustrated in the following UML class diagram:
Note that all classes (except the Point class) are in the default package.
-2-
3.1. About the Main Class
The main class does three important things: constructs a Sensor object (for a given animal), constructs a
Locator object (passing the constructor the Sensor to use), and calls the Locator object's search()
method passing it the square grid that contains the entire search area.
3.2. About the Sensor Class
The Locator class that you are writing will interact only with the Sensor class, and only using the scan()
method. This method is passed the square grid/sub-grid to scan (x and y are the upper-left corner of the grid/sub-
grid and width is the width and height of the square). It returns -width (i.e., the negative of the width) if the
animal is not in the square grid/sub-grid and +width (i.e., the width) if the animal is in the square grid/sub-grid.
3.3. About the SensorDisplay Class
The Sensor class uses the SensorDisplay class to present information to the user. A SensorDisplay
object looks something like the following:
-3-
Areas that were scanned but did not contain the animal of interest are shaded in gray. The area that is currently being
scanned is the solid red square (which is delineated by red lines to make it easier to identify). In this example, the area
cell that is currently being scanned has an upper-left cell of (144,304) and is 16 cells wide and 16 cells high.
3.4. The Test Area
The test area is area in and around the main JMU campus (as illustrated above). This area is divided up into 512x512
grid cells of equal size. As is traditional in computer graphics applications, the upper-left corner is at (0,0), the x-
coordinate increases from left to right, and the y-coordinate increases from top to bottom.
Several animals are known to frequent the test area, including: "DukeDog", "Huey", "Hedwig",
"Flipper", "Remy", "QuadCat", and "Nemo". (Note that spaces have been removed from the names to
make it easier to process the command line arguments.) "DukeDog" is sedentary, so is always at the point (147,
315). The others should be found if you search for them, but their locations are not known.
-4-
For testing purposes, there are four "fake" animals (i.e., permanently mounted sensors) named "UL", "LL",
"UR", and "LR" (that are located at the upper-left, lower-left, upper-right, and lower-right corners of the test
area, respectively).
Also, note that Nearby is thinking about marketing a related product called FacultyFinder that will allow
students to locate faculty members at any time of the night or day. One JMU professor, "Bernstein", has had
a chip inserted under his skin and, hence, can also be located using the sensor. "Bernstein" is also sedentary,
so you can count on finding him at the point (378, 349).
Finally, note that several animals are known to avoid the JMU area (apparently because they had a run-in with
President Alger at a party), including: "Dewey", "Louie", "Dory", "Lassie", "Melman", "Timon",
and "Yax". In other words, these animals should not be found if you search for them.
4. The Class to be Written
You must write the Locator class. In addition to the specifications contained in the UML class diagram above,
the Locator class must conform to the following specifications.
1. Constructor
1.1. The constructor is passed the Sensor that the Locator object must use.
2. The search(int, int, int) Method
2.1. Parameters/Invocation
2.1.1.In general, this method is passed information describing the area to search. The area is defined by
the x and y coordinates of the upper-left cell in the area, and the width (which is also the height) of
the area in cells.
2.1.2.When it is first called (i.e., by the main class), this method is passed 0,0 and the width of the entire
search area (e.g., 0, 0, 512).
2.1.3.This method may (indeed should) invoke itself.
2.2. Purpose
2.2.1. Must search the area defined by the parameters x, y, and width for the animal of interest (i.e.,
the animal that the Sensor was configured to search for).
2.3. Return
2.3.1. Must return null if the animal of interest is not in the area.
2.3.2. Must return a Point object containing the location of the animal of interest if it is in the area.
5. Testing
You are responsible for testing all of the code that you write. You should use the animals mentioned in the
discussion of the test area.
5.1. Controlling the Visualization
The visualization of the scanning process can both help and hinder testing and debugging. For your convenience:
• The Sensor object's scan time controls the speed of the visualization. Longer scan times will make it
easier for you to see what your Locator is doing, shorter scan times will make the program run faster.
-5-
• You can disable the visualization completely by using a Sensor with a scan time of 0.
5.2. Unit Testing Requirements
You must test the Locator class that you write using JUnit (v5). Your tests must be in the default package,
and each test class must include the word "Test" in its name. As in the past, your JUnit tests do not have to
include comments. However, they should conform (wherever possible) to other aspects of the style guide and
must include a class comment that includes the @author tag.
Your JUnit tests must completely cover your code (as determined by EclEmma/JaCoCo).
5.3. Using Test-Driven Development (TDD)
If you haven't done it before, this assignment is a good opportunity to use Test-Driven Development (in which
you write the tests before you write the code that needs to be tested). Though many people use TDD for all of
their projects, it is particularly appropriate for this assignment for several reasons:
• You can't write the Locator class until you understand recursive thinking and you have a recursive
algorithm for solving the problem, both of which will take some time.
• The Locator class is very easy to stub-out (because it only has a constructor and one method).
• The tests are easy to write (for the animals with known locations and the animals which shouldn't be
found).
To encourage you to use TDD, here's a stubbed-out Locator class:
import java.awt.Point;
public class Locator {
public Locator(Sensor sensor) {
}
public Point search(int x, int y, int width) {
return new Point(0,0);
}
}
and the start of a JUnit test suite:
import static org.junit.jupiter.api.Assertions.*;
import org.junit.jupiter.api.Test;
import java.awt.Point;
public class LocatorTest {
@Test
public void upperLeftTest() {
-6-
Locator locator;
Point result;
Sensor sensor;
sensor = new Sensor("UL", 0);
locator = new Locator(sensor);
result = locator.search(0, 0, 512);
assertEquals(new Point(0, 0), result);
}
}
5.4. System Testing
Obviously, you will only be able to write JUnit tests for the animals with known locations. You should, however,
perform system tests using the AnimalTracz driver for all of the animals discussed above (since you do know
which animals should be found and which animals shouldn't be found).
6. Submission
You must submit (using Autolab) a .zip file named pa5.zip that contains:
1. Your implementation of the Locator class.
2. Your JUnit tests.
All of the files must be at the top-level of the .zip file (since they are all in the default package). There is no limit on
the number of submissions and no penalty for excessive submissions.
7. Grading
Your code will first be graded by Autolab and then by the Professor. The grade you receive from Autolab is the
maximum grade that you can receive on the assignment
7.1. Autolab Grading
Your code must compile (in Autolab, this will be indicated in the section on "Does your code compile?"), all
class names and method signatures must comply with the specifications (in Autolab, this will be indicated in the
section on "Do your class names, method signatures, etc. comply with the specifications?"), and your code
must conform to the style guide for you to receive any points on this assignment. Autolab will then grade your
submission as follows:
Passing your Tests (SelfTests): 10 points (All or Nothing; Required)
Coverage of your Tests (Coverage): 30 points (Partial Credit Possible)
Correctness (Correctness): 60 points (Partial Credit Possible)
7.2. Manual Grading
After the due date, the Professor may manually review your code. At this time, points may be deducted for
inelegant code, inappropriate variable names, bad comments, etc.
-7-
8. Hints/Advice
This assignment is very different from any assignment you have worked on so far. So, the following hints/advice
may be particularly useful.
8.1. Allocating Your Time
Almost all of your time on this assignment should be spent thinking; very little time should be spent
typing/compiling/etc. This is because very few lines of code are needed to complete this assignment.
8.2. Avoiding A Commonly-Used Process
Despite our advice, students in CS159 sometimes (often?) use a trial-and-error process to complete assignments. That
is, they try different things (without much thought) until they find one that seems to work. This process is sometimes
referred to as "10,000 monkeys at 10,000 keyboards".
It is very unlikely that you will complete this assignment if you use such a process. In other words, trial-and-error is
unlikely to lead to a correct algorithm. Thinking, on the other hand, may.
8.3. Before You Start Thinking
Before you start thinking about building a full-fledged Locator class, you might want to play around a little bit
to get a feeling for how the Sensor class works. For example, here's a Locator that scans the whole area and
then scans some cells around the CS building.
import java.awt.Point;
public class Locator {
private Sensor sensor;
public Locator(Sensor sensor) {
this.sensor = sensor;
}
public Point search(int x, int y, int width) {
int resultOfScan;
Point resultOfSearch;
resultOfSearch = null;
// Check the whole area
resultOfScan = sensor.scan(x, y, width);
if (resultOfScan < 0) { // The animal isn't in the area
resultOfSearch = null;
} else { // The animal is in the area so let's search some more
// Try some cells around the CS building
for (int xx=360; xx<380; xx++) {
resultOfScan = sensor.scan(xx, 349, 1);
if (resultOfScan == 1) {
-8-
resultOfSearch = new Point(xx, 349);
break;
}
}
}
return resultOfSearch;
}
}
8.4. Recommended Approach
This assignment will be much easier to complete if your algorithm is recursive. Indeed, it is possible to write a
recursive algorithm that contains fewer than 10 lines (though your algorithm may, and probably should, have
more than that).
Remember that there are two parts of a recursive algorithm:
• The part of the algorithm that handles the "base" case.
• The part of the algorithm that moves "difficult" cases toward the "base" case (i.e., the refinement part of
the algorithm).
The first thing to think about is how to define the "base" case. To do so, suppose your Locator calls the
scan() method in the Sensor class. When is its job really easy?
The second thing to think about is what you need to do to refine other cases (i.e., to take "difficult" cases and
move them closer to the easy case).
Note: It is tempting to think that the "base" case is when the animal being searched for isn't found. However, this
is not correct. While this is, indeed, a simple case, the "base" case is defined in terms of the inputs, not the
outputs. Also, remember that the goal is to create a refinement process that moves "difficult" cases towards the
base case and there is no way to move a "difficult" case in which the animal is found to the case in which it isn't
found.
9. Looking Back - The Big Picture
By the time you complete this assignment you should have learned many things, including but not limited to the
following.
• Thinking recursively is rather different from other kinds of thinking.
• Recursive algorithms are very powerful for some kinds of problems.
• Test-driven development is an especially good process to use when the problem itself is difficult to
understand.
-9-