|
CPSC 110-08: Computing on Mobile Phones
|
This lesson delves deeper into loop algorithms, especially those that process lists of data.
Recall the MakeList procedure from the Make-a-list homework, which uses a while loop to create a list of random numbers:
# Procedure to add random numbers to the global variable, theList
# Argument: listSize specifies how many numbers to add to the list
To MakeList(listSize) :
Set global theList to an empty list
While length(theList) < listSize do:
Add a random integer in the range 0-9 to theList
Each time the 'do' slot is executed, a random integer between 0 and 9 is added to thelist. Each time through the loop, the list will grow in size until it reaches a length of listSize at which point the test will be false (length of list is no longer less than listSize) and the loop will terminate.
The while statement is a basic control structure that is used in many programming languages. It provides a standard way to get a program to repeat an action based on some condition.
The MakeList procedure uses the App Inventor while block (in the Control drawer), which implements the while statement. The while block contains a slot for a condition and a do slot, where one or more statements can be placed:
The statement(s) inside the do slot will be repeated while the condition is true.
In order to ensure that the while loop starts and stops correctly, the while statement must be combined with other statements. As shown in the following flow chart, we can distinguish the raw while statement (left) from the while structure (right), which includes initializer and updater steps.
Let's take another look at the MakeList procedure, this time with comments showing how the initialization and update steps are performed:
As you can see, theList starts out as an empty list, with a length of 0. Assuming that listSize is greater than 0, items will be added to the list -- thereby increasing its length -- until its length is equal to listSize. At that point the loop will stop. Thus, this procedure will add listSize random numbers to theList. We can express this in pseudocode as follows:
# Procedure to add random numbers to the global variable, theList
# Argument: listSize specifies how many numbers to add to the list
To MakeList(listSize) :
Set global theList to an empty list
While length(theList) < listSize do:
Add a random integer in the range 0-9 to theList
Initialization Step: Before we enter a while loop we need to perform some initializations. In this case we initialize theList to the empty list. And the listSize argument is also initialized to the value given when the procedure is called.
Loop Entry Condition: Before the while loop performs the do slot, it must test that the loop-entry-condition is true.
Update Step: At least one operation in the do slot must make progress toward the termination of the loop -- e.g., increasing the size of the list.
Thus, in a properly constructed while loop, the following steps are repeated:
Initialize. Test that the entry condition is true. Do the statements in the Do slot, including the Update step. Test that the entry condition is true. Do the statements in the Do slot, including the Update step. ... Stop when the entry condition is false.
An infinite loop results when the loop algorithm does not make progress toward termination -- that is, the test never becomes false.
For each of the following exercises, copy the question to your Portfolio page and then answer the question.
# Function to calculate the sum of a list of numbers # Argument: list contains a list of integers To SumAList(list) : Set global Sum to 0 Set global Index to 1 While Index <=length(list) do: Add to the Sum the selected item in list at index Index Add 1 to the Index Return Sum
# Function to calculate the sum of a list of numbers
# Argument: list contains a list of integers
To SumAList(list) :
Set global Sum to 0
Set global Index to 1
While Index <=length(list) do:
Add to the Sum the selected item in list at index Index
Return Sum
In the previous exercises, you had an algorithm that traversed a list, adding each item to a running total. There were two initializations required: one to initialize the global Sum (the running total) to 0 and a second to initialize the Index to 1. The Index variable, which varies from 1 to the length of the list, is used to traverse the list, selecting items one-by-one from the list and adding those items to the running total. If you forget to update Index (as in the second exercise) you will get an infinite loop.
In addition the while loop, App Inventor provides a for-each loop that will perform some operation for each element on a list.
One of the great advantages of the for-each loop is that it automatically takes care the initialization and update steps that control the process of traversing the list. This makes it much easier to write correct loop algorithms.
There are three slots that need to be filled in to define a for-each loop:
For example, suppose we want to compute the sum of the numbers on our random list. Let's write a Pseudocode function to do that, using the idea of for-each-item-in-a-list:
# Function using a for-each loop to compute the sum of a list of numbers.
# In this case the variable is named item
# In this case the in list is named aList
To computeListSum(aList) :
Set global Sum to 0
For each item is aList do:
Set Sum to Sum + item
Return Sum
And here is the App Inventor definition. The comments point out where App Inventor is automatically (behind the scenes) initializing and updating an index that controls the traversal through the list. Each time through the foreach loop, one item from the list is added to the sum:
Let's use App Inventor's Watch and DoIt features to test our function:
