Problem Solving Andthe Computer

Chapter 3

Problem Solving andthe Computer

An algorithm is a step-by-step operations that the CPU must execute in order to solve a problem, or to perform that task.

A program is the specification of an algorithm in a programming language.

Before you can write a program to solve a problem or to perform a task, you must first determine an algorithm to solve that problem or to perform that task.

This chapter discusses

the basic operations that the CPU can perform, and
how these operations are used to design algorithms.

Algorithm, Flowchart, and Pseudo-code

The basic operationsof a C/C++ programming language are specified using the following statements or structures:

the input statement
the output statement
the assignment statements
the single-way selection structure
the two-way selection structure
the multiple-way selectionstructure
the counter-controlled iteration structure, and
the logically-controlled iteration structure.

Pseudo-Code

These statements and structures are specified in pseudo-code using English language-like statements:

The input statement may be specified using an English-like statement with the keyword read into.

The output statement may be specified using an English-like statement with the keyword write.
The assignment statement may be specified using an English-like statement with the keyword compute or calculate.

Flowcharts

They may also be specified using the flowchart symbols in Figure 3.2:

The input statement is specified by using symbol (b) in which the keyword read is inserted along with the names of the variables where values should be read.

The following says to read the first value into variable num1 and the second value into variable num2:

The output statement is specified by using symbol (b) in which the keyword write is inserted along with the expressions whose values should be printed.

The following says to output the string constant “Result=” followed by the result of the expression num * 5, followed by the result of the expression 3 * (num – 7):

The assignment statement is specified by using symbol (c) in which a C++ like assignment statement is inserted.

The following says to add the value in variable num1, to the value in variable num2 and to store the result in variable sum:

The specification of each of the programming language structures involves a test that the CPU must first performs on a logical expression (also referred to as a condition).

Figure 3.1Flowchart Symbols

SYMBOL

(a)

(b)

(c)

(d)

(e)

(f)

NAME

Terminal

Input/Output

Process

Flow Lines

Decision

Connector

DESCRIPTION

Indicates the beginning or the end of an algorithm.

Indicates an input or an output operation.

Indicates a computation or a data manipulation.

Used to connect the symbols and to indicate the logic flow.

Indicates a decision point in an algorithm.

Indicates an entry or an exit from another part of the flowchart.

Program Development

There are six steps in the development of a program to perform a task or to solve:

These steps are organized into four phases:

the requirements analysis phase
the design phase
the implementation phase and
the testing phase

We use the following simple programming problem to discuss all these steps

Given that the circumference of a circle is 2 *  * r, and that its area is  * r * r, where r is its radius and  is the constant value 3.14, write a C++ program to read the radius of a circle, and to compute its perimeter and area.

Requirements Analysis Phase (Steps 1 and 2)

Step 1:you analyze the problem or the task in order to determine the desired result(s) or the output items that the program must produce.

The objective our sample programming problem is:

to compute the circumference and the area of the circle.

The output items are therefore:

the circumference of the circle(identified as circumf )
the area of the circle(Identified as area)

Step 2:you analyze the problem or the task in order to determine the data items (input or constants) that will be processed in order to produce the desired result(s) or output items.

For our sample programming problem, the input item is:

the radius of the circle(identified as radius).

Design Phase (Steps 3 and 4)

Step 3

You design an algorithm for transforming the data items (input or generated) into the desired result(s) or output.

You specify the algorithm in one of the following ways:

In a programming language,
using a pseudo-code,or
using a flowchart.

For our sample programming problem, the algorithm is specified in pseudo-code as follows:

1. Read the radius of the circle into variable radius.

2. Calculate the circumference of the circle as follows:

circumf = 2 * 3.14 * radius

3. Calculate the area of the circle as follows:

area = 3.14 * radius * radius

4. Display the results (circumference and area).

It is specified using a Flowchart as follows:

Variables:radius(double)to hold the radius of the circle

circumf(double)to hold its circumference

area(double)to hold its area

Step 4:You check the algorithm manually using specific data to make sure that it is correct.

Implementation Phase (Step 5)

Step 5:You write the algorithm that you have designed in step 3 in a programming language.

For our sample programming problem, the program is provided in Figure 3.2

Testing Phase (Step 6)

Step 6:You test the program (using selected test data) to verify that it works correctly, and that it also fulfills its requirements.

Figure 3.2

/*************************************************************

Program to read the radius of a circle and to compute its circumference and area.

*************************************************************/

#include <iostream >

using namespace std;

int main()

{

const double PI = 3.14;// holds the value of PI

double radius,// to hold the radius of a circle

circumf,// to hold its circumference

area;// to hold its area

/*------read the radius of the circle------*/

cout < “\nEnter the radius of the circle:\t”;

cin > radius;

/*------compute its circumference------*/

circumf = 2 * PI * radius;

/*------compute its area ------*/

area = PI * radius * radius;

/*------print its circumference and area------*/

cout < endl“The circumference of the circle is:\t”

< circumf < endl < “and its area is:\t” < area;

return( 0 );

}

