-1

こんにちは私はこのアルゴリズムを理解しようとしています。私はそれをウォークスルーして、どのような値が得られるかを確認しようとしていますが、そうすることであまり運がありません。私はこれが正しいかどうかわからないと思います。これがアルゴリズムです

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になります

4

1 に答える 1

2

の要素にアクセスしている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

于 2012-07-20T13:35:33.150 に答える