Programming and Problem Solving with C++, Comprehensive, Sixth Edition

1. Analysis and specification. Understand (define) the problem and what the solution must do.

2. General solution (algorithm). Develop a logical sequence of steps that solves the problem.

3. Verify. Follow the steps exactly to see if the solution really does solve the problem.

If our definitions of a computer program and an algorithm look similar, it is because all programs are algorithms. A program is simply an algorithm that has been written for a computer.

An algorithm is a verbal or written description of a logical sequence of actions. We use algorithms every day. Recipes, instructions, and directions are all examples of algorithms that are not programs.

When you start your car, you follow a step-by-step procedure. The algorithm might look something like this:

5. If the engine starts within six seconds, release the key to the ignition position.

6. If the engine doesn’t start in six seconds, release the key and gas pedal, wait ten seconds, and repeat Steps 3 through 6, but not more than five times.

Some people try to speed up the programming process by going directly from the problem definition to coding the program (see FIGURE 1.3). A shortcut here is very tempting and at first seems to save a lot of time. However, for many reasons that will become obvious to you as you read this book, this kind of shortcut actually takes more time and effort. Developing a general solution before you write a program helps you manage the problem, keep your thoughts straight, and avoid mistakes. If you don’t take the time at the beginning to think out and polish your algorithm, you’ll spend a lot of extra time debugging and revising your program. So think first and code later! The sooner you start coding, the longer it takes to write a program that works.

Once a program has been put into use, it may become necessary to modify it. Modification may involve fixing an error that is discovered during the use of the program or changing the program in response to changes in the user’s requirements. Each time the program is modified, the problem-solving and implementation phases must be repeated for those aspects of the program that change. This phase of the programming process, which is known as maintenance, actually accounts for the majority of the effort expended on most programs. For example, a program that is implemented in a few months may need to be maintained over a period of many years. Thus it is a cost-effective investment of time to develop the initial problem solution and program implementation carefully. Together, the problem-solving, implementation, and maintenance phases constitute the program’s life cycle.

THEORETICAL FOUNDATIONS

Binary Representation of Data

In a computer, data are represented electronically by pulses of electricity. Electric circuits, in their simplest form, are either on or off. A circuit that is on represents the number 1; a circuit that is off represents the number 0. Any kind of data can be represented by combinations of enough 1s and 0s. We simply have to choose which combination represents each piece of data we are using. For example, we could arbitrarily choose the pattern 1101000110 to represent the name “C++.”

Data represented by 1s and 0s are in binary form. The binary, or base-2, number system uses only 1s and 0s to represent numbers. (The decimal, or base-10, number system uses the digits 0 through 9.) The word bit (short for binary digit) refers to a single 1 or 0. Thus the pattern 1101000110 has ten bits. A binary number with three bits can represent 2³, or eight, different patterns. The eight patterns are shown here, together with some examples of base-2 arithmetic:

A ten-digit binary number can represent 2¹⁰ (1024) distinct patterns. Thus you can use your fingers to count in binary from 0 to 1023! A byte is a group of eight bits; it can represent 2⁸ (256) patterns. Inside the computer, each character (such as the letter A, the letter g, the digit 7, a question mark, or a blank) is usually represented by either one or two bytes.2 For example, in one scheme 01001101 represents M and 01101101 represents m (look closely—the third bit from the left is the only difference). Groups of 16, 32, and 64 bits are generally referred to as words (the terms “short word” and “long word” sometimes are used to refer to 16-bit and 64-bit groups, respectively).

The process of assigning bit patterns to pieces of data is called coding—the same name we give to the process of translating an algorithm into a programming language. The names are the same because the first computers recognized only one language, which was binary in form. Thus, in the early days of computers, programming meant translating both data and algorithms into patterns of 1s and 0s. The resulting programs looked like messages in a secret code that were being passed from the programmer to the computer. It was very difficult for one programmer to understand a program written by another programmer. In fact, after leaving a program alone for a while, many programmers could not even understand their own programs!

