Transcript Loops - Computing Science

Loops
Introduction to Computing
Science and Programming I
Loops


To this point you’ve learned how to write code
that executes from top to bottom as well as how
to use conditional (if) statements to select or
skip parts of the code.
Loop structures allow the programmer to have
sections of code executed multiple times. This
allows many programs that couldn’t be written
without loops as well as making many programs
that can be written without loops, more simple.
Algorithms With Loops

Before getting into how to write the loops
themselves, let’s look at some problems
that require loops.
Prime Number Algorithm

Here’s an algorithm we looked at previously to test whether a user
input number is prime.
set divisor to 2
write “Enter an integer greater than 2”
read userNumber
repeat while divisor2 < userNumber
if userNumber % divisor is equal to 0
write “The number is not prime, it is divisible by :”
write divisor
exit program
set divisor to divisor +1
write “The number is prime.”
Prime Number Algorithm

Notice that we have a section of the algorithm
we want to repeat
repeat while divisor2 < userNumber
if userNumber % divisor is equal to 0
write “The number is not prime, it is divisible by :”
write divisor
exit program
set divisor to divisor +1

The algorithm wants to repeat the indented
section of code while (divisor2 < userNumber)
Algorithms


A couple simpler algorithms that will need to repeat code.
Factorial



n! = n * (n-1) * (n-2) *…*2 * 1
5! = 5 * 4 * 3 * 2 * 1 = 120
Algorithm
write “Enter a nonnegative integer:”
read n
set factorial to 1
do this for i equal to each number from 1 to n:
set factorial to factorial * i
write factorial

Notice the code that will be repeated, but this time it is stated differently.
Instead of repeat while this is true, it says do this this many times.
A Couple More Algorithms

Repeatedly prompting a user until they give proper
input
set number to 0
repeat while number < 1
write “Enter a positive integer: “
read number

Printing out the powers of 2
write “How many powers of 2 should be printed?”
read max
set value to 1
do this max times
write value
set value to value * 2
Two Kinds of Loop

while loops


These are called indefinite loops because they
are often used to repeat code without
knowing how many times it will be repeated
beforehand.
for loops

These are called definite loops because they
usually will repeat a set number of times
while Loops
while condition:
code block

Similar to an if statement, a while loop is
given a condition (boolean expression).
The code block associated with the while
loop will repeat over and over again until
the condition becomes false.
while Loops

A simple example that prints the number 1
through 3.
num = 1
while num <= 3:
print num
num = num + 1
print “Finished”

When the while statement is reached the first time, num is 1 which
is less than five. Therefore execution enters the code block and
repeats the code block until num is greater than 5
while Loops

Unwinding the loop

To understand what’s going on we can ‘unwind’ the loop
num = 1
while num <= 3:
print num
num = num + 1
print “Finished”












num = 1
Check the condition, is num <=3?
print num
num = num + 1 (num is 2)
Check the condition, is num <= 3?
print num
num = num + 1 (num is 3)
Check the condition, is num <= 3?
print num
num = num + 1 (num is 4)
Check the condition, is num <= 3?
print “Finished”
Yes, so enter the code block
Yes, so repeat the code block
Yes, so repeat the code block
No, so skip the code block
while Loops



Remember that the condition is checked before
the block of code is executed for the first time.
Therefore, the code in a while loop may never
be executed.
You also need to make sure the condition
eventually becomes false, if not you will have an
infinite loop. The program will never leave the
while loop and never finish
while Loops

while loops are an easy way to wait
for proper input from the user
number = 0
while number < 1:
number = int(raw_input(“Enter a positive integer: “))
print “Your number is “ + str(number)
for Loops

For the time being all of the for loops we look at
will look something like this
for x in range(5):
print x

We’ll learn more general uses of it, but for now
the for statement will be of the form
for varname in range(..):

Here we just have the single statement ‘print x’
inside the loop, but you have any sized code
block you like
range Function


range is a Python function that returns a list of numbers
If you give range one argument, it returns a list of integers starting
at 0, ending at one less than the argument



