Repetition Pattern: Counting
Pattern Name:
Repetition Pattern: Counting
Author:
Viera K. Proulx
Intent and Motivation:
Often when writing a program some part of the program needs to repeat several times. We read a list of names, we process items in the grocery purchase, we display a chart of data values, we respond to a sequence of user commands. In some cases we know exactly how many times a task has to be repeated, at other times we may continue until some threshold is reached or a signal is given to stop.
The simplest repetition pattern is when we know ahead of the time how many times a task has to be repeated. The task that will be repeated may depend on which iteration of the repetition is being performed. For example, if we paint ten circles in a row, the horizontal position of the circle that we are painting depends on which circle (first, second, ...) is being painted. We will call these iteration-dependent tasks.
Other repetition patterns are presented later.
Problem Examples:
Problem and Context:
There are four key issues you need to consider when designing counting repetition. The first issue to consider is to determine what is the task that will be repeated and how is it going to be coded. At this point, you will see whether the task is iteration dependent or iteration independent. In some cases, the dependence is fairly minor (print the iteration number with each line of output). In some cases the dependence is more complex (location of the circle in a row of circles).
Next design a counting method. The simplest counting method is to count by ones - starting at one or starting at zero (i.e. 1, 2, 3, ... or 0, 1, 2, ...). If the location of the first circle is 30 and they are 40 pixels apart, you may count from 30 and increment the count by 40 for each repetition (i.e. 30, 70, 100, 130, ...). You need to determine how do you start the count, how do you update the count after each repetition, and what condition determines whether the task should be repeated or whether all repetitions have been done.
If the task is iteration dependent, you need to consider the design of the task code together with the design of the counting method. The goal is always to make the task code simple and understandable.
Finally, you need to determine what initial processing needs to be done before the repetition can start and what post-processing needs to be done after the repetition is completed.
Required Elements and Structure:
In programming the word loop is used instead of repetition. We say that a program loops ten times - or, if we design the loop incorrectly, the program may get into an infinite loop (i.e. repeats the same task forever). Counting loop is controlled by the value of a counting variable.
Loop consists of the following parts:
The program typically performs these steps as follows:
1. Perform Initialization
2. Evaluate Loop Continuation Condition
if it is true - continue
if it is false - go to 5. Post-Mortem
3. Perform Loop Body
4. Perform Loop Update Statement
Return to 2.
5. Post-Mortem
We design these parts as follows:
Outline the first design of the Loop Body.
Design the counting method and adjust the Loop Body if needed.
Design Initialization, including setting the initial value of the counting variable.
Design Loop Update.
Design Loop Continuation Condition.
Design Post-Mortem.
The loop body contains code that may be repeated many times. You want that code to be as efficient as possible. You also want that code to be readable, so that if it needs to be modified, it is clear exactly what the code does. Once you design the counting, you need to see how the counting starts (Initialization) and how is the counting variable updated (Loop Update), before you can decide on the exact form of the Loop Continuation Condition. Finally, when you know how the loop will be performed, you can design Post-Mortem.
Programming a 'for' loop:
Modern programming languages have typically more than one statement that can control repetition. We will start by using the for loop control statement.
We explain the for loop control statement on the following example:
int n; // our initialization
for (int i = 0; i <= 10; i++) { // loop control - see below
n = RequestInt("Next number:"); // loop body
cout << n << " : " << n * n << endl; // loop body
}
// Post-Mortem:
cout << "We printed ten numbers and their squares." << endl;
The loop control statement contains three statements inside the parentheses that follow the keyword
for.The first is the Initialization statement. This statement will be performed once before the loop starts, in addition to any initialization we performed in the code before the for statement. In the example above it declares the counting variable
i and sets its value to 0 (int i = 0;).The second part is Loop Continuation Condition. It is evaluated before the loop starts. If it is false, we proceed with Post-Mortem. If it is true, we continue with the Loop Body. In the example above, it is coded as
i <= 10. So, we repeat the loop body as long as the count is less than or equal to ten.The Loop Update statement is the third part and it is performed after the completion of the Loop Body. In the example above it is a simple increment (
i++).The Loop Body can be one statement or several statements enclosed in { }. In the example above it consists of two statements enclosed in { }.
The code segment above is executed as follows:
Step 1:
int n; is processed (n is declared)Step 2:
int i = 0; is performed (i is declared and initialized - it is valid only until we reach Post-Mortem)Step 3:
i < 10 is evaluated:if it is true, we proceed with the loop body
if it is false, we go to Step 7: Post-Mortem (notice that identifier i is no longer valid)
Step 4: { ... } loop body is performed
Step 5: i++ loop update is performed
Step 6: program returns to Step 3.
Step 7: cout << ... Post-Mortem is performed
Implementation Examples:
The following examples show several different loops - especially different counting methods.
Example 1:
// print ten random numbers
// counting: 1 , 2, 3, 4, 5, 6, 7, 8, 9, 10
for (int i = 1; i <= 10; i++){
cout << RandomLong(10, 99) << endl;
};
cout << "We printed 10 random numbers." << endl;
Example 2:
Roll a dice ten times
// counting: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
for (int i = 0; i < 10; i++){
cout RandomLong(1, 6);
};
Example 3:
Counting variable used; upper bound is variable
// ask user how many numbers to print and print them
// print also the running count
// counting 1, 2, 3, ... , n-1, n
int n = RequestInt("How many numbers?");
for (int i = 1; i <= n; i++){
cout << i << " : " << RandomLong(10, 99) << endl;
};
cout << "We printed " << n << " random numbers." << endl;
Example 4:
// counting with increment other than one
// counting: 5, 10, 15, 20, 25, 30, 35, 40, 45, 50
for (int n = 5; n <= 50; n = n + 5){
cout << n << endl;
};
Note
that the following loop prints the same values:for (int n = 1; i <= 10; i++){
cout << i * 5 << endl;
};
Example 5:
// counting with increment other than one
// observe the start of the loop
// counting: 20, 25, 30, 35, 40, 45, 50, 55, 60, 75
for (int n = 20; n <= 75; n = n + 5){
cout << n << endl;
};
Note
that the following loop prints the same values:for (int n = 1; i <= 10; i++){
cout << 20 + i * 5 << endl;
};
Another variation
(base 25 plus iteration count i times the increment 5)for (int n = 0; i < 10; i++){
cout << 25 + i * 5 << endl;
};
The first and the third method are preferred, as it is easier to understand the nature of the counting.
Example 6:
Loop within a loop (nested loop)
// print n rows with m stars in each row (assume m, n are initialized)
for (int row = 1; row <= n; row++){
for (int col = 1; col <= m; col++){
cout << "* ";
}
cout << endl;
};
cout << "DONE" << endl;
Variation
using encapsulation for the inner loop:// function definition
void PrintRow(int n){
for (int col = 1; col <= n; col ++){
cout << "* ";
}
};
// main program
for (int row = 1; row <= m; row++){
PrintRow(n);
cout << endl;
}
Example 7:
Computing cumulative result
// count number of heads in n coin tosses
// 0 represents tail and 1 represents head
int count; // variable that will keep the count of heads
count = 0; // initialize the count to zero
int n = RequestInt("Number of tosses:");
for (int i = 0; i < n; i++){
count = count + RandomLong(0, 1); // add one to count if head
};
// print the final value of count
cout << "We got " << count << " heads in ";
cout << n << " coin tosses." << endl;
Forces and Variations:
while statement
Summary:
Counting loop consists of five parts: initialization, loop continuation condition, loop body, loop update, and post-mortem. The
for loop control statement contains the loop control variable initialization, the loop continuation condition, and the loop update statement. The loop body follows, enclosed in { } if needed. Additional initialization can be done before the for statement. Post-mortem contains any clean-up or user notification that needs to be done after the loop exits. This again is outside of the for loop statement.When designing loop we suggest starting with the loop body, then designing the loop counting (including loop update) and adjusting the loop body as needed. The design of initialization and loop continuation condition comes at the end.
When designing a loop inside of another loop, it is nearly always better to encapsulate the inner loop by making it an independent function.
Appendix: Counting patterns
This table shows you some of the common counting patterns and how can they be implemented using the
for loop control statement. The table shows concrete examples of numbers used inside the loop. The patterns below then illustrate general formulas.limit = 10 k = 5 a = 13
|
A |
B |
C |
D |
E |
F |
G |
H |
|
i |
n |
k * n |
k * n + a |
limit - i |
limit - n |
k * (limit - i) |
k * (limit - i) - a |
|
0 |
1 |
5 |
18 |
10 |
9 |
50 |
37 |
|
1 |
2 |
10 |
23 |
9 |
8 |
45 |
32 |
|
2 |
3 |
15 |
28 |
8 |
7 |
40 |
27 |
|
3 |
4 |
20 |
33 |
7 |
6 |
35 |
22 |
|
4 |
5 |
25 |
38 |
6 |
5 |
30 |
17 |
|
5 |
6 |
30 |
43 |
5 |
4 |
25 |
12 |
|
6 |
7 |
35 |
48 |
4 |
3 |
20 |
7 |
|
7 |
8 |
40 |
53 |
3 |
2 |
15 |
2 |
|
8 |
9 |
45 |
58 |
2 |
1 |
10 |
-3 |
|
9 |
10 |
50 |
63 |
1 |
0 |
5 |
-8 |
.
A: for (i = 0; i < limit; i++) {... i ...}
B: for (n = 1; n <= limit; n++) {... n ...}
C: for (n = 1; n <= limit; n++) {... k * n ...}
for (x = k; x <= k * limit; x = x +k) {... x ...}
D: for (n = 1; n <= limit; n++) {... k * n + a...}
for (x = k + a; x <= k * limit + a; x = x+ k) {... x...}
E: for (i = 0; i < limit; i++) {... limit - i ...}
for (x = limit; x > 0; x--) {... x ...}
F: for (n = 1; n <= limit; n++) {... limit - n ...}
for (x = limit - 1; x >= 0; x--) {... x ...}
G: for (i = 0; i < limit; i++) {.. k * (limit - i) ..}
for (x = k * limit; x >0; x = x - k) {... x ...}
H: for (i = 0; i < limit; i++) {.. k * (limit - i) - a ..}
for (x = k * limit - a; x >= k - a; x = x - k) {... x ...}