The patterns of bits that represent data vary from one family of computers to another. Even on the same computer, different programming languages may use different binary representations for the same data. A single programming language may even use the same pattern of bits to represent different things in different contexts. (People do this, too: The four letters that form the word tack have different meanings depending on whether you are talking about upholstery, sailing, sewing, paint, or horseback riding.) The point is that patterns of bits by themselves are meaningless. Rather, it is the way in which the patterns are used that gives them their meaning. That’s why we combine data with operations to form meaningful objects.

Fortunately, we no longer have to work with binary coding schemes. Today, the process of coding is usually just a matter of writing down the data in letters, numbers, and symbols. The computer automatically converts these letters, numbers, and symbols into binary form. Still, as you work with computers, you will continually run into numbers that are related to powers of 2—numbers such as 256, 32,768, and 65,536. They are reminders that the binary number system is lurking somewhere in the background.

One benefit of using standardized high-level languages is that they allow you to write portable (or machine-independent) code. As Figure 1.5 emphasizes, a single C++ program can be used on different machines, whereas a program written in assembly language or machine language is not portable from one computer to another. Because each computer has its own machine language, a machine language program written for computer A will not run on computer B.

It is important to understand that compilation and execution are two distinct processes. During compilation, the computer runs the compiler program. During execution, the object program is loaded into the computer’s memory unit, replacing the compiler program. The computer then runs the object program, doing whatever the program instructs it to do (see FIGURE 1.6).

FIGURE 1.5 High-Level Programming Languages Allow Programs to Be Compiled on Different Systems

Imagine you’re driving a car. Going down a straight stretch of road is like following a sequence of instructions. When you come to a fork in the road, you must decide which way to go and then take one or the other branch of the fork. This is what the computer does when it encounters a selection control structure (also called a branch) in a program. Sometimes you have to go around the block several times to find a place to park. The computer does the same sort of thing when it encounters a loop in a program.

A subprogram is a process that consists of multiple steps. Every day, for example, you follow a procedure to get from home to work. It makes sense, then, for someone to give you directions to a meeting by saying, “Go to the office, then go four blocks west” without specifying all the steps you have to take to get to the office. Subprograms allow us to write parts of our programs separately and then assemble them into final form. They can greatly simplify the task of writing large programs.

In the life cycle of a program, the maintenance phase accounts for the majority of a typical program’s existence. As we said earlier, programs are initially written in a fairly short time span, and then are used for many years after. The original designers develop the program to meet a set of specifications, and they cannot possibly foresee all the ways that the program will be used in the future. Decisions that were made in the initial implementation may prove to be inadequate to support some future use, and a new team of programmers may then be called in to modify the program. After going through many modifications, the code may become so complicated that it is difficult to identify the purpose of some of the original instructions.

For example, at the turn of the millennium, the software industry faced a major maintenance effort known collectively as the “Y2K Problem.” For much of the preceding 50 years, programmers had been encoding dates with a two-digit integer representing the year, as shown here:

SOFTWARE MAINTENANCE CASE STUDY: An Introduction to Software Maintenance

The preceding discussion is intended to illustrate the importance of developing skills not just in writing new code, but also in working with existing code. These Software Maintenance Case Study sections walk you through the process of typical maintenance tasks. Unlike the Problem-Solving Case Study sections, where we begin with a problem, solve it, and then code a program, here we begin with a program and see how to understand what it does before making some change.

Let’s start with something extremely simple, just to get a sense of what we’ll be doing in future Software Maintenance Case Study sections. We keep this example so simple that you don’t even have to know anything about C++ to follow what’s happening. But in following our steps through this process, you’ll get a sense of what’s involved in working with programs.

MAINTENANCE TASK: Enter the “Hello World” application program, changing it to output “Hello Universe” instead.

EXISTING CODE

DISCUSSION: The classic first application that is written by many beginners is generically known as “Hello World.” Its sole purpose is to print out a greeting from the computer to the programmer, and then quit. There are many variations of the message, but the traditional one is “Hello World!” Here, we are being asked to change the existing message to “Hello Universe!”

