Transcript finding a solution to the problem

CARIBBEAN SECONDARY EDUCATION CERTIFICATE (CSEC)
INFORMATION TECHNOLOGY SYLLABUS
TEACHER ORIENTATION WORKSHOP
AUGUST 11TH – 15TH, 2008
TRINIDAD & TOBAGO
Facilitator:
Gerard Phillip
INTRODUCTION
 How are instructions given to the computer?
 Computer programs – finite set of precise instructions
written in a computer language
 Before program is written we must find a way to solve the
problem
 After figuring out how to solve the problem we then
translate the solution into a language meaningful to the
computer
INTRODUCTION
 Giving precise, unambiguous instructions is not
inherent in human nature
 Consider the following: Proceed a mile or so down the
road until you reach the roundabout. Turn left at the
roundabout and follow the road until you reach a
green house on the right hand side. The Post office is
about the 3rd or 4th building on the right after the green
house. You can’t miss it!
INTRODUCTION
 Problem-solving statements/ instructions should be:
 Precise
 Unambiguous
 Must be in a logical sequence
 Finite, i.e. terminate after a definite number of steps
 Teachers must ensure that students have a good grasp of
what these attributes mean
 Students should engage students in problem-solving
exercises involving everyday problems they can relate to.
PROBLEM-SOLVING ON THE COMPUTER
 Examples of everyday problems:
 Write a recipe for making a cheese sandwich
 Write instructions to teach your mom how to retrieve voice
message from a generic cell phone
 Write instructions to give directions to a visitor to get to the
nearest hospital, starting from the school premises
 Write instructions to tell a novice how to download music
from the Internet.
PROBLEM-SOLVING ON THE COMPUTER
 The design of any computer program involves two phases:
 The Problem-solving Phase
 The Implementation Phase
 Problem-Solving Phase comprises the following steps:
1. Define the problem
2. Find solutions to the problem
3. Evaluate alternative solutions
4. Represent the most efficient solution as an algorithm
5. Test the algorithm for correctness
DEFINING THE PROBLEM
 The problem must first be defined: Ensure that students
understand the Problem
 Defining the problem is the first step towards finding a
solution
 It helps the programmer to understand what is given and
what is required
 If the programmer does not fully understand what is
required, he/she cannot produce the desired solution to
the problem
DEFINING THE PROBLEM
 One of the biggest challenges faced in problem-solving is
understanding the problem to be solved.
 Defining the program can be accomplished by
decomposing the problem into three key components:
1.
What is given (the inputs)
2.
The tasks that must be performed (processing)
3.
The expected results (the output)
THE DEFINING DIAGRAM
 Define the problem by constructing a defining diagram
 A table with three columns which represents the three
components: input, processing and output.
 E.g. A program is required to read three numbers and
calculate and print the total.
INPUT
PROCESSING
OUTPUT
3 numbers
e.g. Num1, num2,
num3
1. Get 3 numbers
2. Ad numbers
together
3. Print total
Total
THE DEFINING DIAGRAM
 Input refers to the source data provided - easily identified
by the keywords – given, read or accept, input
 Output refers to the end result required - keywords are
print, display, produce, output
 Processing are the actions must be performed to achieve
the required output - it answers the question: What must
I do with the inputs in order to produce the desired result?
THE DEFINING DIAGRAM
 In the defining diagram, the actions must be listed in a
logical sequential manner
 All necessary actions must be explicitly stated
 The processing section is NOT the solution to the problem.
It’s simply the actions that must be done in order to solve
the problem
 Note that in some cases the input, processing and output
statements might not be as explicitly stated.
PROBLEM 2
 E.g. of problem not clearly stated to facilitate student
identification of the problem:
Given three integers representing the age of three boys
respectively, write a solution to find their average age and
also determine the age of the oldest boy.
 This problem statement could have been stated more
precisely to read:
Given three integers A, B, C, representing the age of three
boys respectively, write a solution to find and display their
average age as well as the age of the eldest boy.
DEFINING DIAGRAM
 Two major tasks to be performed, each consisting of
multiple actions:
INPUT
PROCESSING
OUTPUT
3 integers
Say age1, age2,
age3
1. Read/accept/get 3 integers
2. Find the average of the three
integers
3. Find the highest age
4. Print the average, highest age
Average-age
Highest-age
PROBLEM 3
The cost of a new car is the sum of the wholesale cost,
the local sales tax and the dealer’s percentage mark-up.
Assuming that the dealer’s mark-up is 10 percent of the
wholesale cost and the sales tax is 6 percent, design an
algorithm to read a car ID (an integer value) and the
wholesale cost of the car (a real value) and print the car
ID and the cost to the consumer.
PROBLEM 3
 Here, input and output data are clearly stated. To
