CompSciWeek2
From Predictive Chemistry
(Wed. only)
Contents
Reading Assignment
- Beginning Python, Chapter 5
Algorithms, Continued
- Complexity notation, O(n), etc.
- Loop Complexity
- First algorithms (Horner, Euclid, Babylonian)
- Code walk-through for a poorly designed Euclids algo.
- The KISS, DRY, and incremental principles
- Loading python modules
Poorly Designed Euclid's Algo.
<source lang="python"> a = 1547 b = 224
while(1):
if a < b: c = a a = b b = c a = a % b if a < b: c = a a = b b = c if a == 0: break print "%d, %d"%(a,b)
print "The GCD of %d and %d is %d"%(a,b,b) </source>
Improved Version
<source lang="python"> doc = """ Euclid's Algo.: reduce 7/30 - 8/18
30 = 6*5 18 = 6*3 (7*3 - 8*5)/(6*5*3)
gcd(a,b)
gcd(30,18) = 6 = gcd(18,12) = 6 = gcd(12,6) = gcd(6, 0) = 6 [termination]
show: gcd(a, b) = gcd(b, a mod b)
... gcd(a, 0) = a
write:
a = s*u, b = t*u u also divides r = a % b = a - b*q = (s - q*t)*u
Properties:
(a + b) mod c = a % c + b % c a - b mod c = a mod c - b mod c (a*b) mod c = (a mod c) * (b mod c)
a*(b/a) """
- always return a <= b
def order(a, b):
if a < b: return a, b else: # a >= b return b, a
b = 1547 a = 224
- Input integer a, b
- Output: integer gcd(a,b)
def gcd(a, b):
b, a = order(b, a)
while b != 0: #print "%d, %d"%(a,b) a = a % b # a < b a, b = b, a return a
r = gcd(a, b)
str = "The GCD %d of %d and is %d "%(a, b, r) print str
- subtracting numbers in quotient form
def qsub((a, b), (c, d)):
return (a*c -b*d), (c*d)
</source>