Exercise 3.1

1.a.Specify an algorithm (in pseudo-code and using a flowchart) to read the width and the length of a rectangle and to calculate its perimeter and area.

1.b.Write the C++ program that corresponds to the algorithm in question 1a. The output of your program must look like the following:

Enter the width of the rectangle (in inches):12.5

Enter its length (in inches) :10.0

Its perimeter is:45.0 inches

Its area is:125.0 square inches

2. In the division of a positive integer value by 10, the quotient is the same number without the right-most digit (for example, 345 / 10 = 34), and the remainder is the right-most digit (for example, 345 % 10 = 5).

a.Specify an algorithm (using a flowchart) to read a 3-digit positive integer value, and to output its digits in reverse order (for example, if the integer value is 345, the output will be 5 4 3).

b.Write the C++ program that corresponds to the algorithm in question 2a. The output of your program must look like the following:

Enter a three-digit integer value:345

The digits of this number are:543

3.3Logical Expressions

A logical expression (or condition) is an expression that evaluates to either true or false.

There are two types of conditions:

simple conditions and
Compound conditions.

Simple Conditions

A simple condition has the following syntax:

Relational Operators

C/C++ Symbol / Meaning
is less than
is greater than
== / is equal to
<= / is less than or equal to
>= / is greater than or equal to
!= / is not equal to

Evaluation of simple conditions

Assuming that the variables are defined and initialized as follows:

int num1 = 5 , num2 = 7 , num3 = 2;

float fnum = 11.75;

char ch = ‘K’;

Solutions

a)num1 >= 5d)num2 + 3 == num3 * 4

5 >= 57 + 3 == 2 * 4

True10==8

False

b) fnum + 7.2 != fnum / 2e)3 * num1 + 4 < num3 * 2

11.75 + 7.2 != 11.75 / 2 3 * 5 + 4 < 2 * 2

18.95 != 5.875 19 < 4

True False

c) fnum * 2 num1 +20f)‘A’ <= ch

11.75 *2 5 + 20‘A’ <= ‘K’

23.5 > 25 True

False

Characters are ordered according to their ASCII code representations:

‘0' < ‘1' < ‘2' < . . . < ‘9' < ‘A’ < . . . < ‘Z’ < ‘a’ . . . < ‘z’.

Exercise 3.2

Assuming that the variables are defined and initialized as follows:

int num1 = 9 , num2 = 5 , num3 = 10;

float fnum = 12.50;

char ch = ‘P’;

Evaluate the following conditions:

a. num1 <= 5b.3 * num1 + 4 < num3 * 2

c.3 * num2 > fnum + 2d. 2 * num1 + 12 == 3 * num3

e.num1 + 3 != num1 * 4f. ch – ‘M’ == 5

Relational operators have a lower precedence than arithmetic operators:

In the absence of parentheses, arithmetic operations are evaluated before any relational operation is evaluated.

However, it is a good programming practice to use parentheses to clarify the meaning of logical expressions.

Example: (fnum * 2) > (num1 + 20)

Compound Conditions

A compound condition is built from simple conditions and logical operators.

Logical Operators

C++ Symbol / Meaning / Evaluation
AND / <condition1> & <condition2> is true if and only if both conditions are true
|| / OR / <condition1> || <condition2> is true if and only if at least one of the two conditions is true
! / NOT / !<condition> is true if and only if <condition> is false

Evaluations of compound conditions

True || TrueTrue || FalseFalse || TueFalse || False

TrueTrueTrueFalse

True & TrueTrue & FalseFalse & TrueFalse & False

TrueFalseFalseFalse

short-circuit evaluation

There is a short-circuit evaluation of a compound condition when you do not have to evaluate the right-most condition to get its true value:

True || TrueandTrue || FalseTherefore True || -

TrueTrueTrue

False & TrueandFalse & FalseThereforeFalse & -

FalseFalseFalse

Assuming that the variables are defined and initialized as follows:

int num1 = 5, num2 = 7, num3 = 2;

float fnum = 11.75;

char ch = ‘K’;

Compute the true value of each of the following compound conditions:

a)num1 >= 5 || num2 + 3 == num3d)num2 + 3 == num3 * 4 || ch >= ‘Z’

b)‘A’ <= ch& fnum + 7.2 != 2.5e)num1 < 3 & num2 > num3

c) !(3 * num1 + 4 < num3 * 2)f)!(fnum * 2 < num1 + 20)

Solutions