Looking at this code, you can immediately see the message, enclosed in quotes. Your first temptation would be to just change the word “World” to “Universe”. (Even without knowing any C++, you’re already programming!) In a simple case like this, that strategy may be adequate; with a larger application, however, such an approach could result in the creation of more problems. With any maintenance effort, we must first observe and record the current behavior of the application. If it isn’t working initially, you may think that your changes are the source of a preexisting problem and spend many hours in a futile attempt to fix the problem by correcting your changes.

Thus the first step in this maintenance task is to enter the application exactly as it is written and run it to ensure that it works. Unless you’ve written programs before, it is hard to appreciate how precisely you must type C++ code. Every letter, every capitalization, every punctuation mark is significant. There are exceptions, which we’ll see later, but for now, it is good practice to enter this application exactly as it appears here. For example, can you spot the error in the following version of the code that fails to run? All you have to do is compare it, letter by letter, with the preceding version, to find the difference.3

Once we are sure that the program works as claimed, we can change it with the knowledge that any new problems are associated with our modifications.

Entering an application involves typing it into the computer with an editor, which is just a program that lets us record our typing in a file. A word processor is an example of an editor. Most programming systems use a specialized code editor that has features to help us enter programs. For example, a code editor will indent the lines of an application automatically in a pattern similar to what is shown in the preceding example, and it may color-code certain elements of the program to help us locate them more easily.

Depending on the programming system that you are using, you may need to begin by creating a new “project,” which is the system’s way of organizing the information it keeps about your application. Typically, creating a new project involves selecting the “New Project” item from the File menu of the programming system, and then entering a name for the project in a dialog box that appears.

In another programming system, you may need to create a new file directory manually and tell the editor to store your code file there. There are too many different C++ programming systems for us to show them all here. You should consult the manual or help screens for your particular system to learn the specifics.

Once you type the application into the editor window, you need to save it (with another menu selection) and then run it. Here’s what happens when we try to run the erroneous version of Hello World. A red mark appears in the margin next to the line with the offending name, and the error message, “error: ‘Cout’ was not declared within this scope” appears on another screen.

Every programmer gets these kinds of error messages at some time. Very few of us are perfect typists! Rather than being afraid of seeing such messages, we just come to expect them, and are pleasantly surprised on the rare occasions when we discover that we’ve entered a long stretch of code without typos. Usually, we enter some code, look it over carefully for mistakes, and run it to see if the computer finds any more. We then use the error messages to help us find remaining typos and fix them. Here’s what happens when the application is at last correct:

Now we know that the program works as advertised, and we can start changing it. Of the seven lines in this application, the first three and the sixth are general instructions that appear in almost all programs. The braces are a form of punctuation in a C++ application. It is the fifth line that is specific to this problem.

Now, let’s try making our change, substituting “Universe” for “World”—in two places. We must also change the documentation. Here’s the revised application, with “Universe” substituted for “World”.

Is that it? Could it really be as simple as changing one word? Well, actually no. We edited our existing Hello World code file, and when we saved it, we overwrote the existing application, so we no longer have the original code. It’s always a good idea to keep the working version of a program separate from a new version. That way, we have a working baseline to compare against the new version. And if things really go wrong with our modifications, we have a place to go back to, and start over.

To correct this situation, we really should have created a new project, perhaps called HelloUniverse, and copied the code from our existing project into the new one. Then we can edit the fifth line, and save the change without affecting the original.

Software Maintenance Tips

1. Check that the existing code works as claimed.

2. Make changes to a copy of the existing code.

3. A maintenance task isn’t necessarily complete once the desired functionality has been achieved. Change related aspects of the program to leave clean, consistent code for the next programmer who has to do maintenance.

4. Keeping backup copies of code is also useful in developing new programs. Before making any significant change in a program that you’re developing, save a copy of the current version so that you can go back to it if necessary.

The memory unit is an ordered sequence of storage cells, each capable of holding a piece of data. Each memory cell has a distinct address to which we refer so as to store data into it or retrieve data from it. These storage cells are called memory cells, or memory locations.⁴ The memory unit holds data (input data or the product of computation) and instructions (programs), as shown in FIGURE 1.9.

