algorithm - 演练算法

Question

嗨，我正在尝试理解这个算法，并试图通过它来查看会产生什么值，但这样做的运气并不好。我想我不知道我是否做对了。这是算法

Algorithm Fast-Fibonacci(n)
Let fib[0] and fib[1] be 1.
for each i from 2 to n, do:
  Let fib[i] be fib[i - 2] + fib[i - 1].
end of loop
return fib[n].

say Fast-Fib(5)
fib[0] = 0
Fib[1] = 1
fib[2] = {2-2] + [2-1] = 1
fib[3] = [3-2] + [3-1] = 3
fib[4] = 4-2] + [4-1] = 5

那么循环退出对吗？导致 01135 作为答案

Answer 1

您正在访问 的元素fib，因此Fast-Fib(5)您将获得：

fib[0] = 1
fib[1] = 1
fib[2] = fib[2-2] + fib[2-1] = fib[0] + fib[1] = 1+1 = 2 // i==2
fib[3] = fib[3-2] + fib[3-1] = fib[1] + fib[2] = 1+2 = 3 // i==3
fib[4] = fib[4-2] + fib[4-1] = fib[2] + fib[3] = 2+3 = 5 // i==4
fib[5] = fib[5-2] + fib[5-1] = fib[3] + fib[4] = 3+5 = 8 // i==5

返回fib[5]（即5）

注意：我根据问题初始条件（fib[0]= fib[1]=1）更新了值；经常fib[0]=0；fib[1]=1