Difference between revisions of "CompSciWeek2"
From Predictive Chemistry
| (3 intermediate revisions by the same user not shown) | |||
| Line 3: | Line 3: | ||
== Reading Assignment == |
== Reading Assignment == |
||
* Beginning Python, Chapter 5 |
* Beginning Python, Chapter 5 |
||
| − | * Algorithms, Chapters 1-3 |
||
| − | |||
== Algorithms, Continued == |
== Algorithms, Continued == |
||
| − | ** ignore python 'Class' for now |
||
* Complexity notation, O(n), etc. |
* Complexity notation, O(n), etc. |
||
* Loop Complexity |
* Loop Complexity |
||
| Line 35: | Line 32: | ||
print "The GCD of %d and %d is %d"%(a,b,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> |
</source> |
||
Latest revision as of 09:56, 18 September 2014
(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>
