CPSC120B - Day 18 Notes

Cool Computer Science Thing of the Day

A Friend For Pluto

No Reading Questions

No Quiz

Review

Find the largest common divisor, by test each number, record largest in variable and return

def gcd(a, b):
    for i in range(b, 0, -1):
        if a % i == 0 and b % i == 0:
            result = i
    return result

print(gcd(3, 5))
print(gcd(3, 9))

This works if the gcd is 1, but not when it is larger
It always returns 1, because it is actually finding the least common divisor because the loop doesn’t stop.

solve this by changing the loop direction

def gcd(a, b):
    for i in range(1, b + 1):
        if a % i == 0 and b % i == 0:
            result = i
    return result

print(gcd(3, 5))
print(gcd(9, 12))

While Loop

Another name is conditional loop, a loop that runs while a condition is true
```
i = 0
while i < 10:
    print(i)
    i = i + 1
```
Loop will run while x is less than 10

What happens if we get the condition wrong?

i = 0
while i > 10:
    print(i)
    i = i + 1

The loop won’t run because 0 is not greater than 10

What if we get the change in x wrong?

i = 0
while i < 10:
    print(i)
    i = i - 1

Inifinte loop, C-c C-z to kill in emacs
Any for loop can be written as a while loop
The above loop as a for loop is
```
for i in range(10):
    print(i)
```
Which is much more concise with fewer opportunities for errors
So why use a while loop?
Because not all while loops can be written as a for loop
For loops are for when you know the number of times the loop will run
Sometimes you have inputs, user or function parameters that will make predicting the number of iteration impossible
```
user_input = input('> ')
while user_input != 'bye':
    print(user_input)
    user_input = input('> ')
```
Note, there are two prompts because we need user for the first while test

Could get around this by reordering the loop body

user_input = ''
while user_input != 'bye':
    user_input = input('> ')
    print(user_input)

It’s also worth emphasizing that the loop condition is true if it should continue to run
But when writing loops you often think in terms of when you want the loop to stop
In that case, just negate the stopping condition
Want to stop when user_input == 'bye', so the stopping condition is user_input != 'bye'
While loops can also be useful for making more efficient code
The gcd program wastes computation by checking all numbers to see if they are a common divisor

A faster algorithm starts at the largest and stops at the first it finds

def gcd(a, b):
    i = b
    while a % i != 0 or b % i != 0:
        i = i - 1
    return i

An even better algorithm, also starts at the smaller input

def gcd(a, b):
    if a < b:
        i = a
    else:
        i = b
    while a % i != 0 or b % i != 0:
        i = i - 1
    return i

Lab

lab18