The part of the computer that follows instructions is called the central processing unit (CPU). The CPU usually has two components. The arithmetic/logic unit (ALU) performs arithmetic operations (addition, subtraction, multiplication, and division) and logical operations (comparing two values). The control unit controls the actions of the other components so that program instructions are executed in the correct order.

For us to use computers, there must be some way of getting data into and out of them. Input/output (I/O) devices accept data to be processed (input) and present data values that have been processed (output). A keyboard is a common input device. Another is a mouse, a pointing device. Trackpads and touch screens are also used as pointing devices. A liquid crystal display (LCD) screen is a common output device, as are printers. Some devices, such as a connection to a computer network, are used for both input and output.

The set of programs that simplify the user/computer interface and improve the efficiency of processing is collectively called system software. It includes the compiler as well as the operating system and the editor (see FIGURE 1.10). The operating system manages all of the computer’s resources. It can input programs, call the compiler, execute object programs, and carry out any other system commands. The editor is an interactive program used to create and modify source programs or data.

BACKGROUND INFORMATION

What Makes One Computer Faster Than Another?

The faster a computer is, the more quickly it responds to our commands and the more work it can do in less time. But which factors affect the speed of a computer? The answer is quite complex, but let’s consider some of the essential issues.

In computer advertising you often see numbers such as 3.2 GHz, and the ads clearly want you to believe that this is an important contributor to speed. But what does it really mean? The abbreviation GHz is short for gigahertz, which means billions of cycles per second. What’s cycling at this speed is the pulse of the computer—an electrical signal called the clock, which generates a continuous sequence of precisely regulated on/off pulses that are used to coordinate all of the actions of the other circuitry within the computer. It’s called a clock because it bears a similarity to the steady ticking of a mechanical clock. But if you want a better sense of what it does, think of it like the rhythmic swinging of an orchestra conductor’s baton, which keeps all of the instruments playing in time with each other. The clock ensures that all the components of the computer are doing their jobs in unison. It’s clear that the faster the clock, the faster the components work. But that’s just one factor that affects speed.

Clock An electrical circuit that sends out a train of pulses to coordinate the actions of the computer’s hardware components, The speed of the clock is measured in Hertz (cycles per second).

Although we have described the fetch–execute cycle as if the computer always fetches just one instruction at a time and executes that instruction to completion before fetching the next one, modern computers are not so simple. They often fetch and execute multiple instructions at once (for example, most can simultaneously do integer and real arithmetic, while retrieving values from memory). In addition, they start fetching the next instruction from memory while executing prior instructions. The number of instructions that the computer can execute simultaneously also has a significant effect on speed.

Different computers also work with data in chunks of different sizes. The computer in a microwave oven may work with 8 bits at a time, whereas a smartphone computer typically handles 32 bits at once. Higher-performance machines work with data in units of 64 bits. The more data the computer can process at once, the faster it will be, assuming that the application has need of working with larger quantities of data. The computer in the microwave is plenty fast enough to do its job—your popcorn would not pop any faster if it had a 64-bit processor!

It is not uncommon to see, for example, a 1.8 GHz, 64-bit computer that can process many instructions at once, which is significantly faster than a 3.6 GHz, 32-bit computer that handles fewer instructions in parallel. The only way to accurately judge the speed of a computer is to run an application on it, and measure the time it takes to execute.

Other major hardware factors that affect speed are the amount of memory (RAM) and speed of the hard disk. When a computer has more memory, it can hold more programs and data in its memory. With less memory, it must keep more of the programs and data on the hard disk drive, shuffling them between disk and memory as it needs them. The hard disk takes as much as a million times longer to access than RAM, so you can see that a computer with too little RAM can be slowed down tremendously. Disks themselves vary significantly in the speed with which they access data.

Software also affects speed. As we will see in later chapters, problems can be solved more or less efficiently. A program that is based on an inefficient solution can be vastly slower than one that is more efficient. Different compilers do a better job of translating high-level instructions into efficient machine code, which also affects speed. Operating systems also vary in their efficiency. The raw speed of the hardware is masked by the overall efficiency of the software. As a programmer, then, you can have a strong influence on how fast the computer seems to be.

QUICK CHECK

1.4.1 How can you help to keep confidential data private? (p. 25)

