-
Notifications
You must be signed in to change notification settings - Fork 1.8k
/
Copy pathcfbook006.html
515 lines (515 loc) · 22.4 KB
/
cfbook006.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
"http://www.w3.org/TR/REC-html40/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="GENERATOR" content="hevea 1.07" />
<title>
Iteration
</title>
</head>
<body>
<a href="cfbook005.html"><img src="previous_motif.gif" alt="Previous" /></a>
<a href="index.html"><img src="contents_motif.gif" alt="Up" /></a>
<a href="cfbook007.html"><img src="next_motif.gif" alt="Next" /></a>
<hr />
<h1><font color="black"><a name="htoc59">Chapter 5</a> Iteration</font></h1>
<a name="@default288"></a>
<a name="toc56"></a>
<h2><font color="black"><a name="htoc60">5.1</a> Updating variables</font></h2>
<a name="update"></a>
<a name="@default289"></a>
<a name="@default290"></a>
<font color="black">A common pattern in assignment statements is an assignment statement
that updates a variable -
where the new value of the variable depends on the old.
</font><pre><font size="4" color="blue">
x = x+1
</font></pre><font color="black">This means "get the current value of <tt>x</tt>, add one, and then
update <tt>x</tt> with the new value."<br />
<br />
If you try to update a variable that doesn't exist, you get an
error, because Python evaluates the right side before it assigns
a value to <tt>x</tt>:
</font><pre><font size="4" color="blue">
>>> x = x+1
NameError: name 'x' is not defined
</font></pre><font color="black">Before you can update a variable, you have to <b>initialize</b>
it, usually with a simple assignment:</font><br />
<br />
<a name="@default291"></a>
<pre><font size="4" color="blue">
>>> x = 0
>>> x = x+1
</font></pre><font color="black">Updating a variable by adding 1 is called an <b>increment</b>;
subtracting 1 is called a <b>decrement</b>.</font><br />
<br />
<a name="@default292"></a>
<a name="@default293"></a><br />
<br />
<a name="toc57"></a>
<h2><font color="black"><a name="htoc61">5.2</a> The <tt>while</tt> statement</font></h2>
<a name="@default294"></a>
<a name="@default295"></a>
<a name="@default296"></a>
<a name="@default297"></a>
<font color="black">Computers are often used to automate repetitive tasks. Repeating
identical or similar tasks without making errors is something that
computers do well and people do poorly.
Because iteration is so common, Python provides several
language features to make it easier. <br />
<br />
One form of iteration in Python is the <tt>while</tt> statement. Here is
a simple program that counts down from five and then says "Blastoff!".
</font><pre><font size="4" color="blue">
n = 5
while n > 0:
print n
n = n-1
print 'Blastoff!'
</font></pre><font color="black">You can almost read the <tt>while</tt> statement as if it were English.
It means, "While <tt>n</tt> is greater than 0,
display the value of <tt>n</tt> and then reduce the value of
<tt>n</tt> by 1. When you get to 0, exit the while statement and
display the word <tt>Blastoff!</tt>"<br />
<br />
<a name="@default298"></a><br />
<br />
More formally, here is the flow of execution for a <tt>while</tt> statement:
</font><ol type="1"><li><font color="black">Evaluate the condition, yielding <tt>True</tt> or <tt>False</tt>.</font><br />
<br />
</li><li><font color="black">If the condition is false, exit the <tt>while</tt> statement
and continue execution at the next statement.</font><br />
<br />
</li><li><font color="black">If the condition is true, execute the
body and then go back to step 1.</font></li></ol>
<font color="black">This type of flow is called a <b>loop</b> because the third step
loops back around to the top. Each time we execute the body of
the loop, we call it an <b>iteration</b>. For the above loop, we
would say, "It had five iterations" which means that the body of
of the loop was executed five times.<br />
<br />
<a name="@default299"></a>
<a name="@default300"></a>
<a name="@default301"></a><br />
<br />
The body of the loop should change the value of one or more variables
so that eventually the condition becomes false and the loop
terminates.
We call the variable that changes each time the loop
executes and controls when the loop finishes the
<b>iteration variable</b>.
If there is no iteration variable, the loop will repeat forever,
resulting in an <b>infinite loop</b>. </font><br />
<br />
<a name="toc58"></a>
<h2><font color="black"><a name="htoc62">5.3</a> Infinite loops</font></h2>
<font color="black">An endless source of amusement for
programmers is the observation that the directions on shampoo,
"Lather, rinse, repeat," are an infinite loop because
there is no <b>iteration variable</b> telling you how many times
to execute the loop.<br />
<br />
<a name="@default302"></a>
<a name="@default303"></a><br />
<br />
In the case of <tt>countdown</tt>, we can prove that the loop
terminates because we know that the value of <tt>n</tt> is finite, and we
can see that the value of <tt>n</tt> gets smaller each time through the
loop, so eventually we have to get to 0. Other times a loop is obviously
infinite because it has no iteration variable at all.</font><br />
<br />
<a name="toc59"></a>
<h2><font color="black"><a name="htoc63">5.4</a> "Infinite loops" and <tt>break</tt></font></h2>
<a name="@default304"></a>
<a name="@default305"></a>
<font color="black">Sometimes you don't know it's time to end a loop until you get half
way through the body. In that case you can write an infinite loop on purpose
and then use the <tt>break</tt> statement to jump out of the loop.<br />
<br />
This loop is obviously an <b>infinite loop</b> because the logical
expression on the
<tt>while</tt> statement is simply the logical constant <tt>True</tt>:
</font><pre><font size="4" color="blue">
n = 10
while True:
print n,
n = n - 1
print 'Done!'
</font></pre><font color="black">If you make the mistake and run this code, you will learn quickly how
to stop a runaway Python process on your system or find where the power-off
button is on your computer.
This program will
run forever or until your battery runs out
because the logical expression at the top of the loop
is always true by virtue of the fact that the expression is the
constant value <tt>True</tt>.<br />
<br />
While this is a dysfunctional infinite loop, we can still use this pattern
to build useful loops as long as we carefully add code to the
body of the loop to explicitly exit the loop using <tt>break</tt>
when we have reached
the exit condition.<br />
<br />
For example, suppose you want to take input from the user until they
type <tt>done</tt>. You could write:
</font><pre><font size="4" color="blue">
while True:
line = raw_input('> ')
if line == 'done':
break
print line
print 'Done!'
</font></pre><font color="black">The loop condition is <tt>True</tt>, which is always true, so the
loop runs repeatedly until it hits the break statement.<br />
<br />
Each time through, it prompts the user with an angle bracket.
If the user types <tt>done</tt>, the <tt>break</tt> statement exits
the loop. Otherwise the program echoes whatever the user types
and goes back to the top of the loop. Here's a sample run:
</font><pre><font size="4" color="blue">
> hello there
hello there
> finished
finished
> done
Done!
</font></pre><font color="black">This way of writing <tt>while</tt> loops is common because you
can check the condition anywhere in the loop (not just at the
top) and you can express the stop condition affirmatively
("stop when this happens") rather than negatively ("keep going
until that happens.").</font><br />
<br />
<a name="toc60"></a>
<h2><font color="black"><a name="htoc64">5.5</a> Finishing iterations with <tt>continue</tt></font></h2>
<a name="@default306"></a>
<a name="@default307"></a>
<font color="black">Sometimes you are in an iteration of a loop and want to finish the
current iteration and immediately jump to the next iteration.
In that case you can use the <tt>continue</tt>
statement to skip to the next iteration without finishing the
body of the loop for the current iteration.<br />
<br />
Here is an example of a loop that copies its input until the user
types "done", but treats lines that start with the hash character
as lines not to be printed (kind of like Python comments).
</font><pre><font size="4" color="blue">
while True:
line = raw_input('> ')
if line[0] == '#' :
continue
if line == 'done':
break
print line
print 'Done!'
</font></pre><font color="black">Here is a sample run of this new program with <tt>continue</tt> added.
</font><pre><font size="4" color="blue">
> hello there
hello there
> # don't print this
> print this!
print this!
> done
Done!
</font></pre><font color="black">All the lines are printed except the one that starts with the hash
sign because when the <tt>continue</tt> is executed, it ends
the current iteration and jumps
back to the <tt>while</tt> statement to start the next iteration, thus
skipping the <tt>print</tt> statement.</font><br />
<br />
<a name="toc61"></a>
<h2><font color="black"><a name="htoc65">5.6</a> Definite loops using <tt>for</tt></font> </h2>
<a name="@default308"></a>
<a name="@default309"></a>
<font color="black">Sometimes we want to loop through a <b>set</b> of things such
as a list of words, the lines in a file or a list of numbers.
When we have a list of things to loop through, we can
construct a <em>definite</em> loop using a <tt>for</tt> statement.
We call the <tt>while</tt> statement an <em>indefinite</em> loop
because it simply loops until some condition becomes <tt>False</tt>
whereas the <tt>for</tt> loop is looping through a known
set of items so it runs through as many iterations as there
are items in the set.<br />
<br />
The syntax of a <tt>for</tt> loop is similar to the <tt>while</tt> loop
in that there is a <tt>for</tt> statement and a loop body:
</font><pre><font size="4" color="blue">
friends = ['Joseph', 'Glenn', 'Sally']
for friend in friends:
print 'Happy New Year:', friend
print 'Done!'
</font></pre><font color="black">In Python terms,
the variable <tt>friends</tt> is a list<sup><a name="text8" href="#note8">1</a></sup>
of three strings and the <tt>for</tt>
loop goes through the list and executes the body once
for each of the three strings in the list resulting in this output:
</font><pre><font size="4" color="blue">
Happy New Year: Joseph
Happy New Year: Glenn
Happy New Year: Sally
Done!
</font></pre>
<font color="black">Translating this <tt>for</tt> loop to English is not as direct as the
<tt>while</tt>, but if you think of friends as a <b>set</b>,
it goes like this: "Run the statements in the body of the
for loop once for each friend <em>in</em> the set named friends.".<br />
<br />
Looking at the <tt>for</tt> loop, <b>for</b> and <b>in</b> are reserved
Python keywords, and <tt>friend</tt> and <tt>friends</tt> are variables.<tt><br />
<br />
<b>for</b> friend <b>in</b> friends<b>:<br />
<code> </code>print</b> 'Happy New Year', friend </tt><br />
<br />
In particular, <tt>friend</tt> is the <b>iteration variable</b> for
the for loop. The variable <tt>friend</tt> changes for each iteration of
the loop and controls when the <tt>for</tt> loop completes. The
<b>iteration variable</b> steps successively through the
three strings stored in the <tt>friends</tt> variable.</font><br />
<br />
<a name="toc62"></a>
<h2><font color="black"><a name="htoc66">5.7</a> Loop patterns</font></h2>
<font color="black">Often we use a for or while loop to go through a list of items
or the contents of a file and we are looking for something such as
the largest or smallest value of the data we scan through.<br />
<br />
These loops are generally constructed by:
</font><ul><li><font color="black">Initializing one or more variables before the loop starts.</font><br />
<br />
</li><li><font color="black">Performing some computation on each item in the loop body,
possibly changing the variables in the body of the loop.</font><br />
<br />
</li><li><font color="black">Looking at the resulting variables when the loop completes.</font></li></ul>
<font color="black">We will use a list of numbers to demonstrate the concepts and construction
of these loop patterns. </font><br />
<br />
<h3><font color="black"><a name="htoc67">5.7.1</a> Counting and summing loops</font></h3>
<font color="black">For example, to count the number of items
in a list, we would write the following <tt>for</tt> loop:
</font><pre><font size="4" color="blue">
count = 0
for itervar in [3, 41, 12, 9, 74, 15]:
count = count + 1
print 'Count: ', count
</font></pre><font color="black">We set the variable <tt>count</tt> to zero before the loop starts,
then we write a <tt>for</tt> loop to run through the list of numbers.
Our <b>iteration</b> variable is named <tt>itervar</tt> and while we do
not use <tt>itervar</tt> in the loop, it does control the loop and cause
the loop body to be executed once for each of the values in the list.<br />
<br />
In the body of the loop, we add one to the current value of <tt>count</tt>
for each of the values in the list. While the loop is executing, the
value of <tt>count</tt> is the number of values we have seen "so far".<br />
<br />
Once the loop completes, the value of <tt>count</tt> is the total number
of items. The total number "falls in our lap" at the end of the
loop. We construct the loop so that we have what we want when the loop
finishes.<br />
<br />
Another similar loop that computes the total of a set of numbers
is as follows:
</font><pre><font size="4" color="blue">
total = 0
for itervar in [3, 41, 12, 9, 74, 15]:
total = total + itervar
print 'Total: ', total
</font></pre><font color="black">In this loop we <em>do</em> use the <b>iteration variable</b>.
Instead of simply adding one to the <tt>count</tt> as in the previous loop,
we add the actual number (3, 41, 12, etc.) to the running
total during each loop iteration.
If you think about the variable <tt>total</tt>, it contains the
"running total of the values so far". So before the loop
starts <tt>total</tt> is zero because we have not yet seen any values,
during the loop <tt>total</tt> is the running total, and at the end of
the loop <tt>total</tt> is the overall total of all the values
in the list.<br />
<br />
As the loop executes, <tt>total</tt> accumulates the sum of the
elements; a variable used this way is sometimes called an
<b>accumulator</b>.
<a name="@default310"></a><br />
<br />
Neither the counting loop nor the summing loop are particularly
useful in practice because there are built-in functions
<tt>len()</tt> and <tt>sum()</tt> that compute the number of
items in a list and the total of the items in the list
respectively.</font><br />
<br />
<h3><font color="black"><a name="htoc68">5.7.2</a> Maximum and minimum loops</font></h3>
<a name="@default311"></a>
<a name="@default312"></a>
<a name="@default313"></a>
<a name="@default314"></a>
<a name="maximumloop"></a><font color="black">
To find the largest value in a list or sequence, we construct the
following loop:
</font><pre><font size="4" color="blue">
largest = None
print 'Before:', largest
for itervar in [3, 41, 12, 9, 74, 15]:
if largest is None or itervar > largest :
largest = itervar
print 'Loop:', itervar, largest
print 'Largest:', largest
</font></pre><font color="black">When the program executes, the output is as follows:
</font><pre><font size="4" color="blue">
Before: None
Loop: 3 3
Loop: 41 41
Loop: 12 41
Loop: 9 41
Loop: 74 74
Loop: 15 74
Largest: 74
</font></pre><font color="black">The variable <tt>largest</tt> is best thought of as
the "largest value we have seen so far".
Before the loop, we set <tt>largest</tt> to the constant <tt>None</tt>.
<tt>None</tt> is a special constant value which we can
store in a variable to mark
the variable as "empty". <br />
<br />
Before the loop starts, the largest value we have seen so far
is <tt>None</tt> since we have not yet seen any values. While the
loop is executing, if <tt>largest</tt> is <tt>None</tt> then we take
the first value we see as the largest so far. You can see in
the first iteration when the value of <tt>itervar</tt> is 3,
since <tt>largest</tt> is <tt>None</tt>, we immediately set
<tt>largest</tt> to be 3.<br />
<br />
After the first iteration, <tt>largest</tt> is no longer <tt>None</tt>,
so the second part of the compound logical expression that checks
<tt>itervar > largest</tt> triggers only when we see a value that is
larger than the "largest so far". When we see a new "even larger"
value we take that new value for <tt>largest</tt>. You can see in the
program output that <tt>largest</tt> progresses from 3 to 41 to 74.<br />
<br />
At the end of the loop, we have scanned all of the values and
the variable <tt>largest</tt> now does contain the largest value
in the list.<br />
<br />
To compute the smallest number, the code is very similar with one
small change:
</font><pre><font size="4" color="blue">
smallest = None
print 'Before:', smallest
for itervar in [3, 41, 12, 9, 74, 15]:
if smallest is None or itervar < smallest:
smallest = itervar
print 'Loop:', itervar, smallest
print 'Smallest:', smallest
</font></pre><font color="black">Again, <tt>smallest</tt> is the "smallest so far" before, during, and after the
loop executes. When the loop has completed, <tt>smallest</tt> contains the
minimum value in the list.<br />
<br />
Again as in counting and summing, the built-in functions
<tt>max()</tt> and <tt>min()</tt> make writing these exact loops
unnecessary.<br />
<br />
The following is a simple version of the Python built-in
<tt>min()</tt> function:
</font><pre><font size="4" color="blue">
def min(values):
smallest = None
for value in values:
if smallest is None or value < smallest:
smallest = value
return smallest
</font></pre><font color="black">In the function version of the smallest code, we removed all of the
<tt>print</tt> statements so as to be equivalent to the <tt>min</tt>
function which is already built-in to Python.</font><br />
<br />
<a name="toc63"></a>
<h2><font color="black"><a name="htoc69">5.8</a> Debugging</font></h2>
<font color="black">As you start writing bigger programs, you might find yourself
spending more time debugging. More code means more chances to
make an error and more places for bugs to hide.<br />
<br />
<a name="@default315"></a>
<a name="@default316"></a><br />
<br />
One way to cut your debugging time is "debugging by bisection."
For example, if there are 100 lines in your program and you
check them one at a time, it would take 100 steps.<br />
<br />
Instead, try to break the problem in half. Look at the middle
of the program, or near it, for an intermediate value you
can check. Add a <tt>print</tt> statement (or something else
that has a verifiable effect) and run the program.<br />
<br />
If the mid-point check is incorrect, the problem must be in the
first half of the program. If it is correct, the problem is
in the second half.<br />
<br />
Every time you perform a check like this, you halve the number
of lines you have to search. After six steps (which is much
less than 100), you would be down to one or two lines of code,
at least in theory.<br />
<br />
In practice it is not always clear what
the "middle of the program" is and not always possible to
check it. It doesn't make sense to count lines and find the
exact midpoint. Instead, think about places
in the program where there might be errors and places where it
is easy to put a check. Then choose a spot where you
think the chances are about the same that the bug is before
or after the check.</font><br />
<br />
<a name="toc64"></a>
<h2><font color="black"><a name="htoc70">5.9</a> Glossary</font></h2>
<dl compact="compact"><dt><font color="black"><b>accumulator:</b></font></dt><dd><font color="black"> A variable used in a loop to add up or
accumulate a result.
</font><a name="@default317"></a><br />
<br />
</dd><dt><font color="black"><b>counter:</b></font></dt><dd><font color="black"> A variable used in a loop to count the number
of times something happened. We initialize a counter to
zero and then increment the counter each time we want to
"count" something.
</font><a name="@default318"></a><br />
<br />
</dd><dt><font color="black"><b>decrement:</b></font></dt><dd><font color="black"> An update that decreases the value of a variable.
</font><a name="@default319"></a><br />
<br />
</dd><dt><font color="black"><b>initialize:</b></font></dt><dd><font color="black"> An assignment that gives an initial value to
a variable that will be updated.</font><br />
<br />
</dd><dt><font color="black"><b>increment:</b></font></dt><dd><font color="black"> An update that increases the value of a variable
(often by one).
</font><a name="@default320"></a><br />
<br />
</dd><dt><font color="black"><b>infinite loop:</b></font></dt><dd><font color="black"> A loop in which the terminating condition is
never satisfied or for which there is no termination condition.
</font><a name="@default321"></a><br />
<br />
</dd><dt><font color="black"><b>iteration:</b></font></dt><dd><font color="black"> Repeated execution of a set of statements using
either a recursive function call or a loop.
</font><a name="@default322"></a></dd></dl>
<a name="toc65"></a>
<h2><font color="black"><a name="htoc71">5.10</a> Exercises</font></h2><br />
<div align="left"><font color="black"><b>Exercise 1</b> <em>
Write a program which repeatedly reads numbers until the user
enters "done".
Once "done" is entered, print out the total, count, and average
of the numbers. If the user enters anything other than a number,
detect their mistake using <tt>try</tt> and <tt>except</tt> and
print an error message and skip to the next number.
</em></font><pre><font color="black"><em>
Enter a number: 4
Enter a number: 5
Enter a number: bad data
Invalid input
Enter a number: 7
Enter a number: done
16 3 5.33333333333
</em></font></pre></div><br />
<div align="left"><font color="black"><b>Exercise 2</b> <em>
Write another program that prompts for a list of numbers as above
and at the end prints out both the maximum and minimum of the numbers instead of the average.
</em></font></div><br />
<hr width="50%" size="1" /><dl><dt><font size="5" color="black"><a name="note8" href="#text8">1</a></font></dt><dd><font color="black">We will
examine lists in more detail in a later chapter
</font></dd></dl>
<hr />
<a href="cfbook005.html"><img src="previous_motif.gif" alt="Previous" /></a>
<a href="index.html"><img src="contents_motif.gif" alt="Up" /></a>
<a href="cfbook007.html"><img src="next_motif.gif" alt="Next" /></a>
</body>
</html>