determine the processing steps we may ask “What should I
do with wholesale cost in order to find the cost to the
consumer?”
INPUT
PROCESSING
Car-ID, Wholesale-cost 1. Read/get wholesale-cost
2. Calculate dealer’s markup
3. Calculate the sales tax
4. Find the sum of the
wholesale-cost, the
dealer’s mark-up and the
sales tax
5. Print the results
OUTPUT
Car-ID
Consumer-Cost
THE PROBLEM WITH PROBLEM SPECIFICATION
 Many real-world programming problems are not always
precise
 Initial descriptions are often vague, and ambiguous
 Students should be encouraged to evaluate problem
statements and ask questions if they are perceived as
ambiguous
 Also, some information may be implicit in the problem
statement and therefore should be taken into account
when defining the problem
THE PROBLEM WITH PROBLEM SPECIFICATION
Have students evaluate several problem statements,
ranging from simple to complex, some precise, some
ambiguous, lacking pertinent information.
Here are some examples of imprecise problem statements:
 #4: Write a program to print a list of all the employees
who have been in the company for over five years
 #5: Write a program that reads a file that contains
information on the height, weight and age of 100
children. The program should print the names of
all the children who are overweight.
FINDING A SOLUTION TO THE PROBLEM
 Introduction
 The Concept of Variables
 Choosing Variable Names
 Initialization of Variables
FINDING A SOLUTION TO THE PROBLEM
INTRODUCTION
Now that we have defined the problem, we know what we
need to do. We must now figure out how to do it.
 A problem can have many different solutions
 Let students arrive at one that works, however long-winded
 Once a solution is found, it can then be reviewed to see
how it can be optimized, or made more efficient
 The first approach in deriving a solution to a problem is to
do the problem by hand, noting each step as you proceed.
FINDING A SOLUTION TO THE PROBLEM
INTRODUCTION
Problem #6: Find and print the average of three numbers
 Define the problem
INPUT
PROCESSING
OUTPUT
3 Numbers
Say num1,
num2, num3
Read/get 3 numbers
Find the average
Print average
average
 Create sample data: sample input data 5, 3, 25
 Execute each processing step in the defining diagram
manually
FINDING A SOLUTION TO THE PROBLEM
INTRODUCTION
 Having completed a manual solution to the problem, the








next step is to write your solution as a sequence of
instructions
Initial solution
Get the first number, call it num1
Get the second number, call it num2
Get the third number, call it num3
Add num1 + num2 + num3
Divide result by 3
Print result
Stop
FINDING A SOLUTION TO THE PROBLEM
THE CONCEPT OF VARIABLES
In our solution to problem #6, we did not tell the computer
where to put the result of the add operation. The result must be
stored somewhere so it can be accessed later.
Grandma’s fluffy pancakes: Method:
Sift flour in mixing bowl ...
Melt the butter in a frying pan ...
Pour batter into a bowl ...
Just as we need containers to hold or store ingredients, likewise,
in computation, we need something to store or hold the values
we manipulate
FINDING A SOLUTION TO THE PROBLEM
THE CONCEPT OF VARIABLES
 In the computer, values are stored in memory locations.
 There are many memory locations, so in order to keep
track of where our values are stored we need to place a label
or identifier on a particular memory location.
 The label or identifier is called a variable.
 A variable is a symbolic name assigned to a memory
location that stores a particular value
FINDING A SOLUTION TO THE PROBLEM
THE CONCEPT OF VARIABLES
 When we say num1, num2, etc we are actually defining a
variable or an identifier for each number, so that we can
refer to (access) it later.
 We need to tell the computer where to put the result of the
addition of num1, num2, num3
 Add num1 + num2 + num3 storing in Sum
 This would tell the computer that the result of the
computation should be stored in a memory location called
Sum.
FINDING A SOLUTION TO THE PROBLEM
THE CONCEPT OF VARIABLES
Likewise, we must address a similar issue in the last two
statements where we stated,
Divide result by 3
Print result
 Computations are performed by the ALU, part of the CPU
and results are temporarily stored in registers within the
cpu
 These values must be stored in memory locations if they