You solve problems every day, often unaware of the process you are going through. In a learning environment, you usually are given most of the information you need: a clear statement of the problem, the necessary input, and the required output. In real life, the process is not always so simple. You often have to define the problem yourself and then decide what information you have to work with and what the results should be.

After you understand and analyze a problem, you must come up with a solution—an algorithm. Earlier we defined an algorithm as a step-by-step procedure for solving a problem in a finite amount of time. Although you work with algorithms all the time, most of your experience with them is in the context of following them. You follow a recipe, play a game, assemble a toy, take medicine. In the problem-solving phase of computer programming, you will be designing algorithms, not following them. This means you must be conscious of the strategies you use to solve problems so as to apply them effectively to programming problems.

If you are given a task orally, you ask questions—When? Why? Where?—until you understand exactly what you have to do. If your instructions are written, you might put question marks in the margin, underline a word or a sentence, or in some other way indicate that the task is not clear. Your questions may be answered by a later paragraph, or you might have to discuss them with the person who gave you the task.

Often a problem may remind you of a similar problem you have seen before. You may find solving the problem at hand easier if you remember how you solved the other problem. In other words, draw an analogy between the two problems. For example, a solution to a perspective-projection problem from an art class might help you figure out how to compute the distance to a landmark when you are on a cross-country hike. As you work your way through the new problem, you may come across things that are different than they were in the old problem, but usually these are just details that you can deal with one at a time.

Analogy is really just a broader application of the strategy of looking for things that are familiar. When you are trying to find an algorithm for solving a problem, don’t limit yourself to computer-oriented solutions. Step back and try to get a larger view of the problem. Don’t worry if your analogy doesn’t match perfectly—the only reason for using an analogy is that it gives you a place to start (see FIGURE 1.12). The best programmers are people who have broad experience solving all kinds of problems.

Often the beginning state and the ending state are given; the problem is to define a set of actions that can be used to get from one to the other. Suppose you want to go from Boston, Massachusetts to Austin, Texas. You know the beginning state (you are in Boston) and the ending state (you want to be in Austin). The problem is how to get from one to the other. In this example, you have lots of choices. You can fly, walk, hitchhike, ride a bike, or whatever. The method you choose depends on your circumstances. If you’re in a hurry, you’ll probably decide to fly.

The overall strategy of means-ends analysis is to define the ends and then to analyze your means of getting between them. This process translates easily to computer programming. You begin by writing down what the input is and what the output should be. Then you consider the actions a computer can perform and choose a sequence of actions that can transform the data into the results.

We often break up large problems into smaller units that are easier to handle. Cleaning the whole house may seem overwhelming; cleaning the rooms one at a time seems much more manageable. The same principle applies to programming: We can break up a large problem into smaller pieces that we can solve individually (see FIGURE 1.14). In fact, the functional decomposition and object-oriented methodologies, which we describe in Chapter 4, are based on the principle of divide and conquer.

Another way of attacking a large problem is to see if any solutions for smaller pieces of the problem exist. It may be possible to put some of these solutions together end to end to solve most of the big problem. This strategy is just a combination of the look-for-familiar-things and divide-and-conquer approaches. You look at the big problem and see that it can be divided into smaller problems for which solutions already exist. Solving the big problem is just a matter of putting the existing solutions together, like mortaring together blocks to form a wall (see FIGURE 1.15).

Writers are all too familiar with the experience of staring at a blank page, not knowing where to begin. Programmers have the same difficulty when they first tackle a big problem. They look at the problem and it seems overwhelming.

BACKGROUND INFORMATION

The Origins of C++

In the late 1960s and early 1970s, Dennis Ritchie created the C programming language at AT&T Bell Labs. At the time, a group of people within Bell Labs were designing the UNIX operating system. Initially, UNIX was written in assembly language, as was the custom for almost all system software in those days. To escape the difficulties of programming in assembly language, Ritchie invented C as a system programming language. C combines the low-level features of an assembly language with the ease of use and portability of a high-level language. UNIX was reprogrammed so that approximately 90% was written in C and the remainder in assembly language.

