Iteration
Introduced| English | Meaning |
|---|---|
| iteration/ˌɪtəˈreɪʃn/ | iteration |
| infinite loop/ˈɪnfɪnət luːp/ | A loop whose stopping condition is never met, so it runs forever. |
| trace table/treɪs ˈteɪbl/ | A table recording variable values and outputs as an algorithm's steps are followed. |
When will £1000 become £2000?
- You save £1000 at 5% interest a year. How many years until it passes £2000? You could multiply by 1.05 again and again by hand, but a computer does it in a blink.
- Doing the same step again and again is iteration 循环. This lesson is about writing loops that run the right number of times and then stop.
balance, years = 1000.0, 0
while balance < 2000.0:
balance *= 1.05
years += 1
print(years, round(balance, 2)) # 15 2078.93
for: a loop with a known count
for i in range(1, 6):runs its block once for each value:1, 2, 3, 4, 5. The end value6is not included.range(5)gives0, 1, 2, 3, 4;range(2, 11, 2)gives2, 4, 6, 8, 10. Aforloop can also walk through a string or a list:for ch in "banana":.
How many times does the block of for i in range(3, 8): run?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
i takes 3, 4, 5, 6, 7; the end value 8 is left out. range(a, b) runs $b - a = 8 - 3 = 5$ times.
Match each range to the values it gives.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
One number is the stop; two are start and stop; a third is the step, which can be negative. The stop value is never included.
The accumulator pattern
- To add things up, set a total to zero before the loop, add to it inside the loop and use it after the loop.
- Putting
total = 0inside the loop resets it every time round, so only the last value survives.
total = 0
for i in range(1, 6):
total += i
print(total) # 15
Watch the total build up
Step through each pass. i takes the next value from range(1, 6) and total grows by it, so after the fifth pass the total is 15.
After total = 0 and for p in [4, 8, 15]: total += p, what is total?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
The total goes $0 \to 4 \to 12 \to 27$, one step for each item in the list.
while: loop until a condition fails
while condition:repeats as long as the condition isTrue. Use it when you do not know the number of rounds in advance.- Every
whileloop needs three things: a start value, a condition, and a step that moves towards making the conditionFalse. Forget the step and you have an infinite loop 死循环.
What happens when this runs: n = 5, then while n > 0: print(n)?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The loop has a start and a condition but no step. Adding n -= 1 inside the loop makes it print 5, 4, 3, 2, 1 and stop.
Trace it by hand
- A trace table 跟踪表 records every variable after each round. It is how you predict a loop, and how you find where your idea of the loop and the real loop part company.
- Fill one row per round and check the condition at the end of each row. The loop stops at the first
False.
- Trace the factorial loop for
n = 5. - Start:
n = 5,factorial = 1. After each round: $(4, 5)$, $(3, 20)$, $(2, 60)$, $(1, 120)$. - Now
n > 1isFalse, so the loop ends and120is printed. Four rounds, becausenwent from 5 down to 1.
Trace it: x = 1, then while x < 50: x *= 3. What is x when the loop ends?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$x$ goes $1 \to 3 \to 9 \to 27 \to 81$. At 27 the condition is still true, so it runs once more; at 81 it is false.
break: stop when the job is done
breakleaves the loop at once. It suits a search: look at each item, and stop when you find the one you want.- Searching from 100 for the first multiple of 7 tests 100, 101, 102, 103 and 104, then stops at 105.
for n in range(100, 200):
if n % 7 == 0:
break
print(n) # 105
A loop tests for n in range(30, 60): and breaks at the first n with n % 8 == 0. What is n after the loop?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
30 and 31 are not multiples of 8; 32 is, so break stops the loop with n still equal to 32.
for or while?
- Use
forwhen the number of rounds is known, or when you visit every item in a collection. It cannot run for ever. - Use
whilewhen a condition decides: until the balance passes £2000, until the user types a valid number. The savings loop above stops after 15 years at £2078.93, not exactly on £2000.
Which task needs a while loop rather than a for loop?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Nobody knows how many wrong tries the user will make, so a condition must decide. The other three visit a known set of items.
Marks that slip away
- Off by one.
range(1, 5)stops at4. Count the rounds:range(a, b)runs $b - a$ times. - No step in a
while. If nothing inside the loop changes the condition, it never ends. - Accumulator in the wrong place.
total = 0goes before the loop;print(total)usually goes after it, not indented inside. - Changing the loop variable of a
for. Settingi = 10insidefor i in range(5):does not skip rounds; the next round setsiagain.
for i in range(1, 5): runs with i equal to 5 in its last round.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The last value is 4; the stop value is never reached. Write range(1, 6) to include 5.
You've got it
- Iteration repeats a block.
forsuits a known count or a collection;range(a, b)stops beforeb. - A
whileloop needs a start, a condition and a step towardsFalse; without the step it is an infinite loop. - Accumulate with a total set before the loop. Use
breakto stop a search early, and check any loop with a trace table.