a) num1 >= 5 || num2 + 3 == num3d)num2 + 3 == num3 * 4 || ch >= ‘Z’

5 >= 5 || 7 + 3 == 2 * 4 || ‘K’ >= ‘Z’

True 10 == 8 || False

TrueFalse||False

False

b) ‘A’ <= ch fnum + 7.2 != 2.5e)num1 < 3 num2 > num3

‘A’ <= ‘K’11.75 + 7.2 != 2.5 5 < 3

True& 18.95 != 2.5 False

TrueTrue False

True

c) !(3 * num1 + 4 < num3 * 2)f)!(fnum * 2 < num1 + 20)

!( 3 * 5 + 4 < 2 * 2)!(11.75 * 2 < 5 + 20)

!( 19 < 4)!( 23.50 < 25)

! False!True

TrueFalse

Precedence of C/C++ Operators

The following table lists C/C++ arithmetic, relational, and logical operators with their relative order of precedence.

In the evaluation of an expression, operators with higher precedence are evaluated before those with lower precedence.

Operators with the same precedence are evaluated in the order specified in the “order of evaluation” column.

Operator / Order of Evaluation / Precedence
!
Unary – / right to left / 7
*
/
% / left to right / 6
+
- / left to right / 5
<=
= / left to right / 4
==
!= / left to right / 3
left to right / 2
|| / left to right / 1

Accuracy of Floating-Point Values

The fact that floating-point values are approximated inside a computer makes it difficult to test for the equality of floating-point values.

For example, if the variable fnum is defined as follows:

floatfnum = 7.1;

Then, the condition:fnum / 2 == 3.55 may not be true.

The problem may be solved by assuming that two floating-point values are equal if their difference is relatively very small.

This is done by testing if the absolute value of their difference is less than a certain value chosen by the programmer (for example 0.000001).

Using the library function fabs() that takes as argument a floating-point value and returns its absolute value, the condition:

value1 == value2

is replaced with the condition:fabs(value1 - value2) < 0.000001

which tests whether the difference between the two values is small enough so that we can make them equal.

Evaluation of True and False

In the C/C++ programming language,

The integer value 0 represents false
Any value other than 0 represents true.

The following conditions are therefore equivalent (you can replace one with the other):

Conditions value != 0and value

Saying thatvalue is not zero is the same thing as saying that value is true

Conditions value == 0and! value

Saying that value is zero is the same thing as saying that

value is false or!value is true

bool Data Type

A variable with data type bool can only hold the bool values true and false.

Examples:

bool flag = true;

bool condValue = false, HighTemperature, ExtremeTemperature;

double temperature;

HighTemperature = false;

cin temperature;

HighTemperature = (temperature >= 120);

