FIT1045: Algorithms and Programming Fundamentals in Python Lecture 2
Control Flow
COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
WARNING
This material has been reproduced and communicated to you by or on behalf of Monash University pursuant to Part VB of the Copyright Act 1968 (the Act).The material in this communication may be subject to copyright under the Act.Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act.
Do not remove this notice.
https://xkcd.com/518/
Reminder
Live stream chat is for asking question to lecturer/moderator
Workshops assessment
• You must complete workshop sheet for Week 1 and
submit online by midnight of Wednesday.
• Make sure to save your work (e.g., Google Drive, Git, USB,
laptop)
Tutorial preparation
• You must attempt the tutorial preparation question on
your Week 2 tutorial sheet by midnight of Monday.
Recap
>>> x = 1
>>> y = 1.0
>>> z = ‘1’
>>> username = ‘Rebecca’ >>> ‘Hello ‘ + username ‘Hello Rebecca’
>>> some_ones = max(abs(x – 100), round(0.001)) * z
>>> some_ones
‘111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111’
>>> from math import exp
>>> important_number = exp(x) >>> important_number 2.718281828459045
Recap
>>> help(exp)
Help on built-in function exp in module math:
exp(x, /)
Return e raised to the power of x.
(END)
Quiz time
5
Objectives of this lecture
Python
• custom functions and modules
• Boolean expressions (True/False) • conditional and loopy control flow
Algorithms
• greatest common divisor problem • Euclid’s algorithm
Covered learning outcomes
• 1, translate between problem descriptions and program
• 2, choose and implement appropriate problem solving strategies • 4, decompose problems into simpler problems
• 5, understand limitations of algorithms
Where am I?
1. Custom modules and functions
2. Boolean expressions
3. Conditionals
4. Greatest common divisor
5. While-loops
6. Euclid’s Algorithm
Goal: use Python for grocery price calculation
Our rules for price calculation
• our target sales prices should incorporate a 10% profit margin
• products close to best-before-date should be discounted
30% reduction rate if within 3 days 60% reduction rate if within 1 day
• sales prices has to incorporate goods and service tax (GST)
Let’s focus first on GST
>>> gst_rate = 0.1
>>> gross_price = 35
>>> gst = gross_price * gst_rate >>> price = gross_price + gst >>> price
38.5
>>>
To be useful we want reusable function
>>> from prices import price_after_gst >>> price_after_gst(35)
38.5
>>> price_after_gst(140)
154.0
>>>
… but we can build it ourselves!!!
Too bad Python doesn’t come with module ’prices’
L
Start by creating module file Let’s put what we have into file: prices.py
gst_rate = 0.1
gross_price = 35
gst = gross_price * gst_rate
price = gross_price + gst
Next, run Python from same folder
Python 3.7.6 (default, Dec 30 2019, 19:38:28)
[Clang 11.0.0 (clang-1100.0.33.16)] on darwin
Type “help”, “copyright”, “credits” or “license” for more information.
>>> import prices
>>> prices.gst_rate
0.1
>>>
Now turn specific computation into our own reusable function
gst_rate = 0.1
gross_price = 135
gst = gross_price * gst_rate
price = gross_price + gst
define this as our function
price_after_gst
Step 1: function head
keyword for function definition
gst_rate = 0.1
function name
def price_after_gst():
gross_price = 135
gst = gross_price * gst_rate
price = gross_price + gst
colon indicating that following lines contain definition
Step 2: function body
gst_rate = 0.1
def price_after_gst():
gross_price = 135
gst = gross_price * gst_rate
price = gross_price + gst
indentation
determines lines of function definition
Must be the same for all lines in block
Python coding standard: always use 4 spaces
Step 3: declare input
gst_rate = 0.1
def price_after_gst(gross_price):
gst = gross_price * gst_rate
price = gross_price + gst
input parameter list in parentheses
available as
local variable (name) in function body
Step 4: declare output
gst_rate = 0.1
def price_after_gst(gross_price):
gst = gross_price * gst_rate
price = gross_price + gst
return price
return keyword followed by result expression
Start function with a string to document it
gst_rate = 0.1
def price_after_gst(gross_price):
“””
Input : gross price of product
Output: sales price of product (incorporating GST)
“””
gst = gross_price * gst_rate
price = gross_price + gst
return price
this is called a “docstring”
Good practice:
write a docstring before starting to work on function body (clarify what exactly function is supposed to do)
To work with updated module we have to reload it or whole shell
def price_after_gst(gross_price):
“””
Input : gross price of product
Output: sales price of product (incorporating GST)
“””
gst = gross_price * gst_rate
price = gross_price + gst
return price
Python 3.7.6 (default, Dec 30 2019, 19:38:28)
[Clang 11.0.0 (clang-1100.0.33.16)] on darwin
Type “help”, “copyright”, “credits” or “license” for more information.
>>> from importlib import reload
>>> reload(prices)
>>> from prices import price_after_gst
>>>
Our function documentation shows up in help page
def price_after_gst(gross_price):
“””
Input : gross price of product
Output: sales price of product (incorporating GST)
“””
gst = gross_price * gst_rate
price = gross_price + gst
return price
Python 3.7.6 (default, Dec 30 2019, 19:38:28)
[Clang 11.0.0 (clang-1100.0.33.16)] on darwin
Type “help”, “copyright”, “credits” or “license” for more information.
>>> from importlib import reload
>>> reload(prices)
>>> from prices import price_after_gst
>>> help(price_after_gst)
Help on function price_after_gst in module gst:
price_after_gst(gross_price)
Input : gross price of product
Output: sales price of product (incorporating GST)
We’ve done it!!!
gst_rate = 0.1
def price_after_gst(gross_price):
gst = gross_price * gst_rate
price = gross_price + gst
return price
Python 3.7.6 (default, Dec 30 2019, 19:38:28)
[Clang 11.0.0 (clang-1100.0.33.16)] on darwin
Type “help”, “copyright”, “credits” or “license” for more information.
>>> from importlib import reload
>>> reload(gst)
>>> from gst import customer_price
>>> price_after_gst(35)
38.5
>>> price_after_gst(140)
154
…or have we?
So customer price function has to be modified…
cake
cookies
chair
taxable
bread
peach
tea
GS T -free
>>> price_after_gst(5, ‘cookies’) 5.05
>>> price_after_gst(5, ‘bread’) 5
>>>
Now we need conditional behaviour
input
gross_price
gst = gross_price * gst_rate
price = gross_price + gst
output price
False
gst = gross_price * gst_rate
input
gross_price, product
product is True GST-free
gst = 0
a new kind of thing: truth values
output
gross_price + gst
Where am I?
1. Custom modules and functions
2. Boolean expressions
3. Conditionals
4. Greatest common divisor
5. While-loops
6. Euclid’s Algorithm
Logic: Reasoning about the Truth
For every thing in the world, it is either a potato, or not a potato.
• True • False
https: //flux. qa
Boolean values
George Boole 1815-64, England
>>> True
True
>>> False
False
>>> type(True)
>>> type(False)
True and False are of type bool
Comparison operators yield Boolean results
Operator
Description
==
Equal
!=
Not equal
George Boole 1815-64, England
>>> ‘potato’ == ‘potato’ True
>>> ‘icecream’ == ‘potato’ False
>>> ‘icecream’ != ‘potato’ True
>>> 1 == 1.0
True
note difference to assignment statement
numeric objects of different type can be equal
Don’t confuse equals operator with assignment statement
Operator
Description
==
Equal
!=
Not equal
George Boole 1815-64, England
>>> thing = ‘potato’ >>> thing
‘potato’
>>> thing == ‘icecream’ False
>>> thing = ‘icecream’ >>> thing
‘icecream’
>>>
very different outcomes
More operators for ordered comparison
Operator
Description
==
Equal
!=
Not equal
<
Less than
>
Greater than
<=
Less than or equal
>=
Greater than or equal
George Boole 1815-64, England
>>> 5 < 7 True
>>> 5 > 7 False
>>> -1 >= -1.1 True
>>>
again works across numeric types as expected
More operators for ordered comparison
Operator
Description
==
Equal
!=
Not equal
<
Less than
>
Greater than
<=
Less than or equal
>=
Greater than or equal
George Boole 1815-64, England
>>> ‘williams’ < 'wilson' True
>>> ‘byron’ < 'abrams' False
>>> [1, 2, 3] < [1, 2, 4] True
for strings and other sequence types comparison uses lexicographic order
More operators for ordered comparison
Operator
Description
==
Equal
!=
Not equal
<
Less than
>
Greater than
<=
Less than or equal
>=
Greater than or equal
https://docs.python.org/3/library/stdtypes.html#comparisons
George Boole 1815-64, England
>>> ‘williams’ < 'wilson' True
>>> ‘byron’ < 'abrams' False
Only defined objects that are comparable (ordered)
>>> [1, 2, 3] < [1, 2, 4]
True
>>> 10 > ‘byron’
TypeError: ‘>’ not supported between instances of ‘int’ and ‘str’
Membership test operator for sequences
Operator
Description
e in x
True if e is a member of x (e is contained in x); False otherwise
e not in x
False if e is a member of x (e is contained in x); True otherwise
George Boole 1815-64, England
>>> ‘l’ in ‘williams’ True
>>> ‘l’ in ‘byron’ False
>>> 2 in [1, 2, 4] True
>>>
Membership test operator for sequences
Operator
Description
e in x
True if e is a member of x (e is contained in x); False otherwise
e not in x
False if e is a member of x (e is contained in x); True otherwise
George Boole 1815-64, England
>>> ‘l’ in ‘williams’ True
>>> ‘l’ in ‘byron’ False
Strings define containment as “is sub-string”
>>> 2 in [1, 2, 4]
True
>>> “FIT1045” in “I’m studying FIT1045 at Monash” True
>>> [1, 2] in [1, 2, 4]
False
Lists define containment strictly as “is element of”
Boolean operators for logical expressions
Operator
Description (simplified)
x or y
True if either x or y are True; otherwise False
x and y
True if both x and y are True; otherwise False
not x
True if x is False; otherwise False
George Boole 1815-64, England
>>> True and False False
>>> True or False True
>>> not True
False
>>> value = 10
>>> 1 <= value and value <= 100 True
>>>
Boolean operators for logical expressions
Operator
Description (simplified)
x or y
True if either x or y are True; otherwise False
x and y
True if both x and y are True; otherwise False
not x
True if x is False; otherwise False
George Boole 1815-64, England
>>> def is_potato_or_not_potato(thing):
… return thing == ‘potato’ or thing != ‘potato’ …
>>> is_potato_or_not_potato(‘potato’)
True
>>> is_potato_or_not_potato(‘icecream’)
True
>>> is_potato_or_not_potato(47)
True
Boolean operators: Precedence
Operation
Description
Precedence
x or y
if x is false, then y, else x
Lowest
x and y
if x is false, then x, else y
Medium
not x
if x is false, then True, else False
Highest
Note: all comparison operators have same precedence as not https://docs.python.org/3/library/stdtypes.html#boolean-operations-and-or-not
not (False and True) or not True and True
(not (False and True)) or ((not True) and True)
https: //flux. qa
Where am I?
1. Custom modules and functions
2. Boolean expressions
3. Conditionals
4. Greatest common divisor
5. While-loops
6. Euclid’s Algorithm
Back to our GST problem…
So customer price function has to be modified…
cake
cookies
chair
taxable
bread
peach
tea
GS T -free
>>> price_after_gst(5, ‘cookies’) 5.05
>>> price_after_gst(5, ‘bread’) 5
>>>
Change from linear to conditional flow
input
gross_price
gst = gross_price * gst_rate
output
gross_price + gst
False
gst = gross_price * gst_rate
input
gross_price, product
product is True GST-free
gst = 0
output
gross_price + gst
def price_after_gst(gross_price):
gst = gross_price * gst_rate
return gross_price + gst
Extend function parameter list
input
gross_price
gst = gross_price * gst_rate
output
gross_price + gst
False
gst = gross_price * gst_rate
input
gross_price, product
product is True GST-free
output
gross_price + gst
gst = 0
def price_after_gst(gross_price, product):
gst = gross_price * gst_rate
return gross_price + gst
Declare what are GST free product
input
gross_price
gst = gross_price * gst_rate
output
gross_price + gst
False
gst = gross_price * gst_rate
input
gross_price, product
product is True GST-free
gst = 0
output
gross_price + gst
gst_free_products = [‘bread’, ‘peach’, ‘tea’]
def price_after_gst(gross_price, product):
gst = gross_price * gst_rate
return gross_price + gst
Use if-statement for conditional flow
input
gross_price
gst = gross_price * gst_rate
output
gross_price + gst
keyword
input
gross_price, product
product is True GST-free
False
gst = gross_price * gst_rate
gst = 0
output
gross_price + gst
gst_free_products = [‘bread’, ‘peach’, ‘tea’]
def price_after_gst(gross_price, product):
if product in gst_free_products:
gst = 0
gst = gross_price * gst_rate
return gross_price + gst
Boolean expression
indentation determines conditional code block
Use else-block for alternative behaviour
input
gross_price
gst = gross_price * gst_rate
output
gross_price + gst
False
gst = gross_price * gst_rate
keyword
input
gross_price, product
product is True GST-free
gst = 0
output
gross_price + gst
gst_free_products = [‘bread’, ‘peach’, ‘tea’]
def price_after_gst(gross_price, product):
if product in gst_free_products:
gst = 0 else:
gst = gross_price * gst_rate
return gross_price + gst
Use else-block for alternative behaviour
>>> reload(prices)
>>> price_after_gst(5, ‘cookies’)
5.05
>>> price_after_gst(10, ‘icecream’)
10.10
>>> price_after_gst(5, ‘bread’)
5
>>>
gst_free_products = [‘bread’, ‘peach’, ‘tea’]
def price_after_gst(gross_price, product):
if product in gst_free_products:
gst = 0 else:
gst = gross_price * gst_rate
return gross_price + gst
Can now use GST function in solution for overall problem
Our rules for price calculation
• our target sales prices should incorporate a 10% profit margin
• products close to best-before-date should be discounted
30% reduction rate if within 3 days 60% reduction rate if within 1 day
• sales prices has to incorporate goods and service tax (GST)
Can now use GST function in solution for overall problem
input
purch_price, product, bb_days
base_price = purch_price + purch_price * 0.1
bb_days <= 1
True
reduction = base_price * 0.6
False
bb_days <=4
True
reduction = base_price * 0.3
False
reduction = 0
gross_price = base_price - reduction
output
price_after_gst(gross_price, product)
Now we need 3-way conditional
base_price = purch_price + purch_price * 0.1
multi-way conditional flow
gross_price = base_price - reduction
bb_days <= 1
True
reduction = base_price * 0.6
False
bb_days <=4
True
reduction = base_price * 0.3
False
reduction = 0
def customer_price(purch_price, product, best_before_days):
base_price = purch_price + purch_price*0.1
reduction = base_price*0.6
reduction = base_price*0.3
reduction = 0
gross_price = base_price - reduction
return round(price_after_gst(gross_price, product), 2)
Use elif for more alternatives base_price =
False
purch_price + purch_price * 0.1
bb_days <= 1
True
reduction = base_price * 0.6
bb_days <=4
True
reduction = base_price * 0.3
False
reduction = 0
gross_price = base_price - reduction
def customer_price(purch_price, product, best_before_days):
base_price = purch_price + purch_price*0.1
if best_before_days <= 1:
reduction = base_price*0.6 elif best_before_days <= 4:
reduction = base_price*0.3
else:
reduction = 0
gross_price = base_price - reduction
return round(price_after_gst(gross_price, product), 2)
Pause
Where am I?
1. Custom modules and functions
2. Boolean expressions
3. Conditionals
4. Greatest common divisor
5. While-loops
6. Euclid's Algorithm
Motivation: simplifying fractions
/gcd(18,24)
18 = 3 24 4
/gcd(18,24) =?
Greatest Common Divisor Problem Input: two positive integers m and n Output: greatest common divisor, gcd(m, n)
18480831109
9231418071
https: //flux. qa
Let’s find an algorithm
Greatest Common Divisor Problem
Input: two positive integers m and n Output: greatest common divisor, gcd(m, n)
Observations
• the greatest possible common divisor is the smaller of the two numbers, e.g. gcd(178, 89) = 89
• the smallest possible divisor is 1, e.g. gcd(97, 53) = 1
• we are after the greatest divisor, e.g. gcd(24, 18) = 6, not
1, 2, or 3
“Brute force” Algorithm
check all integers between min(%, ') and 1 (from big to small), output first common divisor encountered
How to “check every integer”?
Observations
• Depending on input there can be an arbitrary number of
integers to check
• But a program will always have only a fixed number of
instructions
So: need to repeat some instructions many times in a loop.
before loop... condition True repeated
False
...after loop
How to “check every integer”?
loop
input
m, n
x = min(m, n)
x is common divisor of n, m
True
output x
False
repeated instruction
x = x - 1
“Brute force” Algorithm
check all integers between min(m, n) and 1 (from big to small), output first common divisor encountered
Where am I?
1. Custom modules and functions
2. Boolean expressions
3. Conditionals
4. Greatest common divisor
5. While-loops
6. Euclid's Algorithm
While statement in Python for loopy control flows
# before loop
# ...
#
while condition:
# repeated
# ...
#
# after loop
# ...
#
before loop... condition True repeated
False
...after loop
Example: summing first n integers
def sum_of_first_n_ints(n):
"""
Input : positive integer n
Output: sum of pos. integers up to n
"""
1+2+⋯+% =?
before loop... condition True repeated
False
...after loop
Example: summing first n integers
def sum_of_first_n_ints(n):
"""
Input : positive integer n
Output: sum of pos. integers up to n"""
i = 1 #iteration variable
res = 0 #accumulation variable
1+2+⋯+% =?
i=1 res = 0
condition
False
T rue
repeated
...after loop
Example: summing first n integers
def sum_of_first_n_ints(n):
"""
Input : positive integer n
Output: sum of pos. integers up to n"""
i = 1 #iteration variable
res = 0 #accumulation variable
while i <= n:
res = res + i i = i +1
1+2+⋯+% =?
i = 1 res = 0
i <= n True
False
sum = sum + i i = i +1
...after loop
Example: summing first n integers
def sum_of_first_n_ints(n):
"""
Input : positive integer n
Output: sum of pos. integers up to n"""
i = 1 #iteration variable
res = 0 #accumulation variable
while i <= n:
res = res + i
i = i +1 return res
1+2+⋯+% =?
i = 1 res = 0
i <= n True
False
sum = sum + i i = i +1
output sum
Sometimes we want condition last
instructions will be repeated while the condition is False
False
before loop... repeated
condition True ...after loop
Example: approximating !
! = 41 − 43 + 45 − 47 ⋯
!
/
= + −1 ,-.
,0. 4 22 − 1
before loop...
repeated
condition True
...after loop
Example: approximating !
! = 41 − 43 + 45 − 47 ⋯
!
8
= 6 −1 )7+
)*+ 4 2% − 1
False
%=0 $=0
"=$
%=%+1 $−" ≤1 True
$ = $ + −1 )*+ 4⁄ 2% − 1
output$
To realise condition at end we can use conditional break statement
def pi_approximation(eps):
"""
Input : positive float eps (accuracy)
Output: approximation x to pi with abs(x-pi)<=eps
"""
i = 0 #iteration variable
x = 0 #candidate solution
while True:
loop never exits here
i += 1
z= x
x = x + (-1)**(i+1)*4/(2*i-1)
# exit loop here if abs(x-z)<=eps
return x
$=0 #=0
False
!=#
$=$+1 #−! ≤0 True
# = # + −1 ()* 4⁄ 2$ − 1
output#
To realise condition at end we can use conditional break statement
def pi_approximation(eps):
"""
Input : positive float eps (accuracy)
Output: approximation x to pi with abs(x-pi)<=eps
"""
i = 0 #iteration variable
x = 0 #candidate solution
while True:
i += 1
z= x
x = x + (-1)**(i+1)*4/(2*i-1) if abs(x - z) <= eps:
break
return x
break statement exits surrounding loop
$=0 #=0
False
!=#
$=$+1 #−! ≤0 True
# = # + −1 ()* 4⁄ 2$ − 1
output#
Loops pose a new kind of danger
def sum_of_first_n_ints(n):
"""
Input : positive integer n
Output: sum of pos. integers up to n"""
i = 1 #iteration variable
res = 0
while i <= n:
res = res + i
i = i +1 return sum
1+2+⋯+% =?
Forgetting just one line results in this flowchart J
Everyone in this unit (including staff) will write an infinite loop by accident at some point
Common mistakes:
◦ Counter not incremented ◦ Tautological condition
◦ Forgot break
https://xkcd.com/1195/
Using while to implement brute force GCD algorithm
input
m, n
x = min(m, n)
doesn’t match the Python pattern for while loops
x is common divisor of n, m
True
output x
False
x = x - 1
need to logically invert the loop condition
https: //flux. qa
Using while to implement brute force GCD algorithm
input
m, n
x = min(m, n) x is not common True divisor of n, m
False
output x
x = x - 1
def gcd_brute_force(m, n):
x = min(m, n)
while not (m % x == 0 and n % x == 0): x=x-1
return x
Using while to implement brute force GCD algorithm
input
m, n
x = min(m, n) x is not common divisor of n, m
False
output x
True x = x - 1
simplified condition
def gcd_brute_force(m, n):
x = min(m, n)
while (m % x != 0) or (n % x != 0): x=x-1
return x
Analysing our GCD algorithm
We have implemented an algorithm to find the GCD of two strictly positive integers
(exercise: make it work for negative and 0 inputs).
>>> gcd_brute_force(24, 18)
6
>>> gcd_brute_force(112, 64)
16
>>> gcd_brute_force(18480831109, 9231418071)
^CTraceback (most recent call last):
File “
File “gcd.py”, line 7, in gcd_brute_force
while (m % x != 0) or (n % x != 0):
KeyboardInterrupt
>>>
But our algorithm seems too slow for large inputs! Is there a better algorithm?
Where am I?
1. Custom modules and functions
2. Boolean expressions
3. Conditionals
4. Greatest common divisor
5. While-loops
6. Euclid’s Algorithm
Let’s analyse the problem to derive smarter algorithm
!” #”
Orange: 24 = 4×6 Blue: 54 = 9×6
Both stacks are made of 6s.
6 6 6 6
66 66 66 666
Input can be decreased to smaller input with same output
If we subtract the smaller stack from the bigger stack, the result will also be made of 6s:
!” #” $%
6666 6666 6666 666666
We have shown that gcd(54, 24) = gcd(24, 30)
This reduction can be applied repeatedly
We repeat the process, subtracting the new smallest stack from the previous smallest stack:
#$ !” %
6
6
6 66
6 6 6 6
6
We have shown that gcd(54, 24) = gcd(24, 6)
…but we don’t have to stop there
We repeat the process, subtracting the new smallest stack from the previous smallest stack:
!” % #$
6 66 66 666
We have shown that gcd(54, 24) = gcd(6, 18)
…but we don’t have to stop there
We repeat the process, subtracting the new smallest stack from the previous smallest stack:
!” $ !#
6 66 666
We have shown that gcd(54, 24) = gcd(12, 6)
…but we don’t have to stop there
We repeat the process, subtracting the new smallest stack from the previous smallest stack:
!” $ !#
6 66 666
We have shown that gcd(54, 24) = gcd(12, 6)
Eventually we end up at a simple case
The gcd of a non-zero number m and itself is simply m !” # #
6 6
66
We have shown that gcd(54, 24) = gcd(6, 6) = 6
…or an even simpler (or at least more general) case
The gcd of a non-zero m number and zero is simply m “!”
66
We have shown that gcd(54, 24) = gcd(6, 0) = 6
Reduction holds for all (unknown) divisors x
We have shown that: gcd(9&, 4&) = gcd(4&, 9& − 4&) Wecangeneralise: gcd(,,-) = gcd(-,,−-)
./.−/
xxxx xxxx xxxx xxxxxx
Can we improve efficiency?
What would happen if our m and n started like this?
mn xxxxxxxx
xxxxxxxxx xxxxxxxxx x xxxxxxxxx x xxxxxxxxx x xxxxxxxxx
Idea:
We would subtract n 17 times!
Can we shortcut this process?
Instead of subtracting, we get the same result if we take the integer remainder of dividing ! by “, i.e., ! % ” in Python.
(This operation is also called modulo).
Final problem reduction: gcd(m, n) = gcd(n, m % n)
m
n
m%n
x x
xxxxxxxx xxxxxxxxx xxxxxxxxx%x xxxxxxxxx x xxxxxxxxx x xxxxxxxxx
Seems we need m >=n
for this to work.
m%n
xx
x%xx x
n
Final problem reduction: gcd(m, n) = gcd(n, m % n)
m
n
m%n
xxxxxxxx
x xxxxxxxxx x x%xxxxxxxxx x x xxxxxxxxx x
xxxxxxxxx xxxxxxxxx
But if m <=n reduction simply flips arguments
Thus
gcd(m, n) = gcd(n, m%n) is generally correct and reduces problem size after at most two applications
m
n
m%n
x x
xxxxxxxx xxxxxxxxx xxxxxxxxx%x xxxxxxxxx x xxxxxxxxx x xxxxxxxxx
Euclid’s Algorithm
input
m, n
n != 0
False
output m
True
r=m%n m=n n=r
Eukleides of Alexandria 3xx BC – 2xx BC
def gcd(m, n):
"""
Input : integers m and n such that not n==m==0
Output: the greatest common divisor of m and n
"""
while n != 0:
r=m%n m=n n=r
return m
Recommended reading
Perkovic. Introduction to Computing using Python • 2.1 (expressions)
• 3.3 (user-defined functions)
• 5.x (control flow, for-loops*)
Levitin. Introduction to Analysis and Design of Algorithms • 1 (pp 4-5 discusses Euclid’s algorithm)
FIT1045/53 Workbook
• 1 (expressions) • 2 (control flow) • 4 (functions)
*pre-reading
Check point for this week
By the end of this week you should be able to implement Python functions to:
• calculate the average of a list
• find a given item in a list
• compute specific sums and products
Next lecture...
• collections and sequences
• tables and matrices • for-loops
• working with files