MIT OpenCourseWare http://ocw.mit.edu6.00 Introduction to Computer Science and ProgrammingFall 2008 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.6.00 Handout, Lecture 12 (Not intended to make sense outside of lecture) a b c d e f g h ----------------- 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 … 11111111Item Size Value Number Available watch (w) 1 15 2 vase (v) 5 10 2 radio (r) 3 9 2 picture (p) 4 5 2 11010010001000010000013579111315n**22**n01000020000300004000050000600007000013579111315n**22**n def fib(n): global numCalls numCalls += 1 if n <= 1: return n else: return fib(n-1) + fib(n-2) numCalls = 0 n = 5 print 'fib of', n, '=', fib1(n) fib(5) fib(4) + fib(3) fib(3) + fib(2) + fib(2) + fib(1) fib(2) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) def fib1(n): global memo global numCalls numCalls += 1 if not n in memo: memo[n] = fib1(n-1) + fib1(n-2) return memo[n] memo = {0:0,
View Full Document
Unlocking...