-
Notifications
You must be signed in to change notification settings - Fork 0
3. Iteration Control Structures
- To develop algorithms which use the DOWHILE and REPEAT-UNTIL control structures
- To introduce a pseudocode structure for counted iteration loops
- To develop algorithms using variations of the iteration construct
##Loops The solution algorithms developed so far have one characteristic in common - they show the program logic required to process just one set of input values. However, most programs require the same logic to be repeated for several sets of data. The most efficient way to deal with this situation is to establish a looping structure in the algorithm. This will cause the processing logic to be repeated a number of times.
###DOWHILE (Also know as a WHILE loop) DOWHILE condition p is true statement block ENDDO
As the DOWHILE loop is a leading decision loop, the following processing takes place:
A. The logical condition p is tested B. If condition p is found to be true, then the statements within the statement block will be executed once. Control will then return to the retesting of the condition p (step a). C. If condition p is found to be false, then control will pass to the next statement after ENDDO and no further processing will take place.
As a result, the DOWHILE structure will continue to repeat a group of statements WHILE a condition remains true. As soon as the con- dition becomes false, the construct is exited.
There are two important considerations about which a programmer must be aware before designing a DOWHILE loop. Firstly, the testing of the condition is at the beginning of the loop. This means that the programmer may need to perform some initial processing to adequately set-up the condition before it can be tested. Secondly, the only way to terminate the loop is to render the DOWHILE condition false. This means that the programmer must set up some process within the statement block which will eventually change the condition so that the condition becomes false. Failure to do this results in an endless loop.
###Example 1 - Fahrenheit - Celsius conversion
A temperature file consists of fifteen records, each containing a temperature in degrees fahrenheit. A program is to be written which will read and print both temperatures in two columns on a report. Column headings which read 'Degrees F and 'Degrees C are to be printed at the top of the page.
Defining diagram
INPUT | PROCESSING | OUTPUT 15 records | Print column headings | Headings F-temp | For each record | F-temp | Read F-temp | C-temp | Convert F-temp to C-temp | | Print F-temp, C-temp |
In this example, the programmer will need:
- -- a DOWHILE structure to repeat the necessary processing, and
- -- a counter, initialised at zero, which will control the fifteen repetitions. This counter, called record-counter, will contain the number of records read and processed. The programmer should now write down the solution algorithm. b
Solution
Fahrenheit-to-Celsius
Print 'Degrees F and 'Degrees C
Set record-counter to zero
DOWHILE record-counter < 15
Read F-temp
Compute C-temp = (F-temp - 32) * 5/9
Print F-temp, C-temp
Add 1 to record-counter
ENDDO
END
Note: the 'record-counter' variable is initialized before the loop, tested in the DOWHILE condition at the top of the loop, and incremented within the body of the loop. It is essential that the variable which controls the loop is acted upon in these three places.
A program is required to read and print a series of names and exam scores for students enrolled in a mathematics course. The class average is to be computed and printed at the end of the report. Scores can range from 0 to 100. The last record contains a blank name and a score of 999 and is not to be included in the calculations.
***Defining diagram ***
INPUT | PROCESSING | OUTPUT Student-records containing | For each record: | Student-report containing Name | Read student record | Names Exam-score | Print student record | Exam-scores Record-999 | Compute Average-score | Average-score | Print Average-score |
The programmer will need to consider the following requirements when establishing a solution algorithm:
- -- a DOWHILE structure to control the reading of exam scores, until it reaches a score of 999.
- -- an accumulator for the total scores, viz Total-score.
- -- an accumulator for the total students, viz Total-students.
Solution
Print-examination-scores
Set Total-score to zero
Set Total-students to zero
Read Name, Exam-score
DOWHILE Exam-score NOT = 999
Add 1 to Total-students
Print Name, Exam-score
Add Exam-score to Total-score
Read Name, Exam-score
ENDDO
Average-score = Total-score/Total-students
Print Average-score
END
This solution algorithm is a typical example of the basic algorithm design required for processing sequential files of data. There is an unknown number of records, so the condition which controls the exam score processing is the testing for the trailer record (Record-999). It is this test which appears in the DOWHILE clause (DOWHILE Exam-score NOT = 999).
However, this test cannot be made until at least one exam score has been read. Hence, the initial processing, which sets up the condition, is a read statement immediately before the DOWHILE clause (Read Name, Exam-score). This is known as a priming read and its use is extremely important when processing sequential files.
The algorithm will require another Read statement, within the body of the loop. Its position is also important. The trailer record must not be included in the calculation of average score, so each time an exam score is read, it must be tested for a 999 value, before further processing can take place. For this reason the Read statement is placed at the end of the loop, immediately before ENDDO, so that its value can be tested when control returns to the DOWHILE condition. As soon as the trailer record has been read, control will exit from the loop to the next statement after ENDDO -- the calculation of Average-score.
This priming read before the DOWHILE condition and subsequent read within the loop, immediately before the ENDDO statement, forms the basic framework for DOWHILE repetitions in pseudocode. In general, all algorithms using a DOWHILE construct to process a sequential file should have the same basic pattern, as follows:
Process-Sequential-file
Do Initial processing
Read first record
DOWHILE more records exist
Process this record
Read next record
ENDDO
Do Final Processing
END
The REPEAT.UNTIL structure is similar to the DOWHILE structure, in that a group of statements are repeated, in accordance with a specified condition. However, where the DOWHILE structure tests the condition at the beginning of the loop, a REPEAT..UNTIL structure tests the condition at the end of the loop. This means that the statements within the loop will be executed once, before the condition is tested. If the condition is false, the statements will then be repeated UNTIL the condition becomes true.
The format of the REPEAT..UNTIL structure is REPEAT statement, statement ... UNTIL condition is true
As can be seen, REPEAT..UNTIL is a trailing decision loop; the statements are executed once, before the condition is tested. There are two other considerations about which a programmer needs to be aware, before using REPEAT..UNTIL:
- REPEAT..UNTIL loops are executed when the condition is false. It is only when the condition becomes true, that repetition ceases. Thus, the logic of the condition clause of the REPEAT..UNTIL structure is the opposite of DOWHILE:
For instance: DOWHILE more records is equivalent to REPEAT.UNTIL no more records; and DOWHILE number not = 99 is equivalent to REPEAT. UNTIL number = 99.
- The statements within a REPEAT..UNTIL structure will always be executed at least once. As a result, there is no need for a priming read when using REPEAT..UNTIL. One read statement at the beginning of the loop is sufficient.
Let us now compare an algorithm, which uses a DOWHILE structure, with the same problem using a REPEAT.UNTIL structure.
Consider the following DOWHILE loop:
Process-Student-Records
Set student-count to zero
Read student record
DOWHILE student number not = 999
Write student record
Increment student-count
Read student record
ENDDO
Print student-count
END
This can be rewritten (incorrectly) as a trailing decision loop, using the REPEAT .UNTIL structure as follows:
Process-Student-Records
Set student-count to zero
REPEAT
Read student record
Write student record Incorrect REPEAT UNTIL
Increment student-count Logic
UNTIL student number = 999
Print student-count
END
This algorithm is incorrect, because the statements within the loop will be repeated just one time too many! Instead of immediately terminating the repetition once the trailer record has been read (Read student record), there are two more statements in the loop which will be executed, before the condition is tested. To avoid this, logic must be included which will prevent the processing of data, once the trailer record has been read. This logic takes the form of an IF statement, immediately after the Read, as follows:
Process-Student-Records
Set student-count to zero
REPEAT
Read student record
IF student number not = 999 THEN
Write student record
Increment student-count
ENDIF
UNTIL student number = 999
Print student-count
END
###Example 3 - Process inventory records A program is required to read a series of inventory records which contain item number, item description and stock figure. The last record in the file has an item number of zero. The program is to produce a 'Low Stock Items' Report, by printing only those records which have a stock figure of less than 20 items. A heading is to print at the top of the report and a total low stock item count to print at the end.
Defining diagram
INPUT | PROCESSING | OUTPUT Inventory record containing: | Print Heading for each inventory record | Heading 'Low Stock Items' item number | read record | Inventory List containing item description | print record | item number stock figure | increment Total-Low-Stock Items | item description | print Total-Low-Stock-ltems | stock figure | | Total-Low-Stock-ltems
The programmer will need to consider the following requirements when establishing a solution algorithm:
- a REPEAT./UNTIL to perform the repetition (a DOWHILE could also have been used),
- an IF statement to select stock figures of less than 20,
- an accumulator for Total-Low-Stock-I terns, and
- an extra IF, within the REPEAT loop, to ensure the trailer record is not processed.
Solution algorithm, using REPEAT..UNTIL
Process-inventory-records
Set Total-Low-Stock-ltems to zero
Print 'Low-Stock Items' Heading
REPEAT
Read inventory record
IF item number > zero THEN
IF stock figure < 20 THEN
print item number, item description, stock figure
increment Total-Low-Stock-ltems
ENDIF
ENDIF
UNTIL item number = zero
Print Total-Low-Stock-Items
END
The solution algorithm has a simple structure, with a single read statement at the beginning of the REPEAT..UNTIL loop and an extra IF statement within the loop to ensure the trailer record is not incorrectly incremented into the Total-Low-Stock-ltems accumulator. The solution algorithm will now be represented by a DOWHILE structure:
***Solution using DOWHILE ***
Process-inventory-records
Set Total-Low-Stock-Items to zero
Print 'Low Stock Items' Heading
Read inventory record
DOWHILE item number > zero
IF stock figure < 20 THEN
print item number, item description, stock figure
increment Total-Low-Stock-ltems
ENDIF
Read inventory record
ENDDO
Print Total-Low-Stock-ltem
END
This solution, using DOWHILE, also has simple structure, with a priming read, and a read at the end of the loop, just before ENDDO. When a record containing an item number of zero is read, the DOWHILE condition will become false and the looping will cease.
##Counted Repetition (For Loop) Counted repetition occurs when the exact number of loop iterations is known in advance. The execution of the loop is controlled by a loop index, and instead of using DOWHILE, or REPEAT..UNTIL, the simple keyword DO is used.
DO loop-index = initial-value to final-value
statement block
ENDDO
The DO loop does more than just repeat the statement block. It will
- initialize the loop-index to the required initial-value;
- increment the loop-index by 1, for each pass through the loop;
- test the value of loop-index at the beginning of each loop to ensure that it is within the stated range of values; and
- terminate the loop when the loop-index has exceeded the specified final-value.
In other words, a counted repetition construct will perform the initializing, incrementing and testing of the loop counter automatically. It will also terminate the loop once the required number of repetitions have been executed. In view of these properties, a counted repetition construct should be used wherever appropriate.
###Example 4 - Print student list A program is required to read a file of 350 student records containing name, address, sex and age and to produce a STUDENT LIST. If a student is over 40 years of age, then an asterisk '*' is to be printed beside that student's details. A total of the number of students over 40 years of age is also to be printed at the end of the report.
Defining diagram
INPUT | PROCESSING | OUTPUT 350 student records: | Print Heading For each student: | Heading 'STUDENT LIST' name | read record | Student Details containing: address | print details | name sex | print '*' | address age | increment | sex | Total-Students-Over-40 | age | Print Total-Students-Over-40 | Total-Students-Over-40
Solution
This is an example of a counted repetition loop. The problem statement indicates that the file contains exactly 350 records. So, the algorithm should contain a DO loop to control the repetition.
Print-student-list
Print 'STUDENT LIST Heading
Set Total-Students-Over-40 to zero
DO loop-index = 1 to 350
read student record
print student details
IF age > 40 THEN
print '*'
increment Total-Students-Over-40
ENDIF
ENDDO
Print Total-Students-Over-40
END
Note the DO loop controls all the repetition:
- it initializes the loop-index to 1;
- it increments the loop-index by 1 for each pass through the loop;
- it tests the loop-index at the beginning of each pass to ensure it is within the range 1-350; and
- it automatically terminates the loop once the loop-index has exceeded 350.
Construct a solution algorithm for the following programming problems. Your solution should contain:
- a defining diagram
- a pseudocode algorithm solution
Exercise 1. Design a program which will read a file of product records, each containing the item number, item name, the quantity sold this year and the quantity sold last year. The program is to produce a Product List' showing the item number, item name, and the increase or decrease in the quantity sold for each item.
Exercise 2. Design a program which will read a file of 50 employee records. Each record contains the employee's number, name and weekly hours worked. If the employee has worked more than 35 hours in that week, then his number, name, and hours worked in excess of 35, are to be printed on a weekly Overtime Report'. At the end of the report, print the total overtime hours worked that week. The first record of a set of records contains a bank account number and an opening balance. Each of the remaining records in the set contains the amount of a cheque drawn on that bank account. The trailer record contains a zero amount.
Exercise 3. Design a program which will read and print the account number and opening balance on a 'Statement of Account' report. The rest of the amounts are to be read and printed on the report, each with a new running balance. A closing balance is to print at the end of the report.
Exercise 4. Design a program which will read a file of employee records containing employee number, employee name, hourly pay rate, regular hours worked and overtime hours worked. The company pays its employees weekly according to the following rules:
- Regular pay = regular hours worked x hourly rate of pay
- Overtime pay = overtime hours worked x hourly rate of pay x 1.5
- Total pay = regular pay + overtime pay
Your program is to read the input data on each employee's record and compute and print the employee's total pay, on the 'Weekly Payroll Report. All input data and calculated amounts are to appear on the report. A total payroll amount is to appear at the end of the report.
Written by: H. Burgess - Specialist Curriculum Coordinator Codemaster Institute
April 2016