Part C: As you might have guessed, the slowness of the recursive \"divide-and-co

Question

Part C: As you might have guessed, the slowness of the recursive "divide-and-conquer" Fibonacci function, fib(n), is duce to redundant calculations performed due to the recursive calls. A VERY POWERFUL concept in Computer Science is dynamic programming. Dynamic programming solutions eliminate the redundancy of divide-and conquer algorithms by caleulating the solutions to smaller problems first, storing their answers, and looking up their answers if later needed instead of recalculating them. We can use a list to store the answers to smaller problems of the Fibonacci sequence To transform from the recursive view of the problem to the dynamic programming solution you can do the following steps I) Store the solution to smallest problems (i.e., the base cases) in a list 2) Loop (no recursion needed) from the base cases up to the biggest problem of interest. On each iteration of the loop we: solve the next bigger problem by looking up the solution to previously solved smaller problems . . store the solution to this next bigger problem for later usage so we never have to recalculate it a) We'll reimplement fibln) that calculates the n number in the Fibonacci sequence use dynamic programming. The lab8·zip file you downloaded and extracted contains a partial program, in the file f ibDynEgm.py We'll use a list called, fibonacci, to store the solution to the "smaller" problems. Complete the dynamic programming code: def fib(n): "Dynamic programming solution to find the nth number in the Fibonacci sequence."" tList to hold the solutions to the smaller problems fibonacci [] t Step 1: Store base case solutions fibonacci.append ( fibonacci.append # Step 2: Loop from base cases to biggest problem of interest for position in xrange ( fibonacci.append ( # return nth number in the Fibonacci sequence return

Explanation / Answer

def fib(n):
    fibonacci = []
    fibonacci.append(1)
    fibonacci.append(1)

   
    for i in range(2,n+1):
        a = fibonacci[i-1] + fibonacci[i-2]
        fibonacci.append(a)

    return fibonacci[n-1]       

print(fib(4))

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.