are to be accessed later
THE CONCEPT OF VARIABLES
 The word variable is derived from the verb ‘to vary’. This
means that the value stored in a particular location can
change from time to time, although the label remains the
same.
 When new values are placed into previously assigned
memory locations, the old values are replaced by the new .
FINDING A SOLUTION TO THE PROBLEM
THE CONCEPT OF VARIABLES
 It is always useful to illustrate the concept of a variable
by using diagrams to show the memory locations:
Memory locations
Num 1
Variables
Num 2
Num 3
5
3
25
FINDING A SOLUTION TO THE PROBLEM
THE CONCEPT OF VARIABLES
We can now revise the initial solution to include the new
variables called sum and average
Get three numbers, say num1, num2, num3
Add num1, num2, num3, storing in sum
Divide sum by 3, storing in average
Print average
THE CONCEPT OF VARIABLES
CHOOSING VARIABLE NAMES
 It’s good practice to choose variable names that reflect the
kind of data that is being stored
 It helps the programmer as well as the reader to understand
the solution better
 It’s important that students grasp the concept of variables
very early in the problem-solving phase.
EVALUATE ALTERNATIVE SOLUTIONS
 Having found a solution to a problem the programmer
should proceed to explore alternative solutions
 The aim is to arrive at the most efficient solution
 The initial solution is usually the first that comes to
mind, but is not always the best solution
 The programmer must evaluate all feasible alternatives
and choose the optimal solution
EVALUATE ALTERNATIVE SOLUTIONS
Points to consider when developing alternative solutions.
 Can the result be derived differently?
 Can the solution be made more general? Would it work if
there were 100 integers, instead of 3?
 Can the solution be used for another problem? E.g. Average
temperature or average grade?
 Can the number of steps be reduced and still maintain the
logic? Can it be made more robust? What would happen if
incorrect data is entered?
REDUCING THE NUMBER OF STATEMENTS
We can reduce the number of statements by combining two
arithmetic statements into one:
1. Add num1, num2, num3 can be written as
Sum = num1 + num2 + num3
(the variable sum is assigned the value of num1 plus num2
plus num3)
2.
Divide sum by 3 storing in average can be written
Average = sum/3
We can combine the two statements to produce:
Average = sum/3
REVISED SOLUTION
Option 2
Get num1, num2, num3
Average = (num1 + num2 num3)/3
Print Average
Stop
Option 1
Get num1, num2, num3
Sum = num1 + num2 + num3
Average = sum/3
Print Average
Stop
The most efficient solution should have the following attributes:
•Should be maintainable
•Should be memory efficient
•Should be robust
INITIALIZATION OF VARIABLES
 Variables that are used as counters or used to store totals
should always be assigned an initial value of 0 before they
are incremented.
 This is called initialization
 E.g. Count = 0
 This ensures that the variable is cleared of any values that
may have been assigned in a previous execution of the
program.
WHAT IS AN ALGORITHM?
At this time, we can now introduce the term ‘algorithm’.
An algorithm is a sequence of precise instructions for solving a
problem in a finite number of steps.
Properties:
 Algorithms must:
 be precise,
 be unambiguous,
 be logically sequenced,
 give the correct solution an all cases, and
 eventually end.
WHAT IS AN ALGORITHM?
Algorithmic structure
Header
: Algorithm’s name or title
Declaration : Brief description of algorithm and variables
used. i.e. A statement of purpose as well as
the initialization of variables
Body
: Sequence of steps
Terminator : An end statement
ALGORITHMIC STRUCTURE
Problem:
Write an algorithm that prompts a student to enter
his/her name and age, accepts the name and age and
then display a welcoming message on the screen such
as “hello Michael! You are 16 years old!”
Write the algorithm identifying the header,
declaration, body and terminator.
ALGORITHMIC STRUCTURE
Algorithm Student data
This algorithm displays a student’s
name and age on the screen.
Start
Display “Enter your name:”
Accept Name
Display “Enter your age:”
Accept Age
Display “Hello”, Name
Display “You are”, Age, “years old”
Stop
{Header}
{declaration}
{Body}
{Terminator}
FLOWCHARTS VERSUS PSEUDOCODE
 Pseudocode is more concise, closely resembles
programming language
 Flowchart gives good view of the structure and flow of
the logic
 Beginners tend to follow the logic easier when using
flowcharts rather than pseudocode
 Longer, more complex solutions are better represented
