Lecture Notes

while exp: stmt ... 
 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:
 initialized: assigned a value before the while is executed
 tested: compared to the terminating value in the while condition
 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 log_{2} 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 "loopandahalf"; 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 loopandahalf 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:
 Initialized before the accumulation loop is entered (usually to 0)
 Updated inside the loop (by adding an input value to it)
 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 