Transcript CSEC Problem Solving Presentation (1)(2)x

CARIBBEAN SECONDARY EDUCATION CERTIFICATE (CSEC)
INFORMATION TECHNOLOGY SYLLABUS
TEACHER TRAINING WORKSHOP
JANUARY 20th – 21st, 2010
ST. LUCIA
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 your grandparent 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 ON THE COMPUTER
 Problem-Solving Phase comprises the following
steps:
Define
the
problem
Find a
solution to
the
problem
Evaluate
alternate
actions
Represent
the most
efficient
solution as
an
algorithm
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 outputs)
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 then
calculate and print the sum.
INPUT
PROCESSING
OUTPUT
3 numbers
e.g. Num1, num2,
num3
1. Get 3 numbers
2. Add numbers
together
3. Print Sum
Sum
THE DEFINING DIAGRAM
Input
Output
Processing
• Refers to the source data provided
• Keywords: read, accept, input, given
• Refers to the end result required
• Keywords: display, print, output, produce
• Refers to the actions performed to achieve the
required output
• Answers the question – What must I do with
the input in order to produce the desired
output
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 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.
PROBLEM 2
 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 age, highest age
Average-age
Highest-age
PROBLEM 3
The cost of a new car is the sum of the wholesale cost,
the 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, write
an algorithm to read the wholesale cost of the car and
print 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
OUTPUT
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
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 a strainer...
Melt the butter in a frying pan ...
Pour batter into a mixing 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
 We can 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, and store in Sum
Divide Sum by 3, store 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 of an algorithm:
 precise,
 unambiguous,
 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}
Flowchart
Pseudocode
Gives view of
program
structure and
logic flow
Precise,
resembles
programming
code
Beginners can
follow program
flow much easier
Better to
represent longer,
more complex
algorithms
FLOWCHARTS VERSUS PSEUDOCODE
 Usage is a matter of preference for experienced
programmers
 Students should 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
FLOWCHART
 Start
 Get num1, num2, num3
 Average
(num1 + num2 + num3)/3
 Print Average
 Stop
Start
Read num1,
num2, num3
Average
(num1+num2+num3)/3
Print
Average
Stop
SELECTION STRUCTURES
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 a stated
condition evaluates to false.
 There are three repetition constructs
FOR Loop
• (counted)
WHILE
Loop
REPEAT
Loop
• (conditional)
• (conditional)
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
For Loop
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
For Loop
Write an algorithm to calculate and print the total
amount of money earned by a family doctor at the end
of a six-day work week. The amount earned each day
is dependant on the number patients he sees each day.
To see the doctor a patient must pay a fee of $120.00
REPETITION STRUCTURES
For Loop
Write an algorithm to print the seven-times table for
numbers 1 to 15
Write an algorithm to calculate and print the square of
all even numbers between 1 and 20. The algorithm
must also calculate and print the sum of all the
squares.
REPETITION STRUCTURES
For Loop
Write an algorithm to accept the scores made by each
player on a cricket team. The algorithm should
determine and print the highest score made as well as
the team average score.
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 to be proven false.
REPETITION STRUCTURES
WHILE Loop
 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.
REPETITION STRUCTURES
WHILE Loop
 Write an algorithm to accept the price of items purchased
at a supermarket. The entry of items 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
WHAT IS AN ARRAY?
 A group of data items that are all of the same type
 Contains any number of storage locations to store variables
of the same type
 A single name (identifier) is used to identify an array
 The storage locations in an array are uniquely identified by
using a subscript
WHAT IS AN ARRAY?
 Elements in an array are organized in sequence
 Elements can be accessed directly by specifying their
position in the sequence, using the subscript or index
 If only one index (subscript) is used the array is called a
one-dimensional array
WHAT IS AN ARRAY?
 We can illustrate the one-dimensional array as follows.
Array Temp
Temp[1]
45
Temp[2]
32
Temp[3]
100
Temp[4]
98
Temp[5]
Data
values in
adjacent
memory
locations
ACCESSING ELEMENTS IN AN ARRAY
 Elements can be accessed individually by specifying
the name of the array followed by the index or
subscript.
 A special variable must be declared as the index of the
array (i, j, k, are commonly used), e.g. Temp[i]
 Using the index, the elements in an array can be
manipulated the same way that we manipulate
ordinary variables.
INITIALIZING ARRAYS
 Set i to 1
 Repeat 10 times
 Temp[i]
0
 Increment i
End-repeat
First iteration i = 1 and Temp[1] would be assigned 0
Second iteration i = 2 and Temp[2] would be assigned 0
READING VALUES INTO AN ARRAY
 Read 10 values into the array Temp
 Set i to 1
 For i = 1 to 10 Do
 Read Temp[i]
End-For
1
2
3
4
5
6
7
8
9
10
45
32
100
98
60
37
30
28
18
75
DISPLAY ARRAY VALUES
 Writing or printing values stored in arrays is similar to
reading values into an array.
 We would already know the number of items stored
 Set i to 1
 Repeat 10 times
 Display Temp[i]
 Increment i
End-repeat
TRAVERSING ARRAYS
 Moving through the array in a sequential manner in
order to manipulate the elements in some way.
 Array is traversed when we print the elements, search
the elements for a particular item, sort the list of items
in a specific order, etc.
 Very often we traverse an array to search for an item
LINEAR SEARCH
 Set Size to 20
 Set Target to 45
 Set index to 1
 Set Found to false
 While ((Found is false) and (Index <=Size))
 If (Temp[index] = Target) then

{if the value is found set the flag to true}
Set Found to true
Else
increment index
 End-while
 If (found = true then
{otherwise move on to the next element in the array}
 display “Target found at location”, index
Else
display “Target not found”
Stop.
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
CXC Jamaica Office: 876 630-5200
Mr. Gerard Phillip : mobile 876 809-0854