using pseudocode.
FLOWCHARTS VERSUS PSEUDOCODE
 Usage is a matter of preference for experienced
programmers
 Students should be asked to use both flowcharts as well as
pseudocode to represent algorithms
 Flowcharts must use special geometrical objects that
designate the basic steps of a program:
Input/Output
Processing/
Assignment
Decision
Start/ Stop
PSEUDOCODE AND FLOWCHART
 Start
 Get num1, num2, num3
 Average
(num1 + num2 + num3)/3
 Print Average
Start
Read num1,
num2, num3
 Stop
Average
(num1+num2+num3)/3
Print
Average
Stop
SELECTION STRUCTURES
Selection (decision)
The IF…THEN selection statement
Syntax:
IF (expression) THEN
{Statement (s)}
Execute this statement if logical
expression is TRUE
This construct is used when no action needs to be performed
if the expression returns false.
SELECTION STRUCTURES
Get Mark
IF Mark >= 50 THEN
Print “Well done”
This requires only that the
expression “Well done” be
printed should the student
score 50 marks or more.
Stop
No action is intended
should the mark be less
than 50
SELECTION STRUCTURES
 IF … THEN … ELSE construct syntax:
 IF (expression) THEN
{Statements} executed only if condition is TRUE
ELSE
{Statements} executed only if condition is FALSE
ENDIF
 Only one group of statements could be executed each time
the program is executed.
SELECTION STRUCTURES
Get Mark
IF Mark >= 50 THEN
PRINT “ Well done”
ELSE
PRINT “Must do better”
ENDIF
Stop
 “Well done” will be
printed should the
student’s mark be 50 or
greater.
 If the mark is less than 50
then the statement “Must
do better” would be
printed.
SELECTION STRUCTURES
A worker in a clothing factory is paid an additional incentive
according to the amount of shirts she folds. The basic salary is
$300.00 per week. Should the worker fold 500 or more shirts per
week, an additional 15%, is added to her basic salary. If the
worker folds less than 500 shirts however, she is paid just the
basic salary.
Write an algorithm to determine and print the salary of the
worker.
SELECTION STRUCTURES
Write an algorithm to accept any two numbers, the first a
numerator and the second the denominator. If the second
is equal to zero print “Cannot divide by 0”. Otherwise
divide the first number by the second and print the answer.
SELECTION STRUCTURES
A teacher has realized an error in his marking of students’
scripts. He has therefore decided to credit all students who
got 55 marks and under with an additional 10 marks. Those
who got more than 55 would be credited with an additional
15 marks. Write an algorithm to accept the mark from a
student in a class. Calculate and print the student’s
adjusted mark.
SELECTION STRUCTURES
A store offers customers a discount of 15% if the cost of
any item purchased is equal to or exceeds $200.00.
Should the cost be less than $200.00 however, then a
5% discount is applied. Write an algorithm to accept
the cost of an item. Apply the relevant discount and
calculate and print the net cost (cost – discount).
REPETITION STRUCTURES
 Repetition or Loop or Iteration structures allow statements
to be repeated a fixed number of times or until some
condition evaluates to false.
 There are three repetition constructs:
1.
FOR Loop
- counted loop
2.
REPEAT Loop - conditional loop
3.
WHILE Loop - conditional loop
REPETITION STRUCTURES
The FOR loop construct syntax:
FOR <counter> = <start value> TO <end value> DO
{Statements}
ENDFOR
e.g. FOR X = 1 to 10 DO
{Statements to be executed}
ENDFOR
REPETITION STRUCTURES
 The FOR loop is used when the required number of
iterations (loops) is known beforehand
 The statements are repeated as long as the value of the
identifier specified by the <counter> element does not
exceed the value specified by <end>. A comparison is
made each time the loop iterates to check whether the
<end> is exceeded. If it is not then the counter value is
incremented by one (the default step value)
REPETITION STRUCTURES
 The 12 workers employed in the folding section of a
