CSEC IT - Home



Contents

Section 2: Problem-solving and program design 2

Objective 2.1: Outline the steps in problem solving. 2

Objective 2.2: Decompose a simple problem into its significant parts. 2

Objective 2.3: Distinguish between variables and constants 4

Objective 2.4: Use appropriate data types 4

Objective 2.5: Explain the concept of algorithms 7

Objective 2.6: Identify ways of representing algorithms 7

Objective 2.7: Develop algorithms to solve simple problems 7

Objective 2.8 Test algorithms for correctness 23

Section 2: Problem-solving and program design

Objective 2.1: Outline the steps in problem solving.

Objective 2.2: Decompose a simple problem into its significant parts.

Content Definition of the problem; propose and evaluate solutions; Determination of the most efficient solution; develop and represent algorithm; test and validate the solution; decompose a problem into input, processing, output and storage.

The steps in problem solving

The steps in problem solving are:

1. Definition of the problem

2. Propose and evaluate solutions

3. Determination of the most efficient solution

4. Develop and represent algorithm

5. Test and validate the solution

Definition of the problem

Defining the problem is the first step towards solving a problem. It is the most important step since it leads to a clearer understanding of what is given and what is required. If the programmer does not fully understand what is required, then he/she cannot produce the desired solution. This step involves decomposing the problem into three key components:

1. Inputs: what is given (source data)

2. Outputs: the expected results

3. Processing: the tasks/actions that must be performed

To do this, a defining diagram is used. A defining diagram is a table with three columns labeled to represent the components.

Inputs can be identified by the keywords that precede them. These are: GIVEN, ENTER, READ, or ACCEPT.

Outputs can be identified by the keywords: PRINT, DISPLAY, FIND, PRODUCE, or OUTPUT.

Processing can be determined by asking;

“What do I have to do with the inputs in order to produce the desired output?” The actions/tasks determined must be listed in a logical sequential order.

Example:

Given two numbers find and print their product.

Defining diagram:

|INPUT |PROCESSING |OUTPUT |

|2 numbers say num1, num2 |Read two numbers |PRODUCT |

| |Find the product | |

| |Print the product | |

Proposing and Evaluating Solutions

Proposing a solution

The second step in solving a problem is ‘Proposing and Evaluating Solutions’. After defining the problem, you would know what needs to be done. In this step, you figure out how to do it, bearing in mind that a problem can have many different solutions. Initially, go through each step of the solution manually (by hand) using sample input data to see if the solution provides the desired outcome. Then review it to see how you can make it more efficient. After completing the manual solution to the problem the next step is to write the solution as a sequence of instructions.

Example:

Start

Read first number, call it num1

Read second number, call it num2

Multiply num1 by num2

Print product

Stop

Objective 2.3: Distinguish between variables and constants

Variables

In processing data, values that are manipulated need to be stored in a memory location. Because of the large number of storage location in memory, we need to have an identifier to label each location. Depending on if the value changes during the execution of the instructions, it is called a variable. If the value does not change it is called a constant.

Choosing Identifier Names

Choose names that reflect the kind of data that is being stored. It helps any reader to understand the solution better, if the identifier reflects what they store. For example, the variable name product indicates that the value stored in that memory location is a product. If instead, X was used, this does not convey the contents of that memory location to the reader of the solution, and it will make debugging and program maintenance more difficult. Most programming languages have strict rules regarding identifier names, for example, in Pascal, they must begin with a letter or underscore; they can be a combination of letters and digits or underscore and the length cannot exceed 31 characters.

Objective 2.4: Use appropriate data types

Each piece of data stored in memory is of a specific data type. In programming there are five (5) basic data types.

|Data Type |Description |Examples |

|Integer |Positive and negative whole numbers including zero |23,-45, 0 |

|Real |All numbers including fractions |15.7, -19.25, 8 |

|Character |Any key on the keyboard |‘A’, ‘z’, ‘8’, ‘?’ |

|String |Characters put together |‘Hello world’, ‘Marcus’ |

|Boolean |True or False |TRUE or FALSE |

Evaluating solutions

There are many ways to solve some problems. Usually, the initial solution may not be the most efficient solution. As such, in solving any problem you must explore alternative solutions to come up with the best (most efficient) solution.

Some points to consider when developing alternative solutions are:

• Can the result be derived differently?

• Can the solution be made more general? E.g. Would it work if there were more inputs – 100 numbers instead of 3 numbers?

• Can the solution be used for a similar problem? E.g. To find the average mark in the results from a test or average temperature for the month.

• Can you reduce the number of steps and still maintain the logic?

• Can you make it more robust? Would it work properly if incorrect data is entered?

E.g. Given three numbers find and print their average.

Initial solution:

Start

Get first number, call it num1

Get second number, call it num2

Get third number, call it num3

Add num1 to num2 to num3, storing in sum

Divide sum by 3, storing in average

Print average

Stop

First alternative solution:

Start

Get num1, num2, num3

Sum = num1 + num2 + num3

Average = Sum ÷ 3

Print average

Stop

N.B. two steps were removed but the logic is maintained.

Second alternative solution:

Start

Get num1, num2, num3

Average = (num1 + num2 + num3) ÷ 3

Print average

Stop

N.B. One more step and a variable is removed but the logic is maintained. The solution is more efficient since less memory is required, less CPU time is required and the program executes faster since there are fewer instructions to be executed.

Third alternative solution:

Start

N= 3

Sum = 0

Repeat N times

Get number

Add number to sum

End Repeat

Average = sum ÷ N

Print Average

