EST102: Programming in C: The World of Problem Solving
EST102: Programming in C: The World of Problem Solving
EST102: Programming in C: The World of Problem Solving
Chapter 2
The world of problem solving
Narasimhan T.
2.1 Introduction
In today’s digital era, the computer has become an indispensable part of our life. Down
from performing arithmetic right up to accurately determining the position for soft lunar
landing, we rely heavily on digital devices. Problem solving using computers generally
involves the following steps:
1. Identify the problem: The first step toward solving a problem is to identify the
problem. A problem is any task that needs to be accomplished.
2. Understand the problem: Once the problem is identified, its exact nature needs
to be sought. Several techniques can be used to gather information about a problem.
Some of these include conducting interviews, sending questionnaires to people who
are concerned with the problem. Segmenting a big problem into simple manageable
ones often helps in developing a clear picture of the problem.
3. Identify the possible ways to solve the problem: A problem could be solved
in multiple ways. The next step in problem solving involves generating as many
solutions as possible. Brainstorming is one of the most commonly used techniques for
generating a large number of ideas in a short period of time. Brain writing and Mind
Mapping are two additional tools that can be employed here.
4. Select the best way to solve the problem: Once a list of possible solutions is
determined, they have to be expressed in formal representations called algorithms or
pseudo-codes. Then, the pros and cons of each solution is thoroughly analyzed to
select the best solution for the problem.
5. Implementation: Once the best algorithm has been determined, it needs to be
translated into a program, ready for execution on a computer. Program is a set of
14
2.2. ALGORITHMS AND PSEUDOCODES 15
6. Evaluate the solution: In the final step, the program is run with relevant inputs
and the obtained output is checked for correctness. The evaluation must be based on
the feedback from all stakeholders. If the output is not satisfactory, then corrections
have to be made in the program until the goals are met.
Evaluate-Algo
1 Start
2 Read the values of a, b and c.
3 Find the product of b and c.
4 Store the product in a temporary variable temp.
5 Find the sum of a and temp.
6 Store the sum in d.
7 Print the value of d.
8 Stop.
Evaluate-Pseudo
1 Start
2 Read(a, b, c)
3 d=a+b∗c
4 Print(d)
5 Stop
In a pseudocode, Read is used to read input values. Print is used to print a message.
The message to be printed should be enclosed in a pair of double quotes. For example,
16 CHAPTER 2. THE WORLD OF PROBLEM SOLVING
Print(“Hello folks!!”)
prints
Hello folks!!
To print the value of a variable, just use the variable name. In the above example, Print(d)
displays the value of the variable d.
Although pseudocode and algorithm are technically different, we use those words inter-
changeably.
R
exit constructs.
When it is said that “the pseudocode is executed”, it just means that the pseu-
docode instructions are processed. It doesn’t denote the actual execution on a com-
puter.
In the sequence structure, all instructions in the pseudocode are executed (exactly) once
without skipping any. On the other hand, with selection and loop structures, it is possible
to skip or repeatedly execute certain instructions. In such structures, the decision as to
which statements are to be executed or to whether the execution should repeat will be
determined based on the outcome of testing a condition. For writing such conditions, we
use special symbols called relational operators. The various relational operators are listed
in the following table:
Operator Meaning
> greater than
< less than
== equal to
>= greater than or equal to
<= less than or equal to
!= not equal to
It is also possible to link two or more conditions using logical operators like “AND”, “OR”.
Eg:- a > b AND a > c.
2.2.1.1 Sequence
This is the most elementary construct where the instructions of the algorithm are executed
in the order listed. It is the logical equivalent of a straight line. Consider the code below.
2.2. ALGORITHMS AND PSEUDOCODES 17
S1
S2
S3
.
.
Sn
A if structure
There are three variations of the if-structure:
A.1 if structure
The general form of this structure is:
if (condition)
true_instructions
endif
1 if (x > 0)
2 Print(x,“is positive”)
3 endif
if (condition)
true_instructions
else
false_instructions
endif
18 CHAPTER 2. THE WORLD OF PROBLEM SOLVING
This structure contains two blocks of statements. If the test condition is met, the first
block (denoted by true_instructions) is executed and the algorithm skips over the
second block (denoted by false_instructions). If the test condition is not met, the first
block of statements is skipped and the second block is executed.
if (condition1 )
true_instructions1
else if (condition2 )
true_instructions2
else
false_instructions
endif
Example 2.3. The following code compares two variables and prints the relation between
them.
1 if (x > y)
2 Print(x,“is greater than”,y)
3 else if (x < y)
4 Print(y,“is greater than”,x)
5 else
6 Print(“The two values are equal”)
7 endif
There is no limit of the number of else if statements, but at the last, there has to be an
else statement. The conditions are tested one by one starting from the top and preoceeding
downwards. Once a condition evaluates to True, the corresponding block is executed and
rest of the structure is skipped. If none of the conditions are met, the final else part is
executed.
2.2. ALGORITHMS AND PSEUDOCODES 19
B case structure
The case structure is a refined alternative to if-else if-else structure. The pseudocode
representation of the case structure is given below.
caseof (expression)
case value1 :
block1
case value2 :
block2
..
.
default :
default_block
endcase
The case structure works like this: First, the value of expression is compared with value1 .
If there is a match, the first block of statements denoted as block1 will be executed.
Generally each block of statements will have a break at the end which causes the case
structure to be exited. If there is no match, the value of expression is compared with value2 .
If there is a match here, block2 is executed and the structure is exited at the corresponding
break statement. This process continues until either a match for the expression value is
found or until the end of the cases is encountered. The default_block will be executed
when the expression does not match any of the cases.
If the break statement is somehow omitted in the block for the matching case, then the
execution continues into subsequent blocks even if there is no match until either a break is
encountered or the end of the case structure is reached.
Example 2.4. The following pseudocode prints a color name based on the value of a
character called code.
1 caseof (dir)
2 case ‘N’:
3 Print(“North”)
4 break
5 case ‘S’:
6 Print(“South”)
7 break
8 case ‘E’:
9 Print(“East”)
10 break
11 case ‘W’:
12 Print(“West”)
13 break
14 default :
15 Print(“Invalid direction code”)
16 endcase
20 CHAPTER 2. THE WORLD OF PROBLEM SOLVING
A while loop
A while loop is generally used for indefinite iteration. The general form of the while loop
is as follows:
while (condition)
true_instructions
endwhile
B repeat-until loop
The second type of loop structure is the repeat-until structure. This type of loop also
implements indefinite iteration. Here the set of instructions constituting the loop body is
repeated until condition becomes True. That is, the loop body is repeated as long as the
condition evaluates to False. The pseudocode form of repeat-until loop is shown below.
repeat
false_instructions
until (condition)
There are two major differences between while and repeat-until loop constructs:
1. In the while loop, the pseudocode continues to loop as long as the resultant of the
condition is True; in the repeat-until loop, the looping process stops when the
resultant of the condition becomes True.
2. In the while loop, the condition is tested at the beginning; in the repeat-until loop,
the condition is tested at the end. For this reason, the while loop is known as entry
controlled loop and the repeat-until loop is known as exit controlled loop.
It is noteworthy that when the condition is tested at the end, the instructions in the loop
are executed at least once.
2.3. FLOWCHARTS 21
C for loop
The for loop implements definite iteration. There are three variants of the for loop. All
the three for loop constructs use a variable (a.k.a. loop variable) as a counter that starts
counting from a specific value called begin and updates the loop variable after each iteration.
The set of instructions within the loop repeats till the value reaches end . The first for loop
variant can be written in pseudocode notation as follows:
Here, the loop variable (var ) is first assigned (initialized with) the value begin. Then the
condition var <= end is tested. If the outcome is True, the loop body is executed.
After the first iteration, the loop variable is incremented (increased by 1). The condition
var <= end is again tested with the updated value of var and the loop is entered (loop body
is executed) if the condition evaluates to True. This process of updating the loop variable
after an iteration and executing the loop body if the condition (tested with the updated
value of loop variable) evaluates to True continues until the counter value becomes greater
than end . At that time, the condition evaluates to False and the loop execution stops.
In the second for loop variant, whose pseudocode syntax is given just below, the loop
variable is decremented (decreased by 1) after every iteration. And the condition being
tested is var >= end. Here begin should be greater than or equal to end and the loop exits
when this condition is violated.
It is also possible to update the loop variable by an amount other than 1 after every
iteration. The value by which the loop variable is increased or decreased is known as step.
In the pseudocode shown below, the step value is specified using the keyword by .
Table 2.1 lists some examples of for loop. In these examples, var is the loop variable.
2.3 Flowcharts
A flowchart is a diagrammatic representation of an algorithm that clearly depicts how
control flows in it. Flowcharts are composed of various blocks (denoted as symbols) inter-
connected by flow-lines. Each block in a flowchart represents some stage of processing in
the algorithm. Different types of blocks are defined to represent the various programming
constructs of algorithm.
22 CHAPTER 2. THE WORLD OF PROBLEM SOLVING
Flow lines indicate the order in which the algorithm steps are executed. The flow lines
entering a block denote data flow into the block and the flow lines emerging from a block
denote data out flow. Most blocks have only single incoming and outgoing flow lines. The
exception is for blocks representing selection and loop constructs. Such blocks have multiple
exits, one for each possible outcome of the condition being tested and each such outcome
is called a branch.
Table 2.2 lists some commonly used flowchart symbols and their descriptions.
Start
SimpleInterest
1 Start
2 Read(principal , rate, years) Read(principal , rate, years)
3 SI = (principal ∗ rate ∗ years)/100
4 Print(SI ) SI = (principal ∗ rate ∗ years)/100
5 Stop.
Print SI
Stop
Start
LargerTwo
1 Start Read(a, b)
2 Read(a, b)
3 if (a > b)
4 large = a False
a > b?
True
5 else
6 large = b
large = b large = a
7 endif
8 Print(large)
9 Stop.
Print(large)
Stop
Start
SmallestThree
1 Start
Read(a, b, c)
2 Read(a, b, c)
3 if (a < b)
4 small = a False True
a < b?
5 else
6 small = b
7 endif small = b small = a
8 if (c < small )
9 small = c
10 endif
11 Print(small )
12 Stop.
True
c < small ?
small = c
False
Print(small )
Stop
Problem 2.4 To determine the entry-ticket fare in a zoo based on age as follows:
Age Fare
< 10 7
>= 10 and < 60 10
>= 60 5
Start
TicketFare
1 Start Read(age)
2 Read(age)
3 if (age < 10)
4 fare = 7 False True
5 else if (age < 60) age < 10?
6 fare = 10
7 else fare = 7
False True
8 fare = 5 age < 60?
9 endif
10 Print(fare)
fare = 5 fare = 10
11 Stop
Print(fare)
Stop
Grade Message
R Red
G Green
B Blue
Any other value Wrong code
PrintColour Start
1 Start
2 Read(code) Read(code)
3 caseof (code)
4 case ‘R’:
5 Print(“Red”)
6 break caseof
code
7 case ‘G’:
8 Print(“Green”)
9 break ‘R’ ‘G’ ‘B’ default
10 case ‘B’:
Print(“Red”) Print(“Green”)
11 Print(“Blue”)
Print(“Blue”) Print(“Wrong code”)
12 break
13 default :
14 Print(“Wrong code”)
15 endcase
Stop
16 Stop
Figure 2.5: To print colors based on a code value
Start
PrintDown
1 Start
2 for count = 50 downto 1 count
50 1
3 Print(count) -1
4 endfor
5 Stop
Print(count)
count
Stop
Start
PrintMult5
1 Start count
2 for count = 10 to 99 by 5 10 99
5
3 Print(count)
4 endfor Print(count)
5 Stop
count
Stop
Start
SumN
1 Start
Read(n)
2 Read(n)
3 sum = 0
4 for count = 1 to n sum = 0
5 Read(num)
6 sum = sum + num count
7 endfor 1 n
1
8 Print(sum)
9 Stop
Read(num)
count
Print(sum)
Stop
Factorial Start
1 Start
2 Read(n)
3 fact = 1 Read(n)
4 for var = n downto 1
5 fact = fact ∗ var
6 endfor fact = 1
7 Print(fact)
8 Stop
var
n 1
-1
var
Print(fact)
Stop
Start
LargeN
1 Start
Read(n, num)
2 Read(n, num)
3 large = num
4 for count = 1 to n − 1 large = num
5 Read(num)
6 if (num > large) count
7 large = num 1 n−1
1
8 endif
9 endfor Read(num)
10 Print(large)
11 Stop
True
num > large?
large = num
False
count
Print(large)
Stop
Problem 2.11 To determine the average age of students in a class. The user will stop
giving the input by giving the age as 0.
Start
AverageAgev1
1 Start sum = 0
2 sum = 0 count = 0
3 count = 0
4 Read(age) Read(age)
5 while (age!=0)
6 sum = sum + age
7 count = count + 1 while False
8 Read(age) age!=0
9 endwhile
10 average = sum/count
11 Print(average) True
average = sum/count
12 Stop
sum = sum + age
count = count + 1 Print(average)
Stop
Start
AverageAgev2
1 Start sum = 0
2 sum = 0 count = 0
3 count = 0
4 Read(age) Read(age)
5 repeat repeat
6 sum = sum + age sum = sum + age
7 count = count + 1 count = count + 1
8 Read(age)
9 until (age == 0) Read(age)
10 average = sum/count
11 Print(average)
False
12 Stop
until
age == 0
True
average = sum/count
Print(average)
Stop
Figure 2.12: To determine the average age using repeat until loop
2.3. FLOWCHARTS 31
Problem 2.13 To find the average height of boys and average height of girls in a class of
n students.
Solution: See Figure 2.13.
Start
AverageHeight
1 Start Read(n)
2 Read(n)
3 btotal = 0
4 bcount = 0 bcount = 0
gcount = 0
5 gtotal = 0 btotal = 0
6 gcount = 0 gtotal = 0
7 for var = 1 to n
8 Read(gender , height) var
9 if (gender == ‘M ’) 1 n
1
10 btotal = btotal + height
11 bcount = bcount + 1
12 else Read(gender , height)
13 gtotal = gtotal + height
14 gcount = gcount + 1
15 endif
16 endfor False True
17 bavg = btotal /bcount gender == ‘M ’?
18 gavg = gtotal /gcount
19 Print(bavg, gavg)
20 Stop gtotal = gtotal + height btotal = btotal + height
gcount = gcount + 1 bcount = bcount + 1
var
Print(gavg, bavg)
Stop