import time def factorial(n): """Takes as input a nonnegative integer. Returns the factorial.""" if n == 0: return 1 else: return n * factorial(n - 1) def minimum(l): """Similar to the built-in function min(). Takes as input a list or tuple of one or more numbers. Returns the minimum number in the list.""" if len(l) == 1: return l[0] else: restMinimum = minimum(l[1:]) if l[0] < restMinimum: return l[0] else: return restMinimum def drawTree(t, trunkLength): """Draws a fractal tree; see the textbook.""" if trunkLength >= 5: t.forward(trunkLength) t.right(30) drawTree(t, trunkLength - 15) t.left(60) drawTree(t, trunkLength - 15) t.right(30) t.backward(trunkLength) def midpoint(a, b): """Returns the midpoint of two 2D points; see the textbook.""" return ((a[0] + b[0]) / 2.0, (a[1] + b[1]) / 2.0) def drawSierpinski(t, a, b, c, detail): """Draws the triangular Sierpinski fractal; see the textbook. Try drawSierpinski(t, (-200, -173), (200, -173), (0, 173), 6).""" if detail == 0: # Draw triangle. t.up() t.goto(a) t.down() t.goto(b) t.goto(c) t.goto(a) else: # Compute the midpoints of the three sides. ab = midpoint(a, b) bc = midpoint(b, c) ca = midpoint(c, a) # Draw three subfractals. drawSierpinski(t, a, ab, ca, detail - 1) drawSierpinski(t, b, bc, ab, detail - 1) drawSierpinski(t, c, ca, bc, detail - 1) def mapping(f, l): """Similar to the built-in function map(). Takes as input a funciton and a list/tuple. Returns a tuple consisting of the results of applying the function to each element in the original list/tuple.""" if len(l) == 0: return () else: return (f(l[0]),) + mapping(f, l[1:]) def powerSet(s): """Takes as input a set (a list or tuple with no repeated elements). Returns the powerset --- the set of all subsets (as a list of tuples).""" if len(s) == 0: return ((),) else: subsets = powerSet(s[1:]) result = [] for i in range(len(subsets)): result.append(subsets[i]) for i in range(len(subsets)): result.append((s[0],) + subsets[i]) return result def drawTriangleSAS(t, s0, angle, s1): """Draws a triangle based on the lengths of two sides and the angle between them (in degrees), using a turtle t.""" a = t.position() t.forward(s0) b = t.position() t.goto(a) t.left(angle) t.forward(s1) t.goto(b) t.goto(a) def drawLogarithmicSpiral(t, r0, r1, angle, count): """Draws a logarithmic spiral of count triangular chambers, based on initial radii r0 and r1 and an angle between them, using a turtle t. Try drawLogarithmicSpiral(t, 200.0, 190.0, 20, 18).""" if count >= 1: drawTriangleSAS(t, r0, angle, r1) drawLogarithmicSpiral(t, r1, r1 * r1 / r0, angle, count - 1) def drawKoch(t, length, detail): """Draws a Koch snowflake of the given side length and level of detail, using a turtle t. For example, when detail == 0 draws a line segment of the given length. Try drawKoch(t, 300, 4).""" if detail == 0: t.forward(length) else: drawKoch(t, length / 3.0, detail - 1) t.left(60) drawKoch(t, length / 3.0, detail - 1) t.right(120) drawKoch(t, length / 3.0, detail - 1) t.left(60) drawKoch(t, length / 3.0, detail - 1) def fibonacci(n): """Takes a nonnegative integer n as input. Returns the nth Fibonacci number.""" if n == 0: return 0 elif n == 1: return 1 else: return fibonacci(n - 1) + fibonacci(n - 2) def fibonacciIteratively(n): """Takes a nonnegative integer n as input. Returns the nth Fibonacci number.""" # Keep track of two consecutive Fibonacci numbers, called old and new. old = 0 new = 1 # Inchworm to update old to new and new to old + new. for i in range(n): temp = old + new old = new new = temp return old if __name__ == "__main__": print "Here are timing results for fibonacciIteratively():" for i in range(0, 100, 10): startTime = time.time() fib = fibonacciIteratively(i) endTime = time.time() print i, endTime - startTime print "Here are timing results for fibonacci():" for i in range(0, 100, 10): startTime = time.time() fib = fibonacci(i) endTime = time.time() print i, endTime - startTime