Stop

N.B. This solution is more general. It can easily be adapted to find the average of any amount of numbers by changing the value of N. It utilizes less memory since a single variable is used to hold every number that will be entered.

Initializing variables

In the last solution given above, the variable sum was given the value 0. This is referred to as initialization. This means giving the variable an initial or starting value. Sometimes it is necessary to give variables a starting value. This ensures that any data previously stored in that memory location, from a previous operation, is erased and not used mistakenly in a new operation.

Initialization is also necessary whenever a value needs to be incremented (added to by a value, usually one). For example in adding the numbers entered in the solution above. The statement “Add number to sum” is translated to the computer as “sum = sum + num” therefore if the variable sum has a value stored from a previous operation, the resultant value of sum would be incorrect.

Use the following rule to determine when to initialize a variable:

If a variable appears on the right hand side of an assignment statement before a value is assigned to it, then it must be assigned an initial value before the assignment statement is executed.

Determining the Most Efficient Solution

After evaluating and refining the solution, the next step is to choose the most efficient solution. Use the following attributes to determine the most efficient solution:

1. It should be maintainable (i.e. easy to read and upgrade, if necessary).

2. Should use memory efficiently

3. Should be robust (be able to check for invalid input data)

Objective 2.5: Explain the concept of algorithms

Objective 2.6: Identify ways of representing algorithms

Objective 2.7: Develop algorithms to solve simple problems

Develop and represent the solution as an algorithm

An algorithm is a sequence of precise instructions which, if followed, produces a solution to a given problem in a finite amount of time.

Algorithms can be represented using pseudocode or a flowchart. It cannot be executed by the computer. Pseudocode uses English–like statements that models or resembles a programming language. A flowchart uses geometrical objects.

Algorithmic Structure

Terminator: Start of statement(s)

Declaration: Initialization of variables, if necessary

Body: Sequence of steps

Terminator: End of statement(s)

E.g.

Start {terminator}

sum = 0

count = 0

Repeat

Read num

count = count + 1

sum = sum + num

Until count > 10

Print sum

Stop {terminator}

Control Structures

In programming, control structures are used to represent logic. There are different types of control structures: sequential, selection and loop (repetition). Just like a program, the body of an algorithm is made up of various control structures.

Sequential structures include:

• Input statements: these accept data entered into the computer and store the value in the location with the given variable name e.g.

input name

get num1, num2

read price and tax_rate

accept option

• Output statements: these display/output data that is in the computer’s memory e.g.

Output Sum

Print total_cost

Display “ Enter student’s name”

Write sum, average

• Assignment statements: gives the value on the right of the assignment operator (equal sign) to the variable on the left of the assignment operator e.g.

N= 100

Count = 0

Answer = “END”

• Calculation statements: uses the values on the right of the assignment operator and performs mathematical operations, then assigns the result of the calculation to the variable on the left of assignment operator e.g.

Sum = num1 + num2

Difference = Payment – bill

Average = sum ÷ 3

• Prompting statements: these are used with input statements to request or notify the user to enter data into the computer. These statements are displayed on the screen. Prompting statements precede input instructions. E.g.

Print “Enter student name: “ Prompting statement

Read name

Selection structures include the IF-THEN or IF-THEN-ELSE statements: They perform comparisons between values and make a decision based on the result of the comparison e.g.

• IF ( A > B) THEN

Display A

ENDIF

or

• IF( age >= 50) THEN

Print “Old”

ELSE

Print “Young”

ENDIF

N.B. If the decision consists of more than one instruction statement. These statements must be enclosed in a BEGIN and an END e.g.

• IF (A > B) THEN

BEGIN

C = A + B

Print C

END

ENDIF

Comparisons are made using a condition/decision statement. A condition/decision statement is an expression that when evaluated gives a Boolean result i.e. either TRUE or FALSE. Condition statements use relational operators between two variables e.g.

• A > B

or between a variable and a constant e.g.

• age >= 50

|Relational Operators |Meaning |

|= |Equal to |

| or ≠ |Not equal to |

|> |Greater than |

|< |Less than |

|>= |Greater than or equal to |

| 5, B= 6 >= s, C= 0 t, evaluate

i. A AND B = TRUE

ii. A OR B = TRUE

iii. D AND C = FALSE

iv. A OR C = TRUE

v. B OR D = TRUE

vi. NOT A = FALSE

vii. NOT D = TRUE

viii. NOT C = TRUE

ix. NOT B AND C = FALSE

x. (NOT A) AND (NOT C) = FALSE

Loop structures include the FOR loop, WHILE loop or REPEAT loop: They allow statements to be repeated a fixed number of times or until a condition becomes TRUE or FALSE e.g.

• FOR count = 1 to 5 DO

Print count

END FOR

• WHILE (noOfItems 10

For each loop example given above, the number of times the instructions have to be repeated is known. As such, it is necessary to keep track of how many times the instructions are repeated. This is done by counting or iteration, which involves increasing the value of a counter variable by a fixed number every time the instructions are repeated. This counter can be part of a condition as in the FOR loop.

e.g. FOR count = 1 to 5 DO

Print count

END FOR

Or within the body of the loop e.g. in WHILE loop and REPEAT UNTIL loop.

e.g. WHILE (noOfItems = 10

In both cases, the instructions stop repeating when the value of the counter becomes equal to a certain value. N.B. Counter variables in the WHILE and REPEAT_UNTIL loops MUST be initialized before the counter variable is incremented (increased).

E.g. cars = 0 counter variable is initialized to zero

WHILE cars ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download