Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Chapter 8

Repetition: While Loops

While loops allow programs to repeat without necessarily knowing ahead of time how many times the loop will run. Like selection, this allows programs to adapt and run more or less code, depending on the circumstances.

Consider the task of printing a table of prime numbers. An integer n is prime if it is greater than 1 and its only positive divisors are 1 and itself. This definition leads to the following program:

Listing 8.1: Prime Numbers

 1 # primes.py

 3 def isprime(n):

 4 # Return True if n is prime.

 5 return n > 1 and smallestdivisor(n) == n

 7 def smallestdivisor(n):

 8 # Find smallest divisor (other than 1) of integer n > 1.

 9 k = 2

10 while k < n and not divides(k, n):

11  k += 1

12 return k

14 def divides(k, n):

15  # Return True if k divides n.

16  return n % k == 0

18 def main():

19 for n in range(2, 100):

20  if isprime(n):

21    print(n, end=" ")

22 print()

24 main()

The definition of the isprime() function parallels the definition of prime number in a nice way and reads like pseudocode. In addition to the while loop, this program uses the modulus operator % and the end= option of print() for the first time.

While Loops

The syntax of a while loop is almost identical to that of an if statement.

while <boolean>:

 <body>

The <boolean> expression is evaluated, and if it is True, then <body> is executed. (So far, this is identical to an if statement.) After the body executes, <boolean> is evaluated again, and if it is still True, then the body executes again. This is repeated until the boolean expression is False.

Unlike a for loop, it is distinctly possible for a while loop to be infinite. Use CTRL-C or look for an option to restart your interpreter or shell if you execute an infinite loop.

Mod Operation

The modulo or mod operation finds the remainder when one integer is divided by another.

n % m

Remainder when n is divided by m.

So, for example, k divides n evenly if the remainder is 0; i.e., if n % k == 0.

Print Options

The Python print() function has two options that give you somewhat more control over output:

print(..., end=s)	Print with string s at end instead of newline.
print(..., sep=s)	Print with string s between expressions.

Both options may be set at the same time.

Tracing Code by Hand

You may have found it hard to follow exactly what is happening in Listing 8.1. One reason might be its use of several functions, another could be the while loop in smallestdivisor(). Tracing code by hand can help overcome both of these difficulties. When we trace code by hand, we try to simulate on paper what the interpreter is asking the CPU to do.

For example, we might trace the evaluation of isprime(9) like this:

isprime(9)

 → smallestdivisor(9)

  → divides(2, 9) returns  $F$  $F$

  → divides(3, 9) returns  $T$  $T$

 returns  $3$  $3$

returns  $F$  $F$

To follow the operation of smallestdivisor(), it may also be helpful to track the values of its variables, like this for the call smallestdivisor(25):

There is nothing special about these ways of writing the traces; the point is just to find a helpful way of simulating the program’s execution.

Nested Loops

Although it is not immediately obvious, Listing 8.1 runs its while loop inside of another loop—the for loop in main(). That means the entire while loop from smallestdivisor() runs once every time the body of the for loop runs.

Any time one loop is run inside of another loop, the loops are called nested. As you may imagine, nested loops can have a significant impact on program performance.

Exercises

