Lecture Notes
Introduction to Programming and Algorithm Design (COP-1000)

Iteration

This chapter shows how to implement loops in your program's flow of control, without using recursion.


Multiple Assignment

  • A variable can be (and often is) assigned different values over the execution of a program
  • A variable can refer to only one value at a time

>>> x = 9
>>> print x
9
>>> x = 54
>>> print x
54

  • It is very important to distinguish between the assignment operator (=) used in an assignment statement, and the equality operator (==) used in a Boolean condition:

>>> x = 20
>>> y = 25
>>> x == y     # is x equal to y ?
False
>>> x = y      # assign the value of y to x
>>> x == y     # is x equal to y now ?
True


Updating variables

  • To update the value of a variable means to change its value using its previous value as part of the expression that is used to calculate its new value
  • A common update is to increment add one to a variable:

>>> x = 9
>>> x = x + 1       # increment x
>>> print x
10

  • Be sure the variable is defined (has been assigned a value) before you try to update it:

>>> y = y + 1

Traceback (most recent call last):
  File "<pyshell#4>", line 1, in <module>
    y = y + 1
NameError: name 'y' is not defined

  • To decrement a variable is to subtract 1 from it
  • You can also use the shortcut assignment operators +=, -=, *= and /= to update a (previously define) variable:

>>> k = 5
>>> k += 10         # same as k = k + 10
>>> print k
15

  • Note that to update a variable you need to use an assignment statement; just using the variable in an expression doesn't change the value of the variable:

>>> j = 8
>>> j + 5           # expression, not assignment
13
>>> print j
8


The while statement

  • Iteration, repetition, and looping all refer to the same thing: a way to execute one or more statements repeatedly
  • Iteration can be implemented with recursion (a function calling itself), but can also be done with the while statement; its syntax:
while exp:
    stmt ...
  • The Python interpreter understands this as:
    1. Evaluate the exp (a Boolean expression)
    2. If it is True, execute the statement(s) indented under the while; if False, execute the first statement after the statement(s) indented under the while
    3. Return flow of control to the while statement and ...
  • Here is the logic with a flowchart:

  • Here is an example:

>>> def blastoff(n):
        while n > 0:         # condition
            print n,
            n = n - 1        # decrement
        print "Blastoff!!!"

>>> blastoff(5)
5 4 3 2 1 Blastoff!!!

  • The function contains a while loop; the condition (n > 0) is evaluated, and, if True, the body of the loop is executed (the two statements indented under the while); when the body has been executed, control is returned to the while statement and the condition again evaluated; the loop continues until the condition evaluates to False
  • A loop that never ends is called an infinite loop and is usually the result of not modifying a loop control variable; in the above example, if the statement n = n - 1 is omitted, an infinite loop will result
  • Example of a loop to calculate the factorial without recursion: factorial_nr.py
  • A loop control variable must be:
    1. initialized: assigned a value before the while is executed
    2. tested: compared to the terminating value in the while condition
    3. updated: modified in the loop body, usually by incrementing or decrementing

Tables

  • One of the most useful things we can do with loop is to construct a table
  • This section shows how to produce a table to display the log2 of a series of numbers
  • Here is the code, written as a program: log2.py
  • Here is an program with a loop that generates the first 16 powers of 2: power2.py
  • And here is another that displays factorials: factorial_nr2.py

The break keyword

  • The break statement can be used to exit a loop
  • You can use break to construct a "loop-and-a-half"; there is the basic form:
while True:
   if condition that terminates loop is true:
      break
   statements in body of loop ...
  • See example program lh.py
    • This is an example of a program that uses a loop-and-a-half to accumulate values input from the keyboard
    • In the accumulator pattern, one variable is used as an accumulator (in this program, the variable total)
    • Accumulator variables should be:
      1. Initialized before the accumulation loop is entered (usually to 0)
      2. Updated inside the loop (by adding an input value to it)
      3. Used (or displayed) when the loop is exited and accumulation complete

Square roots

  • One of the many uses of loops is to compute numerical results by approximation
  • For example, if a is the number we want to compute the square root of, and x is an estimate of the square root, then a better estimate y can by calculated (using Newton's method) with this formula:

y = (x + (a / x)) / 2

  • If we now substitute the new, better estimate y for x, and use the formula again, we can obtain an even better estimate
  • If we do this repeatedly, inside a loop, we can get as close as we want to the true value of the square root; the time to stop is when y and x are so little different from each other that we are satisfied with our approximation.
  • See example program sqroot.py

Algorithms

  • Newton's method is an example of an algorithm:

An algorithm is a set of instructions for solving a problem or a class of problems by a mechanical, unintelligent process.

  • Some knowledge is not algorithmic; you learn (memorize) specific solutions to specific problems (what is the product of 7 and 6?)
  • Here is another algorithm; carry it out for the number 34567:

        1)  d = rightmost digit of number
        2)  answer = d
        3)  c = 0
            while d has a left neighbor:
        4)      add left neighbor to d
        5)      add c to d
                if d >= 10:
        6)          d = d - 10
        7)          c = 1
                else:
        8)          c = 0
        9)      write down d to left of answer
        10)     d = left neighbor
        11) add c to d
        12) write down d to left of answer
     
  • What did you just do? Did you solve a problem? What was it? The point is an algorithm is a set of instructions that can be carried out mechanically, without even an awareness of the problem being solved, and still arrive at the desired result
 Updated: 12.13.2010