You can also give range a beginning and ending number. The list
starts at the first argument and ends at one less than the second
argument.




range(4) = [0, 1, 2, 3]
range(10) = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
range(1,5) = [1, 2, 3, 4]
range(-2,2) = [-2, -1, 0, 1]
range(0,4) = range(4)
We will learn about the list data type and how to create our own
lists later
for Loops

What the for loop does is assign the
values returned by range to the variable
one by one and executes the code block
for each value
for x in range(5):
print x

x will be assigned the 5 values in range,
and those values will be printed
for Loops

Unwinding a for loop
for x in range(5):
print x












Remember, range(5) = {0,1,2,3,4}
x=0 (first value in range(5))
print x
x=1 (second value in range(5))
print x
x=2 (third value in range(5))
print x
x=3 (fourth value in range(5))
print x
x=4 (final value in range(5))
print x
No more values remain in range(5) so we are finished
for Loops


You can just use the structure to repeat code a certain number of
times, ignoring the value assigned to the variable in the for
statement
Printing out the powers of 2
max = int(raw_input("How many powers of 2 should be printed? "))
num = 1;
for i in range(max):
print num
num = num * 2

Notice that the values in range(max) will be assigned to i, but we
don’t use i inside the loop. We’re just using the structure to repeat
the code block max times.
for Loops

Unwinding a for loop

Assume a user entered 3 in the last example
num = 1
for i in range(max): //max previously set to 3
print num
num = num * 2











Remember, range(3) = {0,1,2}
i=0 (first value in range(3))
print num (num is 1)
num = num * 2 (num is 2)
i=1 (second value in range(3))
print num
num = num * 2 (num is 4)
i=2 (third and last value in range(3))
print num
num = num * 2 (num is 8)
No values remain in range(3) so the loop is complete
for Loops

Factorial Example
n = int( raw_input("Enter a nonnegative integer: ") )
factorial = 1
for i in range(n):
factorial = factorial * (i+1)
print factorial
for Loops


range(n) returns {0,1,2…,n}, but you may want
to use the integers starting at 1
Print the first 5 positive integers
for num in range(5):
print num+1


num is set to 0,1,2… but we offset it by one in
the for loop to get the numbers we desired
We could also have used range(1,6) in this case
for Loops

Extending that idea

Print the first 5 positive even numbers
for num in range(5):
print 2*(num+1)

Print the first 5 positive odd numbers
for num in range(5):
print 2*num + 1

Print the first 5 positive numbers squared
for num in range(5):
print num**2

Print the first 5 powers of 2
for num in range(5):
print 2**num
Nesting


The code block inside a loop (or if
structure) can contain loops (or if
structures) itself. This is called nesting
loops.
As you get into more complex programs
these nested structures become
commonplace
Nesting

Nested for loops to print a block of 0s
for row in range(4):
for col in range(5):
print 0,
print “”

Output
0
0
0
0

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
If you put a comma at the end of a print statement ‘print
0,’ it will not go to the next line after printing
Nesting

Another nested for loop example that prints out the
coordinates (row,col) of each location in a grid with (0,0)
being the upper left-hand corner..
for row in range(4):
for col in range(6):
print "(" +str(row) + "," + str(col) + ")",
print “”

Output:
(0,0)
(1,0)
(2,0)
(3,0)
(0,1)
(1,1)
(2,1)
(3,1)
(0,2)
(1,2)
(2,2)
(3,2)
(0,3)
(1,3)
(2,3)
(3,3)
(0,4)
(1,4)
(2,4)
(3,4)
(0,5)
(1,5)
(2,5)
(3,5)
Nesting

Another nested for loop example that prints out the
coordinates (row,col) of each location in a grid.
for row in range(4):
for col in range(6):
print "(" +str(row) + "," + str(col) + ")",
print “”

Remember that the inner for loop is run from start to
end every time the code block for the outer for loop is
run

Each time one of the values in range(4) is assigned to row, every
value in range(6) will be assigned to col
Nesting

