|
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 null-terminated 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].
//===============================================
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!.
//===============================================
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].
//===============================================
#include <algorithm>
using namespace std;
int largest(int A[], int n)
{
int big = A[0];
for(int i = 1; i < n; i++)
{
big = max(big, A[i]);
}
return big;
}
//===============================================
// convertToInt(s) yields the integer described
// by s. For example, convertToInt("325")
// = 325.
//
// Requirement: s must be a null-terminated string
// that only contains decimal digits.
//===============================================
int convertToInt(char* s)
{
int n = 0;
for(int i = 0; s[i] != '\0'; i++)
{
n = 10*n + (s[i] - '0');
}
return n;
}
Remark. There is a library function called atoi that does the same thing as convertToInt. Include cstdlib to use atoi.
Recursion can scan a sequence either forward or backwards. The backward approach is often simpler. Here are recursive definitions of some of the functions above that scan the sequence backwards.
//==============================================
// sum(A,n) returns A[0] + A[1] + ... + A[n-1].
//==============================================
int sum(int A[], int n)
{
if(n == 0)
{
return 0;
}
else
{
return sum(A, n-1) + A[n-1];
}
}
//==============================================
// factorial(n) returns n!.
//==============================================
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].
//==============================================
int largest(int A[], int n)
{
if(n == 1)
{
return A[0];
}
else
{
return 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 function solves. So you define the function that you really want in terms of the one with the extra parameters. Here are recursive definitions of each of the functions 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.
//==============================================
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].
//==============================================
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!.
//==============================================
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.
//==============================================
int largesthelp(int A[], int n, int i, int r)
{
if(i >= n)
{
return r;
}
else
{
return largesthelp(A, n, i+1, max(r,A[i]));
}
}
//==============================================
// largest(A,n) returns the largest of
// A[0], A[1], ..., A[n-1].
//==============================================
int largest(int A[], int n)
{
return largesthelp(A, n, 1, A[0]);
}
//==============================================
// convertToIntHelp(s,r) yields the integer
// that you get by writing the digits of r
// followed by the digits in string s.
//
// For example, convertToIntHelp("325", 64)
// = 64325.
//
// Requirement: s must be a null-terminated string
// that only contains decimal digits.
//==============================================
int convertToIntHelp(char* s, int r)
{
if(*s == '\0')
{
return r;
}
else
{
return convertToIntHelp(s+1, 10*r + (*s - '0'));
}
}
//==============================================
// convertToInt(s) yields the integer described
// by s. For example, convertToInt("325")
// = 325.
//
// Requirement: s must be a null-terminated string
// that only contains decimal digits.
//==============================================
int convertToInt(char* s)
{
return convertToIntHelp(s, 0);
}
Looking at the definitions of the help functions, you can see that each one is tail-recursive. That means that an optimizing compiler can replace the recursion by a loop for you.
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 function 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.
//==============================================
int sumprimes(int n)
{
int total = 0;
for(int i = 2; i <= n; i++)
{
if(isPrime(i))
{
total += i;
}
}
return total;
}
Write a function 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
Solve the preceding problem, but use a forward scan and tail recursion. Answer
Write a function binaryToInt that takes a null-terminated 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
|