Sandbox‎ > ‎IPT 2010-11‎ > ‎Josh's Sandbox‎ > ‎

### Zone4: Algorithms

 This is the area where I post interesting algorithms that I learn about. Most of these come from JRPC (James Ruse Programming Club). Subscribe to posts

#### USACO Milk2 Problem

posted Aug 12, 2010, 6:30 AM by Unknown user

 This is driving me insane...

#### Euclid's Algorithm for GCD

posted Mar 16, 2010, 11:25 PM by Unknown user   [ updated Mar 17, 2010, 1:31 AM ]

 This is an epic algorithm for finding the GCD(a,b) where (a,b) ℤ+  and a > b in O(log10b).This uses recursion (a function calling another)The algorithm is simple:gcd.pseudo (pseudocode)GCD(a,b):    if b == 0:        return a    else:        return GCD(b,a%b)note that a is always less than bPython code:gcd.py (source code)def GCD(a,b): print "calling GCD("+str(a)+","+str(b)+")" if b == 0: print "b is 0 so we return a:"+str(a) return a else: return GCD(b,a%b)x = int(raw_input("enter first number\n"))y = int(raw_input("enter second number\n"))print "GCD("+str(max(x,y))+","+str(min(x,y))+") = "+str(GCD(max(x,y),min(x,y))e.g. finding the Greatest Common Denominator (GCD) or Highest Common Factor (HCF) of 24012 and 48096:output (stdout)enter first number24012 #inputenter second number48096 #inputcalling GCD(48096,24012)calling GCD(24012,72)calling GCD(72,36)calling GCD(36,0)b is 0 so we return a:36GCD(48096,24012) = 364 function calls were made, 5 at most

1-2 of 2