알고리즘을 통해 걸어

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 

그러면 루프가 올바르게 종료됩니까? 당신이 얻을 Fast-Fib(5)에 대한 있도록 , 대답

Answer 1

당신은 fib의 요소를 액세스로 01,135 결과 :

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