CS计算机代考程序代写 python algorithm FIT1045: Algorithms and Programming Fundamentals in Python Lecture 2

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)
the only two objects
>>> 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)
>>> from prices import price_after_gst
>>> 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 ““, line 1, in
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