Transcript Data Abstraction and Problem Solving with JAVA

Data Abstraction and Problem Solving with JAVA Walls and Mirrors
Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Recursion: The Mirrors
Data Abstraction and Problem Solving with JAVA:
Walls and Mirrors
Carrano / Prichard
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Recursive Solutions
• Recursion breaks a problem into
several smaller instances of the same
problem.
• Some recursive solutions are
impractical because they are so
inefficient.
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.1
A recursive solution
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Issues for Constructing Recursive
Solutions
• How to define the problem in terms of a
smaller problem of the same type
• How each recursive call diminishes the
size of the problem
• What instance of the problem can serve
as the base case
• As the problem size diminishes, the
base case is reached
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Factorial of n
• Factorial(n) = n*(n-1)*(n-2)*…*1 for n>0
= n*factorial(n-1)
Factorial(0) = 1
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Factorial of n
•
•
•
•
•
•
•
•
•
•
•
•
•
public static int fact(int n) {
// --------------------------------------------------// Computes the factorial of a nonnegative integer.
// Precondition: n must be greater than or equal to 0.
// Postcondition: Returns the factorial of n.
// --------------------------------------------------if (n == 0) {
return 1;
}
else {
return n * fact(n-1);
} // end if
} // end fact
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.2
fact(3)
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.3
A box
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.4
The beginning of the box trace
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.5a
Box trace of fact(3)
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.5b
Box trace of fact(3)
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.5c
Box trace of fact(3)
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Writing a String Backward
• Problem: write a string in reverse order
– Base case: write the empty string
backward
– Strip away the last character
or
– Strip away the first character
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.6
A recursive solution
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
public static void writeBackward(String s, int size) {
// --------------------------------------------------// Writes a character string backward.
// Precondition: The string s contains size
// characters, where size >= 0.
// Postcondition: s is written backward, but remains
// unchanged.
// --------------------------------------------------if (size > 0) {
// write the last character
System.out.println(s.substring(size-1, size));
// write the rest of the string backward
writeBackward(s, size-1); // Point A
} // end if
// size == 0 is the base case - do nothing
} // end writeBackward
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.7a
Box trace of writeBackward(“cat”, 3)
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.7c
Box trace of writeBackward(“cat”, 3)
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
writeBackward2(s)
System.out.println(“Enter writeBackward2, string: “ + s);
if (the string s is empty) {
Do nothing -- this is the base case
}
else {
writeBackward2 (s minus its first character) // Point A
System.out.println(“About to write first character of “ +
“string: “ + s);
Write the first character of s
} // end if
System.out.println(“Leave writeBackward2, string: “ + s);
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.9a
Box trace of writeBackward2(“cat”, 3) in pseudocode
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.9b
Box trace of writeBackward2(“cat”, 3) in pseudocode
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.9c
Box trace of writeBackward2(“cat”, 3) in pseudocode
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.9d
Box trace of writeBackward2(“cat”, 3) in pseudocode
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.9e
Box trace of writeBackward2(“cat”, 3) in pseudocode
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Multiplying Rabbits (The Fibonacci
Sequence)
• Problem: Count the number of rabbits
assuming the following
– Rabbits never die.
– A pair of original rabbits.
– A pair of rabbits gives birth every month,
exactly two months after they are born.
– Rabbits are always born in male-female
pair.
• rabbit(n) = rabbit(n-1) + rabbit(n-2)
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.10
Recursive solution to the rabbit problem
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.11
Recursive calls that rabbit(7) generates
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Binary Search
public static int binarySearch(int anArray[], int first,
int last, int value) {
// Searches the array items anArray[first] through
// anArray[last] for value by using a binary search.
// Precondition: 0 <= first, last <= SIZE-1, where
// SIZE is the maximum size of the array, and
// anArray[first] <= anArray[first+1] <= ... <=
// anArray[last].
// Postcondition: If value is in the array, the method
// returns the index of the array item that equals value;
// otherwise the method returns -1.
int index;
if (first > last) {
index = -1;
// value not in original array
}
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
else {
// Invariant: If value is in anArray,
//
anArray[first] <= value <= anArray[last]
int mid = (first + last)/2;
if (value == anArray[mid]) {
index = mid; // value found at anArray[mid]
}
else if (value < anArray[mid]) {
// point X
index = binarySearch(anArray,first,mid-1, value);
}
else {
// point Y
index = binarySearch(anArray,mid+1,last,value);
} // end if
} // end if
return index;
} // end binarySearch
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.15
Box traces of binarySearch with anArray = <1,5,9,12,15,21,29,31>:
a) a successful search for 9; b) an unsuccessful search for 6
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.16
Box trace with reference to an array
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.17
A sample array
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Find the kth Smallest Item in an
Arbitrary Array
• Selecting a pivot item in the array
• Arranging, or partitioning, the items in
the array about this pivot item
• Recursively applying the strategy to one
of the partitions
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.18
A partition about a pivot
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
The Towers of Hanoi
• Three poles: A (the source), B (the
destination), and C (the spare) with n
disks
• The disks are of different sizes
• Move the disks from pole A to pole B,
using pole C.
• A disk could be placed only on top of a
disk larger than itself.
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.19a and b
a) The initial state; b) move n - 1 disks from A to C
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.19c and d
c) move one disk from A to B; d) move n - 1 disks from C to B
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
The Towers of Hanoi
public static void solveTowers(int count, char source,
char destination, char spare) {
if (count == 1) {
System.out.println("Move top disk from pole " + source +
" to pole " + destination);
}
else {
solveTowers(count-1, source, spare, destination); // X
solveTowers(1, source, destination, spare);
// Y
solveTowers(count-1, spare, destination, source); // Z
} // end if
} // end solveTowers
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.20
The order of recursive calls that results from solveTowers(3, A, B, C)
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.21a
Box trace of solveTowers(3, ‘A’, ‘B’, ‘C’)
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.21b
Box trace of solveTowers(3, ‘A’, ‘B’, ‘C’)
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.21c
Box trace of solveTowers(3, ‘A’, ‘B’, ‘C’)
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.21d
Box trace of solveTowers(3, ‘A’, ‘B’, ‘C’)
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 2.21e
Box trace of solveTowers(3, ‘A’, ‘B’, ‘C’)
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Recursion and Efficiency
• The overhead associated with method
calls
• The inherent inefficiency of some
recursive algorithms
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Iterative Solution for Counting
Rabbits
static int iterativeRabbit(int n) {
// Iterative solution to the rabbit problem.
// initialize base cases:
int previous = 1; // initially rabbit(1)
int current = 1; // initially rabbit(2)
int next = 1;
// result when n is 1 or 2
// compute next rabbit values when n >= 3
for (int i = 3; i <= n; i++) {
// current is rabbit(i-1), previous is rabbit(i-2)
next = current + previous; // rabbit(i)
previous = current;
// get ready for
current = next;
// next iteration
} // end for
return next;
} // end iterativeRabbit
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Iterative Solution for Writing String
Backward
public static void writeBackward(String s, int size) {
if (size > 0) {
// write the last character
System.out.println(s.substring(size-1, size));
writeBackward(s, size - 1);
// write rest
} // end if
} // end writeBackward
public static void writeBackward(String s, int size) {
// Iterative version.
while (size > 0) {
System.out.println(s.substring(size-1, size));
--size;
} // end while
} // end writeBackward