Nested loops to find the average of different students
grades
count = 0
name = raw_input("Enter student's name, enter nothing to quit: ")
while name!= "":
count = count + 1
totalScore=0
for i in range(3):
totalScore=totalScore + int(raw_input("Assignment " + str(i+1) + " score: "))
print name + "'s average is " + str(round(totalScore/3.0)) + "."
name = raw_input("Enter student's name, enter nothing to quit: ")
print "You entered the grades of " + str(count) + " student(s)"
Deciding Which Control Structure
To Use


You have code that only needs to run in
certain situations
if statement

Absolute value
num = int(raw_input(“Enter number: “))
if num < 0:
num = -num
print “Absolute value is “ + str(num)
Deciding Which Control Structure
To Use


You have two chunks of code, one or the
other of which should run every time
if – else structure
num = int(raw_input(“Enter a number: “))
if (num % 2) == 0:
print “You entered an even number.”
else:
print “You entered an odd number.”
Deciding Which Control Structure
To Use


You have more than two chunks of code, with one and
only one of which that should run each time.
if-elif-else structure
temp = int(raw_input(“Enter the temperature: “))
if temp > 25:
print “It is hot today.”
elif temp > 15:
print “It is warm today.”
elif temp > 5:
print “It is cool today.”
else:
print “It is cold today.”
Deciding Which Control Structure
To Use


You have code that needs to be repeated
for or while loop


There are many cases where either type of
loop can be used, but there are general rules.
If you know how many times a loop is going
to repeat, usually a for loop is best.


You may only know the repetitions based on user
input or some other variable.
If you need to keep repeating something until
some process is finished/goal is met
In Class Exercise

Write a short program that reads some user entered
text, and outputs whether there is a repeated character
in the string. e.g. “aa”, “speed”, but not “banana”

if text is a variable containing a string



len(text) tells you how many characters it has
text[0] gives you the first character, text[1] the second and
text[len(text) – 1] the last
Write a short program that prints out an NxN
multiplication table where N is entered by the user

If
1
2
3
the
2
4
6
user entered 3 the table should be.
3
6
9
In Class Exercise

This could also be done with a while loop
#Find a repeated character
text = raw_input("Enter text: ")
found = False #will be set to true if we find a repeated character
for index in range(len(text)-1):
if text[index] == text[index+1]:
print "Repeated character found: "+text[index]
found = True
if not found:
print "No repeats found"
In Class Exercise
size = int(raw_input(“How many rows/colums? “))
for row in range(size):
for col in range(size):
print (row+1) * (col+1),
print



We need to use row+1 and col+1 since we want
to start at 0, not 1
Remember that the comma at the end of the
print statement prevents it from proceeding to
the next line
print without anything after ends the line
In Class Exercise

What does the code print out?
count = int(raw_input("Enter the max: "))
for row in range(count):
line = ""
for i in range(count-row-1):
line = line + " “
for i in range(row+1):
line = line + str(i+1)
for i in range(row):
line = line + str(row-i)
print line
In Class Exercise




The outer loop is pretty clearly printing out one line for
each iteration, the inner loops are adding text to that
line.
Take each inner loop individually
for i in range(count-row-1):
line = line + " “
Assume count is 5. For each value of row, this will add
count-row-1 spaces. row will be assigned the values
0,1,2…count – 1
Therefore, on the first line this adds count-1 spaces,
count-2 on the second, … , and none on the last
In Class Exercise



for i in range(row+1):
line = line + str(i+1)
For each value of row this will add the numbers
1,2,3…row+1 to the current line
for i in range(row):
line = line + str(row-i)
For each value of row this will add the numbers
row,row-1,row-2…,1 to the current line
Combining these two, the first line will get 1, the
second, 121, the third, 12321, and so on
In Class Exercise


Combining all of this, we see a pyramid of
numbers printed out
The first inner for loop adds the spaces at the
left, the second for loop adds the increasing
number, the last adds the decreasing numbers
1
121
12321
1234321
123454321