ptg
A l g o r i t h m s When we write a computer program, we are generally implementing a
method that has been devised previously to solve some problem. This method is often
independent of the particular programming language being used—it is likely to be
equally appropriate for many computers and many programming languages. It is the
method, rather than the computer program itself, that specifies the steps that we can
take to solve the problem. The term algorithm is used in computer science to describe
a finite, deterministic, and effective problem-solving method suitable for implementa-
tion as a computer program. Algorithms are the stuff of computer science: they are
central objects of study in the field.
We ca n de fine an al gor ithm by d esc rib ing a pro cedure fo r so lvi ng a prob lem in a
natural language, or by writing a computer program that implements the procedure,
as shown at right for Euclid’s algorithm for finding the greatest common divisor of
two numbers, a variant of which was devised
over 2,300 years ago. If you are not familiar
with Euclid’s algorithm, you are encour-
aged to work Exercise 1.1.24 and Exercise
1.1.25, perhaps after reading Section 1.1. In
this book, we use computer programs to de-
scribe algorithms. One important reason for
doing so is that it makes easier the task of
checking whether they are finite, determin-
istic, and effective, as required. But it is also
important to recognize that a program in a
particular language is just one way to express
an algorithm. The fact that many of the al-
gorithms in this book have been expressed
in multiple programming languages over the
past several decades reinforces the idea that each algorithm is a method suitable for
implementation on any computer in any programming language.
Most algorithms of interest involve organizing the data involved in the computa-
tion. Such organization leads to data structures, which also are central objects of study
in computer science. Algorithms and data structures go hand in hand. In this book we
take the view that data structures exist as the byproducts or end products of algorithms
and that we must therefore study them in order to understand the algorithms. Simple
algorithms can give rise to complicated data structures and, conversely, complicated
algorithms can use simple data structures. We shall study the properties of many data
structures in this book; indeed, we might well have titled the book Algorithms and Data
Structures.
Compute the greatest common divisor of
two nonnegative integers p and q as follows:
If q is 0, the answer is p. If not, divide p by q
and take the remainder r. The answer is the
greatest common divisor of q and r.
public static int gcd(int p, int q)
{
if (q == 0) return p;
int r = p % q;
return gcd(q, r);
}
Euclid’s algorithm
Java-language description
English-language description
4 CHAPTER 1
■
Fundamentals
5星 · 超过95%的资源 需积分: 50 122 浏览量
更新于2024-07-27
1
收藏 12.33MB PDF 举报 
