Transcript CSC 205 lect24

CSC 205 – Java Programming II
Lecture 24
March 6, 2002
The Application Interface
import java.util.*;
public interface Application {
// Postcondition: true has been returned if pos could be on a
//path to a goal position. Otherwise, false has been returned.
public boolean valid (Position pos);
// Postcondition: the position specified by pos has been
//marked as being on a path to a goal position.
public void record (Position pos);
// Postcondition: true has been returned if pos is a goal
//position. Otherwise, false has been returned.
public boolean done (Position pos);
The Application Interface
// Postcondition: the position specified by pos has been
//marked as not being on a path to a goal position.
public void undo (Position pos);
// Postcondition: a string representation of this Application has
//been returned.
public String toString();
// Postcondition: an iterator over the positions directly
//accessible from pos has been returned.
public Iterator iterator (Position pos);
} // interface Application
The BackTrack Class
import java.util.*;
public class BackTrack {
Application app;
// Postcondition: this BackTrack has been initialized from app.
public BackTrack (Application app) {
this.app = app;
} // constructor
// Postcondition: a solution going through pos has been attempted.
public boolean tryToSolve (Position pos) {
……
} // method tryToSolve
} // class BackTrack
The tryToSolve Method
boolean success = false;
Iterator itr = app.iterator (pos);
while (!success && itr.hasNext()) {
pos = (Position)itr.next();
if (app.valid (pos)) {
app.record (pos);
if (app.done (pos))
success = true;
else {
success = tryToSolve (pos);
if (!success)
app.undo (pos);
} // not done
} // a valid position
} // while
return success;
The Eight Queens Problem
• Place eight queens on a chessboard
• No queen is under attack from any other
queen
Discussions
Binary Searching
public interface Comparable {
int compareTo(Object o);
}
The int returned by x.compareTo (y) is:
< 0, x is less than y;
= 0, if x.equals (y);
> 0, if x is greater than y.
Sequential Search
• SEQUENTIAL SEARCH OF ARRAY a
FOR ELEMENT key:
• START AT INDEX 0:
– COMPARE EACH ELEMENT IN a TO Key
• UNTIL
– SUCCESS (key FOUND) OR
– FAILURE (END OF A REACHED).
Sequential Search
// Precondition: all the elements in the array a are in the
//
same class, and that class implements the
//
Comparable interface.
// Postcondition: if there is an index i such that
//
((Comparable) a [i]).compareTo (key)
//
returns 0, then such an index has been
//
returned. Otherwise, -1 has been returned.
//
The worstTime (n) is O (n).
public static int sequentialSearch (Object[ ] a, Object key) {
for (int i = 0; i < a.length; i++)
if ((Comparable) a [i].compareTo (key) == 0)
return i;
return –1;
} // sequentialSearch
A Sorted Array
a [0] ANDREW
a [1] BRANDON
a [2] CHRIS
a [3] CHUCK
a [4] GEOFF
a [5] JASON
a [6] MARGARET
a [7] MARK
a [8] MATT
a [9] ROB
a [10] SAMIRA
Binary Search (recursive)
public static int binarySearch(Object[ ] a, int first, int last,
Object key) {
if (first <= last) {
int mid = (first + last) / 2;
Object midVal = a [mid];
int comp = ((Comparable)midVal).compareTo (key);
if (comp < 0)
return binarySearch (a, mid + 1, last, key);
if (comp > 0)
return binarySearch (a, first, mid - 1, key);
return mid; // key found
} // if first <= last
return -first - 1; // key not found; belongs at a [first]
} // method binarySearch