|
A scan algorithm goes through a sequence of values, keeping track of some information as it goes. It stops when it reaches the end of the sequence; the information that it has been keeping tells it the answer to the problem.
Here are some examples of problems that are natural candidates for scan algorithms.
Add up a sequence of numbers x1,…, xn. As you scan through the sequence, keep track of the sum of the numbers that you have seen so far.
Compute the factorial n! of n. Since n! = 1*2*…*n, just scan through sequence 1, 2, …, n, keeping track of the product of the numbers seen so far.
Find the largest of x1,…, xn. As you scan, keep track of the largest number that you have seen so far.
Convert a string of digits to an integer. As you scan, remember the number that the digits seen so far stand for. Each time you encounter a new digit d, replace your current number x by 10*x + d. For example, converting string "2545" to an integer works as follows.
| Scanned so far | x | |
|---|---|---|
| "" | 0 | |
| "2" | 2 | |
| "25" | 25 | |
| "254" | 254 | |
| "2545" | 2545 |
A loop is an obvious way to implement a scan algorithm, and it is usually the recommended approach. Just be sure to initialize your variables, to scan through the sequence correctly, and to update the information that you are keeping correctly. Here are implementations of problems similar to each of the above problems.
//===============================================
// sum(A,n) returns A[0] + A[1] + … + A[n-1].
//===============================================
static int sum(int[] A, int n)
{
int total = 0;
for(int i = 0; i < n; i++)
{
total = total + A[i];
}
return total;
}
//===============================================
// factorial(n) returns n!.
//===============================================
static long factorial(long n)
{
long f = 1;
for(long i = 1; i <= n; i++)
{
f = f * i;
}
return f;
}
//===============================================
// largest(A,n) returns the largest of
// A[0], A[1], …, A[n-1].
//===============================================
static int largest(int[] A, int n)
{
int big = A[0];
for(int i = 1; i < n; i++)
{
big = Math.max(big, A[i]);
}
return big;
}
//===============================================
// convertToInt(s) yields the integer described
// by s. For example, convertToInt("325")
// = 325.
//
// Requirement: String s must only contain decimal digits.
//===============================================
static int convertToInt(String s)
{
int n = 0;
int len = s.length();
for(int i = 0; i < len; i++)
{
n = 10*n + Character.getNumericValue(s.charAt(i));
}
return n;
}
Recursion can scan a sequence either forward or backwards. The backward approach is often simpler. Here are recursive definitions of some of the methods above that scan the sequence backwards.
//==============================================
// sum(A,n) returns A[0] + A[1] + … + A[n-1].
//==============================================
static int sum(int[] A, int n)
{
if(n == 0)
{
return 0;
}
else
{
return sum(A, n-1) + A[n-1];
}
}
//==============================================
// factorial(n) returns n!.
//==============================================
static long factorial(long n)
{
if(n == 0)
{
return 1;
}
else
{
return factorial(n-1) * n;
}
}
//==============================================
// largest(A,n) returns the largest of
// A[0], A[1], …, A[n-1].
//==============================================
static int largest(int A[], int n)
{
if(n == 1)
{
return A[0];
}
else
{
return Math.max(largest(A, n-1), A[n-1]);
}
}
The convertToInt algorithm really wants to scan the string forward. To do a forward scan using recursion, you typically add an extra parameter that is the information being accumulated, and sometimes also add an extra parameter that helps keep track of where you are in the scan. But the extra parameters change the problem that the method solves. So you define the method that you really want in terms of the one with the extra parameters. Here are recursive definitions of each of the methods above using that approach.
//==============================================
// sumhelp(A,n,i,r) returns r + A[i] + A[i+1] + … + A[n-1].
// If i > n then it returns r.
//==============================================
static int sumhelp(int[] A, int n, int i, int r)
{
if(i > n)
{
return r;
}
else
{
return sumhelp(A, n-1, i+1, r + A[i]);
}
}
//==============================================
// sum(A,n) returns A[0] + A[1] + … + A[n-1].
//==============================================
static int sum(int[] A, int n)
{
return sumhelp(A, n, 0, 0);
}
//==============================================
// factorialhelp(i,n,r) returns r*i*(i+1)*…*n.
// For example, factorialhelp(5, 8, 24) yields
// 24*5*6*7*8.
//==============================================
long factorialhelp(long i, long n, long r)
{
if(i > n)
{
return r;
}
else
{
return factorialhelp(i+1, n, r*i);
}
}
//==============================================
// factorial(n) returns n!.
//==============================================
static long factorial(long n)
{
return factorialhelp(1, n, 1);
}
//==============================================
// largesthelp(A,n,i,r) returns the largest of
// r, A[i], A[i+1], …, A[n-1]. If i >= n
// then largesthelp(A,n,i,r) returns r.
//==============================================
static int largesthelp(int[] A, int n, int i, int r)
{
if(i >= n)
{
return r;
}
else
{
return largesthelp(A, n, i+1, Math.max(r,A[i]));
}
}
//==============================================
// largest(A,n) returns the largest of
// A[0], A[1], …, A[n-1].
//==============================================
static int largest(int[] A, int n)
{
return largesthelp(A, n, 1, A[0]);
}
//==============================================
// convertToIntHelp(s,i,r) yields the integer
// that you get by writing the digits of r
// followed by the digits in string the suffix
// of s that you get by removing the first
// i characters.
//
// For example, convertToIntHelp("325", 1, 64)
// = 6425. (Write 64 followed by 25).
//
// Requirement: s must only contain decimal digits.
//==============================================
static int convertToIntHelp(String s, int i, int r)
{
if(i == s.length())
{
return r;
}
else
{
return convertToIntHelp(s, i+1, 10*r + Character.getNumericValue(s.charAt(i)));
}
}
//==============================================
// convertToInt(s) yields the integer described
// by s. For example, convertToInt("325")
// = 325.
//
// Requirement: String s must only contain decimal digits.
//==============================================
static int convertToInt(String s)
{
return convertToIntHelp(s, 0, 0);
}
Sometimes you want accumulate information about only selected values in a sequence of values. To do that, just scan through the sequence, skipping over values that are not of interest. The following illustrates. We assume that a method isPrime(n) is available, which returns true just when n is prime.
//==============================================
// sumprime(n) yields the sum of the prime
// numbers that are less than or equal to n.
// For example, sumprime(5) = 2 + 3 + 5 = 10.
//==============================================
static int sumprimes(int n)
{
int total = 0;
for(int i = 2; i <= n; i++)
{
if(isPrime(i))
{
total += i;
}
}
return total;
}
Write a static method productOdds(n) that yields the product of the odd positive integers that are less than or equal to n. Assume that n and the result have type int. For this exercise, use a loop. Answer
Solve the previous problem, but use recursion instead of a loop. Answer
Write a static method binaryToInt(s) that takes a string of 0's and 1's that stands for a binary number, and returns the integer that the string stands for. For example, binaryToInt("110") returns 6 since 110 is the binary representation of 6. An empty string represents 0. Answer
|