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).

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) \in \!\, + 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 b
  • Python 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 number
24012 #input
enter second number
48096 #input
calling GCD(48096,24012)
calling GCD(24012,72)
calling GCD(72,36)
calling GCD(36,0)
b is 0 so we return a:36
GCD(48096,24012) = 36

  • 4 function calls were made, 5 at most

1-2 of 2