CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Loops
Learning Goal: use loops to repeat actions and direct program flow. In particular:
- Use for loops to repeat actions a specified number of times
- Use while loops to repeat actions until a condition is met
- Predict
- for loops and range
- Check 2.1
- Check 2.2
- nested for loops
- Check 2.3
- while loops
- Check 2.4
- break and continue
- isPrime
- nthPrime
- Predict
Predict the output of the following code snippet and write your guess in the editor.for i in range(5): print(i)import sys def set_certificate(certificate_div_id, certificate): document[certificate_div_id].textContent = certificate def get_student_code(student_code_div_id): raw_student_code = document[student_code_div_id].textContent return window.patchCodeToCheckTimeout(raw_student_code, 'check_timeout();'); def make_certificate(student_code_div_id, certificate_div_id): student_code = get_student_code(student_code_div_id) certificate = [] output = "failure" if student_code != "": output = "success" certificate.append((output, type(output))) set_certificate(certificate_div_id, str(certificate))
Compare
Now run the code and see if you were right!for i in range(5): print(i) - for loops and range
# A for loop repeats an action a specific number of times # based on the provided range def sumFromMToN(m, n): total = 0 # note that range(x, y) includes x but excludes y for x in range(m, n+1): total += x return total print(sumFromMToN(5, 10) == 5+6+7+8+9+10)
Actually, we don't need a loop here...def sumFromMToN(m, n): return sum(range(m, n+1)) print(sumFromMToN(5, 10) == 5+6+7+8+9+10) # And we can even do this with a closed-form formula, # which is the fastest way, but which doesn't really # help us demonstrate loops. :-) def sumToN(n): # helper function return n*(n+1)//2 def sumFromMToN_byFormula(m, n): return (sumToN(n) - sumToN(m-1)) print(sumFromMToN_byFormula(5, 10) == 5+6+7+8+9+10)
What if we omit the first parameter?def sumToN(n): total = 0 # range defaults the starting number to 0 for x in range(n+1): total += x return total print(sumToN(5) == 0+1+2+3+4+5)
What if we add a third parameter?def sumEveryKthFromMToN(m, n, k): total = 0 # the third parameter becomes a step for x in range(m, n+1, k): total += x return total print(sumEveryKthFromMToN(5, 20, 7) == (5 + 12 + 19))
Sum just odd numbers from m to n:# We can also change the step by changing the inside of the loop def sumOfOddsFromMToN(m, n): total = 0 for x in range(m, n+1): if (x % 2 == 1): total += x return total print(sumOfOddsFromMToN(4, 10) == sumOfOddsFromMToN(5,9) == (5+7+9))
Now do it backwards!# Here we will range in reverse # (not wise in this case, but instructional) def sumOfOddsFromMToN(m, n): total = 0 for x in range(n, m-1, -1): if (x % 2 == 1): total += x return total print(sumOfOddsFromMToN(4, 10) == sumOfOddsFromMToN(5,9) == (5+7+9)) - Check 2.1
- Check 2.2
- Nested for loops
# We can put loops inside of loops to repeat actions at multiple levels # This prints the coordinates def printCoordinates(xMax, yMax): for x in range(xMax+1): for y in range(yMax+1): print("(", x, ",", y, ") ", end="") print() printCoordinates(4, 5)
How about some stars?def printStarRectangle(n): # print an nxn rectangle of asterisks for row in range(n): for col in range(n): print("*", end="") print() printStarRectangle(5)
And again:# What would this do? Be careful and be precise! def printMysteryStarShape(n): for row in range(n): print(row, end=" ") for col in range(row): print("*", end=" ") print() printMysteryStarShape(5) - Check 2.3
- while loops
# use while loops when there is an indeterminate number of iterations def leftmostDigit(n): n = abs(n) while (n >= 10): n = n//10 return n print(leftmostDigit(72658489290098) == 7)
Example: nth positive integer with some property# eg: find the nth number that is a multiple of either 4 or 7 def isMultipleOf4or7(x): return ((x % 4) == 0) or ((x % 7) == 0) def nthMultipleOf4or7(n): found = 0 guess = -1 while (found <= n): guess += 1 if (isMultipleOf4or7(guess)): found += 1 return guess print("Multiples of 4 or 7: ", end="") for n in range(15): print(nthMultipleOf4or7(n), end=" ") print()
Misuse: While loop over a fixed range# sum numbers from 1 to 10 # note: this works, but you should not use "while" here. # instead, do this with "for" (once you know how) def sumToN(n): # note: even though this works, it is bad style. # You should do this with a "for" loop, not a "while" loop. total = 0 counter = 1 while (counter <= n): total += counter counter += 1 return total print(sumToN(5) == 1+2+3+4+5) - break and continue
# continue, break, and pass are three keywords used in loops # in order to change the program flow for n in range(200): if (n % 3 == 0): continue # skips rest of this pass elif (n == 8): break # skips rest of entire loop else: pass # does nothing! pass is a placeholder, not needed here print(n, end=" ") print()
Infinite "while" loop with break:# Note- this is advanced content, as it uses strings. It's okay # to not fully understand the content below. def readUntilDone(): linesEntered = 0 while (True): response = input("Enter a string (or 'done' to quit): ") if (response == "done"): break print(" You entered: ", response) linesEntered += 1 print("Bye!") return linesEntered linesEntered = readUntilDone() print("You entered", linesEntered, "lines (not counting 'done').") - Check 2.4
- isPrime
# Note: there are faster/better ways. We're just going for clarity and simplicity here. def isPrime(n): if (n < 2): return False for factor in range(2,n): if (n % factor == 0): return False return True # And take it for a spin for n in range(100): if isPrime(n): print(n, end=" ") print()
fasterIsPrime:# Note: this is still not the fastest way, but it's a nice improvement. def fasterIsPrime(n): if (n < 2): return False if (n == 2): return True if (n % 2 == 0): return False maxFactor = round(n**0.5) for factor in range(3,maxFactor+1,2): if (n % factor == 0): return False return True # And try out this version: for n in range(100): if fasterIsPrime(n): print(n, end=" ") print()
Verify fasterIsPrime is faster:def isPrime(n): if (n < 2): return False for factor in range(2,n): if (n % factor == 0): return False return True def fasterIsPrime(n): if (n < 2): return False if (n == 2): return True if (n % 2 == 0): return False maxFactor = round(n**0.5) for factor in range(3,maxFactor+1,2): if (n % factor == 0): return False return True # Verify these are the same for n in range(100): assert(isPrime(n) == fasterIsPrime(n)) print("They seem to work the same!") # Now let's see if we really sped things up import time bigPrime = 499 # Try 1010809, or 10101023, or 102030407 print("Timing isPrime(",bigPrime,")", end=" ") time0 = time.time() print(", returns ", isPrime(bigPrime), end=" ") time1 = time.time() print(", time = ",(time1-time0)*1000,"ms") print("Timing fasterIsPrime(",bigPrime,")", end=" ") time0 = time.time() print(", returns ", fasterIsPrime(bigPrime), end=" ") time1 = time.time() print(", time = ",(time1-time0)*1000,"ms")
- nthPrime
def isPrime(n): if (n < 2): return False if (n == 2): return True if (n % 2 == 0): return False maxFactor = round(n**0.5) for factor in range(3,maxFactor+1,2): if (n % factor == 0): return False return True # Adapt the "nth" pattern we used above in nthMultipleOf4or7() def nthPrime(n): found = 0 guess = 0 while (found <= n): guess += 1 if (isPrime(guess)): found += 1 return guess # and let's see a list of the primes for n in range(10): print(n, nthPrime(n)) print("Done!") - nthPrime