clothing factory are each paid a basic salary of $500.00 per
week. An incentive is offered according to the amount of
shirts folded. Should a worker fold 600 or more shirts per
week a bonus of 20%, is added to his/her basic salary. If a
worker does not fold as much as 600 shirts however, he/she
is paid just the basic salary.
Write an algorithm to determine and print the salary of
each worker.
REPETITION STRUCTURES
A teacher has realized an error in his marking after having marked all
his students’ scripts. He has therefore decided to credit all students
who got less than 60 with an additional 5 marks. Those who got 60 and
over would be credited with an additional 15 marks. Write an
algorithm to accept the initial marks obtained by the 20 students in the
class. Calculate and print each student’s adjusted mark.
The teacher would like to determine the class average after the marks
are credited. Should the class average exceed 60, “Instructions well
received” should be printed. Otherwise, “Reconsider Teaching
Methods” should be printed.
REPETITION STRUCTURES
A store offers customers a discount of 15% if the total
cost of items purchased is equals or exceeds $400.00.
Should the total be less than $400.00 then 5% discount
is given. Write an algorithm to accept the costs of five
items. Calculate and print the total cost. Apply the
relevant discount and calculate and print the net cost
(total cost – discount).
REPETITION STRUCTURES
WHILE Loop
The WHILE Loop construct syntax:
INPUT Value
WHILE (expression) Do
{statements}
executed if Boolean argument in logical
expression is true
INPUT value to be tested
ENDWHILE
REPETITION STRUCTURES
WHILE Loop
 In processing, the argument (condition) between WHILE
and DO is tested to see if it is true.
 If the condition returns true, the statement(s) that follow
DO will be executed.
 If the condition returns false, execution of the WHILE
statement is stopped. It is possible for the loop never to be
executed if the initial input renders the condition is to be
proven false.
REPETITION STRUCTURES
WHILE Loop
 The while loop can iterate indefinitely, as long as the
condition in the argument expression remains true. It is
terminated only when the condition returns false.
 Write an algorithm that reads a number of arbitrary
integers and find the average of all numbers read. The
program should be terminated if the sentinel value
999 is entered.
REPETITION STRUCTURES
WHILE Loop
 Write an algorithm to accept an unspecified amount of
integers. Calculate and print the sum of the numbers
entered. The algorithm should also determine and print
the highest number entered. The process should be
terminated if the number entered exceeds 1000.
 Write an algorithm to accept the price of items purchased
at a supermarket. The entry of prices should continue as
long as the price entered is not $101.00. Calculate and print
the total cost of items purchased.
REPETITION STRUCTURES
REPEAT Loop
Repeat Loop construct syntax:
REPEAT
{statements to be executed}
UNTIL (Boolean expression)
 The repeat loop is used to iterate a sequence of events until
a specific condition becomes true.
 The statements in the body of a Repeat loop are executed
at least once, because the test of the condition takes place
at the end of the loop.
TRACE TABLES
State what is printed when the following algorithm is
executed.
FOR X = 1 to 3 DO
FOR Y = 1 to 3 DO
Product = Y * X
Print Product
ENDFOR
ENDFOR
TRACE TABLES
What’s printed by the following Algorithm?
AMOUNT = 2
G=4
WHILE AMOUNT < 50 Do
G = G*2
AMOUNT = AMOUNT + G
Print AMOUNT, G
ENDWHILE
TRACE TABLES
INPUT A,B,C
A=B+C
B=A–C
C= A+B
IF A > B THEN
C=A–B
ELSE
C=B–A
ENDIF
Print A,B,C
State what is printed by the algorithm above when the following data is input:
(i)
(ii)
5, 7, 9
9, -7, 5
TRACE TABLES
Complete the trace table based on the following algorithm.
B=2
C=4
Total = 3
WHILE B <= 45 Do
B=B+C
C=C+B
Total = Total + C
ENDWHILE
Print Total
B
C
TOTAL
2
4
3
LIST PROCESSING USING ARRAYS
 What is an Array?
 Accessing the Elements in an Array
 Initializing Arrays
 Reading Values into an Array
 Displaying Array Values
 Traversing Arrays
 Manipulating Arrays
TOP-DOWN DESIGN METHODOLOGY
 What is Top-Down Design?
 Hierarchy Charts
 Sub-dividing a Problem into Modules
 Steps in Modularization
 Representing Modules in Pseudocode and Flowcharts
 Communication between Modules
 Advantages of Top-Down Design Method
FROM ALGORITHMS TO PASCAL PROGRAMS
 Translating Algorithms to Specific Programming Language
 Structure of a Pascal Program
 Pascal in a Nutshell
 Translating Pseudocode into Pascal Code
 Summary
PROGRAM EXECUTION ON THE COMPUTER
 Steps in Executing a Program on the Computer
 Types of Errors
 Debugging
THANK YOU
For your attention and participation