ExtremeTemperature = (HighTemperature || (temperature <= -20);

Exercise 3.3

A.Assuming that the variables are defined and initialized as follows:

int num1 = 9 , num2 = 5 , num3 = 10;

float fnum = 12.50;

char ch = ‘P’;

Evaluate the following conditions (using short circuit evaluation whenever possible):

a. 2 * num1 - 5 >= 9 || fnum / 2 + 10 <= 6.5

b.num1 + num2 == num3 + 5 & 2 * num3 <= 4 * num2

c.! (num1 + 5 <= 13)

d. 3 * num1 > num1 + num2 & num1+ 3 >= 12

e. ! ( num3 % 4 < 3)

f. num1 - 5 >= num3 || num2 < 15 & num1 >= 9

B.Which of the following conditions are equivalent (that means have the same true value)?

a. num1 != 0b. !num1c.num1 == 0d. !(num1 == 0)e. num1

C.Suppose that a person’s age is stored in the variable age, his number of children in the variable NumChild, his salary in the variable salary, and his height in the variable height. Write relational expressions to specify the following conditions:

a.he is 45 year old.

b.he is more than 5.7 feet tall.

c.his salary is between 35,000 and 50,000.

d. he does not have 3 children.

h.he is either 6.0 feet tall, or he has less than 4 children.

j. he is not older that 35 and he has 2 or 3 children

3.4Two-Way Selection using the if-else Structure

Purpose

To ask the CPU to test a condition and then to choose the course of action(s) to perform based on whether that condition is true or false.

A two-way selection structure is specified using a flowchart as follows:

False True

It says to do the following:

Test condition

a. if it is true, perform the operations specified by T-Statement

b. otherwise, perform the operations specified by F-Statement.

T-Statement is one or more statements that specify the T-Action,

F-Statement is one or more statements that specify the F-Action

Next-Statement is the statement that specifies theaction to be performed next.

It may be specified in pseudo-code as follows:

1. If <condition> is true, do the following:

<T-Statement>

2. Otherwise, do the following:

<F-Statement>

3. Next-Statement

Itis specified in the C++ programming language using the if - else structure with the following syntax:

if(<condition>)

<T-statement>

else

<F-statement>

<Next-Statement>

Here:

T-statement> is a single statement that specifies the T-Action

<F-statement> is a single statement that specifies the <F-Action>.

Case Study 3.1

Problem Statement

Write a program to read the age of an individual, and to output the message “serve alcohol drink” if he is 21 or older, and the message “serve juice” otherwise. Your program will then output the message “thank you for using this program.”

Program Logic

output:“Serve alcohol” or “Serve Juice”, depending on the individual’s age.

Input:an individual’s age.

Variables:age(int)to hold an individual’s age.

Algorithm Specification (using a Flowchart)

FalseTrue

Algorithm Specification (using Pseudo-code)

1. Read the individual’s age into variable age.

2. If this individual’s age is 21 or more, do the following:

2.a. output the message “serve alcohol drink”.

3. Otherwise, do the following:

3.a. output the message “serve juice”.

4. Output the message “thank you for using this program”.

Figure 3.3Using the if-else Structure

/***************************************************************

Program to read the age of an individual and to output the type of drink that he should be served

***************************************************************/

#include <iostream>

using namespace std;

#define DRINKAGE21

int main()

{

int age;// to hold an individual’s age

/*------read the individual’s age------*/

cout“\n\nEnter the individual’s age please:\t”;

cinage;

/*---determine what type of drink he should be served -----*/

if (age >= DRINKAGE)// he is over the drinking age

cout endl “Serve alcohol drink”;

else// he can not drink alcohol

coutendl“Serve juice”;

coutendl“Thank you for using this program”;

return (0);

}

PracticeExercise 3.4 (1a and b).

HomeworkExercise 3.4(2 a and b).

Exercise 3.4

1.a.Specify an algorithm (in pseudo-code and using a flowchart) to read a non-zero integer value and to determine if it is positive or negative. If it is positive, print it with the message “POSITIVE”, otherwise, print it with the message “NEGATIVE.” At the end, print the message “Thank You.”

1.b.Write the C++ code segment that corresponds to the algorithm in question 1a.

2.a.Specify an algorithm (using a flowchart) to read a character value and to determine if it is a digit (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). If it is, print it with the message “DIGIT”; otherwise print it with the message “NOT A DIGIT.”

2.b.Write the C++ code segment that corresponds to the algorithm in question 2a.

Case Study 3.2

Problem Statement

Write a program to read a positive integer value and to determine if it is even or odd. If it is even, print it with the message “EVEN”; otherwise, print it with the message “ODD”.

Program Logic

Output:the input value with the message “EVEN” or “ODD”, depending on whether the input value is even or odd.

Input:an integer value.

Variable: num (int)to hold the input value.

Note:

An integer value is even if the remainder in its division by 2 is 0; otherwise, it is odd.

Algorithm Specification (using Pseudo-code)

1.Read a positive integer value into the variable num.

2.If num % 2 is 0, then do the following:

2.aprint the input value with the message “EVEN”.

3.Otherwise do the following:

3.aprint the input value with the message “ODD”

Algorithm Specification (using a Flowchart)

FalseTrue

Figure 3.4Using the if - else Structure

/**************************************************************

Program to read an integer value and to determine if it is even or odd

**************************************************************/

#include <iostream

using namespace std;

int main()

{

int num;// to hold the value read

/*------read in an integer value------*/

cout“\n\nEnter an integer value please:\t”;

cinnum;

/*------determine if it is even or odd ------*/

if (num %2 == 0)// it is even

coutendlnum“\tEVEN”;

else// it is odd

coutendlnum“\tODD”;

return ( 0 );

}

PracticeExercise 3.5.

Exercise 3.5

1.a.Specify an algorithm (using a flowchart) to read an integer value and to determine if it is a multiple of 5. If it is a multiple of 5, print it with the message “MULTIPLE OF 5”, otherwise, print it with the message NOT MULTIPLE OF 5.”

1.b.Write the C++ code segment that corresponds to the algorithm in question 1a.

Compound Statement

A compound statement has the following syntax:

{

(One or more statements to be executed as a block)

}

Example

{

cout“\n\nEnter the dividend please:\t”;

cin dividend;

cout“\nThe quotient in the division of:\t”

dividend < “ by ”divisor “\tis:\t”

(dividend / divisor);

cout“\nand the remainder is:\t” (dividend % divisor);

}

The statements of a compound statement are executed one after another, starting with the first one in the sequence.

Purpose

To specify two or more statements where only one statement is allowed.

Examples

if(num1 > num2)
{
num2 = num1 + 5;
num1 = num1 +1;
}
else
num1 = num2 -5 ; / if(num1 < num2)
num2 = num1 + 4;
else
{
num2 = num1 + 5;
num1 = num1 +1;
}