5 Algorithmic Thinking

5.5 Iteration

Goals:
∙ Learn how to create loops or iterate a script over and over;
∙ Create a guessing game in Python.

Computers are especially good at iteration, i.e., repeatedly executing a well-defined task. Iteration is accomplished by executing loops. The loop construct we will utilize in Python is called a while loop. A while loop will execute as long as a given conditional (something that evaluates to True or False) remains True. Each time the conditional evaluates as True, the commands within the while loop are executed.

Example 5.5.1.

The given code illustrates a while loop:

x = 2while x <= 16:    x = 2*x

After setting x equal to 2, the while loop begins. The loop checks on the value of the conditional x <= 16. If the conditional evaluates to True, then the command x = 2*x is executed. If x <= 16 evaluates as False, the command is skipped and the loop is terminated. The following table summarizes the activity of the loop:

Iterations CountConditional x <= 16Execute Command?New Value of 𝚡0𝚃𝚛𝚞𝚎Yes𝟺1𝚃𝚛𝚞𝚎Yes𝟾2𝚃𝚛𝚞𝚎Yes𝟷𝟼3𝚃𝚛𝚞𝚎Yes𝟹𝟸4𝙵𝚊𝚕𝚜𝚎NoNo Change

When the loop terminates, the value of x is 32. ♣

Example 5.5.2.

Suppose n is a positive integer. Let’s construct a function that takes as input n, and outputs the result of the sum

1+2+3+⋯⁢n.

Solution. Here is one way to write it:

PythonCommentsdef f(n):𝚏 is the function name    i = 1𝚒 will be used as a counter    temp = 0𝚝𝚎𝚖𝚙 will be used to store the sum    while i <= n:stop the loop once 𝚒 > 𝚗        temp = temp + iadd 𝚒 to the sum        i = i + 1bump the counter up    return tempreturn the sum

The variable i in the loop is called a counter. The command i = i + 1 within the loop is key, as otherwise the loop wouldn’t terminate. (If you happen to write an infinite loop, just close the window and fix the code in IDLE.) The manner in which temp is used is a common way of building a sum (or product). If you run the module and enter f(4) in the Shell, the following happens: n is set to 4, i is initialized to 1, temp is set to 0, and then the loop executes:

Iterations CountConditional i <= nNew 𝚝𝚎𝚖𝚙New 𝚒0𝚃𝚛𝚞𝚎121𝚃𝚛𝚞𝚎332𝚃𝚛𝚞𝚎643𝚃𝚛𝚞𝚎1054𝙵𝚊𝚕𝚜𝚎No ChangeNo Change

Figure 5.16 illustrates:

Figure 5.16: Sum of Integers Function

♣

Remark: Note the last output: 500000500000L. Python stores large integers in a special way, and that’s what the L denotes, but it doesn’t have an effect on the value and can be ignored.

Example 5.5.3.

Let’s construct a function that does the following: The function uses randbetween(1,100) to generate a random number n between 1 and 100. The function then repeatedly asks the user to guess the value of n until correct. When a guess is incorrect, the function informs the user if the guess was too high or too low.

Solution. The following code can work within the definition of the function:

PythonCommentsn = randbetween(1,100)generate the numberprint "I'm thinking of a number between 1 and 100."g = 0𝚐 stores guesseswhile g <> n:stop when g == n    g = input("Input a guess for the value: ")get a guess        if g < n:too small?            print "Too small."        else:g >= n is 𝚃𝚛𝚞𝚎            if g > n:too big?                print "Too big."print g, " is correct!we’re out of the loop

Figure 5.17 illustrates:

Figure 5.17: Guess Function

♣

Concepts Check: 1. What is the value of x at the end of the loop?
x = 2while x <= 16:    x = x + 3
Answer: 17 2. How many times is the command x = x**2 executed in the loop?
x = 2while x <= 16:    x = x + 3
Answer: 5

5.5.1 Exercises

  1. 1.

    Write a function f that will take as input a positive integer n, and return the result of the sum

    12+22+32+⋯⁢n2.
  2. 2.

    Write a function f that will take as input a positive integer n, and return n!, i.e., return the result of the product:

    n⋅(n-1)⋅(n-2)⁢⋯⁢3⋅2⋅1.

    Recall that n! is read as n factorial.