People often wonder where the cryptic name “C” came from. In the 1960s, a programming language named BCPL (Basic Combined Programming Language) had a small but loyal following, primarily in Europe. From BCPL, another language arose with its name abbreviated to B. For his language, Dennis Ritchie adopted features from the B language and decided that the successor to B naturally should be named C. So the progression was from BCPL to B to C.

In 1985, Bjarne Stroustrup, also of Bell Labs, invented the C++ programming language. To the C language he added features for data abstraction and object-oriented programming (topics we discuss later in this book). Instead of naming the language D, the Bell Labs group, following a humorous vein, named it C++. As we see later, ++ signifies the increment operation in the C and C++ languages. Given a variable x, the expression x++ means to increment (add one to) the current value of x. Therefore, the name C++ suggests an enhanced (“incremented”) version of the C language.

In the years since Dr. Stroustrup invented C++, the language began to evolve in slightly different ways in different C++ compilers. Although the fundamental features of C++ were nearly the same in all companies’ compilers, one company might add a new language feature, whereas another would not. As a result, C++ programs were not always portable from one compiler to the next. The programming community agreed that the language needed to be standardized, so a joint committee of the International Standards Organization (ISO) and the American National Standards Institute (ANSI) began the long process of creating a C++ language standard. After several years of discussion and debate, the ISO/ANSI language standard for C++ was officially approved in mid-1998. Most of the current C++ compilers support the ISO/ANSI standard (hereafter called standard C++).

Although C originally was intended as a system programming language, both C and C++ are widely used today in business, industry, and personal computing. C++ is powerful and versatile, embodying a wide range of programming concepts. In this book you will learn a substantial portion of the language, but C++ incorporates sophisticated features that go well beyond the scope of an introductory programming course.

Problem-Solving Case Study

Leap Year Algorithm

PROBLEM: You need to write a set of instructions that can be used to determine whether a year is a leap year. The instructions must be very clear because they will be used by a class of fourth graders who have just learned about multiplication and division. They plan to use the instructions as part of an assignment to determine whether any of their relatives were born in a leap year. To check that the algorithm works correctly, you will code it as a C++ program and test it.

DISCUSSION: The rule for determining whether a year is a leap year is that a year must be evenly divisible by 4, but not a multiple of 100. When the year is a multiple of 400, it is a leap year anyway. We need to write this set of rules as a series of steps (an algorithm) that can be followed easily by the fourth graders.

First, we break this into major steps using the divide-and-conquer approach. There are three obvious steps in almost any problem of this type:

1. Get the data.

2. Compute the results.

3. Output the results.

What does it mean to “get the data”? By get, we mean read or input the data. We need one piece of data: a four-digit year. So that the user will know when to enter the value, we must have the computer output a message that indicates when it is ready to accept the value (this is called a prompting message, or a prompt). Therefore, to have the computer get the data, we have it do these two steps:

Get Data

Prompt the user to enter a four-digit year

Read the year

Next, we check whether the year that was read can be a leap year (is divisible by 4), and then we test whether it is one of the exceptional cases. Our high-level algorithm is as follows:

Is Leap Year

IF the year is not divisible by 4
then the year is not a leap year

ELSE check for exceptions

Clearly, we need to expand these steps with more detailed instructions, because neither the fourth graders nor the computer knows what “divisible” means. We use means-ends analysis to solve the problem of how to determine when something is divisible by 4. Our fourth graders know how to do simple division that results in a quotient and a remainder. We can tell them to divide the year by 4, and if the remainder is zero, then it is divisible by 4. Thus the first line is expanded into the following:

Is Leap Year revised

Divide the year by 4

IF the remainder is not 0
then the year is not a leap year

ELSE check for exceptions

Checking for exceptions when the year is divisible by 4 can be further divided into two parts: checking whether the year is also divisible by 100 and whether it is further divisible by 400. Given how we did the first step, this is easy:

Checking for exceptions

Divide the year by 100

IF the remainder is 0
then the year is not a leap year

Divide the year by 400

IF the remainder is 0
then the year is a leap year