8.1 Calculate these values by hand:
1. (a) 23 % 4
2. (b) 15 % 7
3. (c) 52 % 19
4. (d) 219 % 105
5. (e) 1738 % 3
6. (f) 418 % 2
7. (g) 5033 % 2
8. (h) 128 % 10
9. (i) 741 % 5
8.2 Trace the execution of each of these function calls:
1. (a) isprime(7)
2. (b) isprime(27)
3. (c) isprime(1024)
4. (d) smallestdivisor(100)
5. (e) smallestdivisor(81)
6. (f) smallestdivisor(49)
8.3 Write a function is_even(x) that returns the boolean value True if x is even; otherwise, it returns False.
8.4 Write a function is_odd(x) that returns the boolean value True if x is odd; otherwise, it returns False.
8.5 Determine the output of these two fragments of Python code. Which of the two has nested loops? How many print() statements are executed in each case?
1. (a)
```
for i in range(4):
```
```
   print(i)
```
```
 for j in range(3):
```
```
   print(j)
```
2. (b)
```
for i in range(4):
```
```
   print(i)
```
```
   for j in range(3):
```
```
   print(j)
```
8.6 Write an infinite loop.
8.7 Use Listing 8.1 to answer these questions:
1. (a) Explain the purpose and effect of the end=" " in line 21. What happens if it is omitted?
2. (b) Explain the purpose and effect of the print() statement in line 22. What happens if it is omitted?
3. (c) Determine the value of the function call smallestdivisor(1).
4. (d) Is there any way for the loop in smallestdivisor() to be infinite? Explain your answer.
5. (e) Discuss the tradeoffs in having divides() as a separate function.
8.8 Consider this variation of the divides() function from Listing 8.1:
```
def divides(k, n):
```
```
 if n % k == 0:
```
```
   return True
```
```
 else:
```
```
   return False
```
Discuss the tradeoffs between writing the function in this way compared with the original version.
8.9 Modify the smallestdivisor() function in Listing 8.1 to use a for loop instead of a while loop. Discuss the tradeoffs. Hint: a function may return at any time.
8.10 If an integer n is not prime, then at least one of its divisors must be less than or equal to $\sqrt{n}$ $\sqrt{n}$ . (Think about why.) Use this fact to improve the performance of the smallestdivisor() function in Listing 8.1.
8.11 Write a program change.py that asks the user for a number of cents and computes the number of dollars, quarters, dimes, nickels, and pennies needed to make that amount, using the largest denomination whenever possible. For example, 247 cents is 2 dollars, 1 quarter, 2 dimes, and 2 pennies. Use // when you intend to use integer division. You do not need to write any functions other than main().
8.12 Write a program guesser.py that guesses an integer chosen by the user between 1 and 100. After each guess, the user indicates if the guess was too high, too low, or correct. Your program should use as few guesses as possible. You do not need to write any functions other than main().
8.13 Modify guesser.py from Exercise 8.12 to add these features:
1. (a) Allow the user to play more than once.
2. (b) Report the total number of guesses taken after each round.
3. (c) Allow the user to specify the upper limit, instead of always using 100.
4. (d) Have your program sound confident by predicting the maximum number of guesses it will take. The log() and ceil() functions from the math module may be helpful.
8.14 Write a program savings.py that calculates the number of years it will take to reach a savings goal given a starting principal and interest rate. Write appropriate functions, ask the user for input, and display the result. Hint: use an accumulator rather than a formula.
8.15 Write the function intlog2(n) that returns the largest integer k such that 2k ≤ n. For example, intlog2(20) = 4 because 24 = 16 is the largest power of 2 less than or equal to 20, and intlog2(32) = 5 because 25 = 32 is the largest power of 2 less than or equal to 32. Write a main() to test your function. Do not use any library functions inside your intlog2().
8.16 Modify Listing 4.1 to ask the user for a number m and then compute the smallest n for which the harmonic sum $\sum_{k = 1}^{n} \frac{1}{k}$ $\sum_{k = 1}^{n} \frac{1}{k}$ is greater or equal to m. Be careful to test your program only with small m.
8.17 Write a function gcd(m, n) that calculates the GCD (greatest common divisor) of m and n, which is the largest positive k that divides both m and n. Use Euclid’s algorithm to calculate the gcd. Here is one (very succinct!) way to describe it:
```
 Replace m with n, and n with m % n until n is 0.
```
Once n becomes 0, the gcd is in m. Write a program gcd.py with a main() that uses nested loops to test your function thoroughly.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for Chapter 8 Repetition: While Loops

Create new playlist

Sign In