These steps are confusing by themselves. When the year is divisible by 400, it is also divisible by 100, so we have one test that says it is a leap year and one that says it is not. What we need to do is to treat the steps as building blocks and combine them. One of the operations that we can use in such situations is to check when a condition does not exist. For example, if the year is divisible by 4 but not by 100, then it must be a leap year. If it is divisible by 100 but not by 400, then it is definitely not a leap year. Thus the third step (check for exceptions when the year is divisible by 4) expands to the following three tests:

Checking for exceptions revised

IF the year is not divisible by 100
then it is a leap year

IF the year is divisible by 100 but not by 400
then it is not a leap year

IF the year is divisible by 400
then it is a leap year

We can simplify the second test because the check for being divisible by 100 is just the opposite of the first test—if the subalgorithm determines that year is not a leap year in the first test, it can return to the main algorithm, conveying this fact. The second test will then be performed only if the year is actually divisible by 100. Similarly, the last test is really just the “otherwise” case of the second test. If the second test did not return, then we know that the year has to be divisible by 400. Once we translate these simplified tests into steps that the fourth graders know how to perform, we can write the subalgorithm that returns true if the year is a leap year and false otherwise. Let’s call this subalgorithm IsLeapYear, and put the year it is to test in parentheses beside the name.

IsLeapYear(year)

Divide the year by 4

IF the remainder isn’t 0
RETURN with false

(We know the year is not a leap year)

Divide the year by 100

(To get to this step, the year must be divisible by 4)

IF the remainder isn’t 0
RETURN true

(We know the year is a leap year)

Divide the year by 400

(To get to this step, the year must be divisible by 100)

IF the remainder isn’t 0
RETURN false

(We know the year is not a divisible-by-400 leap year)

(To get to this point, the year is divisible by 400)

RETURN true

(The year is a divisible-by-400 leap year)

The only piece left is to write the results. If IsLeapYear returns true, then we write that the year is a leap year; otherwise, we write that it is not a leap year. Now we can write the complete algorithm for this problem.

Main Algorithm

Prompt the user to enter a four-digit year

Read the year

IF IsLeapYear(year)
Write year is a leap year

ELSE
Write year is not a leap year

Not only is this algorithm clear, concise, and easy to follow, but once you have finished the next few chapters, you will see that it is easy to translate into a C++ program. We present the program here so that you can compare it to the algorithm. You do not need to know how to read C++ programs to begin to see the similarities. Note that the symbol % is what C++ uses to calculate the remainder, and whatever appears between // and the end of the line is a comment that is ignored by the compiler.

Here is the input and the output of a test run:

2. Most programming languages use the American Standard Code for Information Interchange (ASCII) to represent the English alphabet and other symbols. Each ASCII character is stored in a single byte. The Java language uses a newer standard called Unicode, which includes the alphabets of many other languages. A single Unicode character takes up two bytes in the computer’s memory. With a little extra work on the part of the programmer, C++ can also process Unicode.

3. In the fifth line, the word “cout” has been capitalized instead of being typed entirely in lowercase.

4. The memory unit is also referred to as RAM, an acronym for random-access memory (so called because we can access any location at random).

Divide the year by 4
IF the remainder isn’t 0 RETURN with false	(We know the year is not a leap year)

Divide the year by 100	(To get to this step, the year must be divisible by 4)
IF the remainder isn’t 0 RETURN true	(We know the year is a leap year)

Divide the year by 400	(To get to this step, the year must be divisible by 100)
IF the remainder isn’t 0 RETURN false	(We know the year is not a divisible-by-400 leap year)
	(To get to this point, the year is divisible by 400)
RETURN true	(The year is a divisible-by-400 leap year)

1.	Divide the year by 4
2.	IF the remainder isn’t 0
3.	RETURN false	(We know the year is not a leap year)
4.	Divide the year by 100	(To get to this step, year must be divisible by 4)
5.	IF the remainder isn’t 0
6.	RETURN true	(We know the year is a leap year)
7.	Divide the year by 400
8.	IF the remainder isn’t 0
9.	RETURN false	(We know the year is not a divisible-by-400 leap year)
10.	RETURN true	(The year is a divisible-by-400 leap year)