algorithm - 修正フィボナッチ数列の N 位の数を取得する

Question

今日のインタビューで、修正されたフィボナッチのような数列が与えられました。

1、1、2、4、6、13、19、42、61、135、...、

n位の数値を返す関数を書くように言われました。

したがって、n = 4 の場合、関数は 4 を返し、n = 6 の場合は 13 を返す必要があります。

お気付きだと思いますが、違いは、偶数項目は前の 4 つの項目に等しく、奇数項目は前の 2 つの項目に等しいということです。

再帰を使用する場合は問題ありません。それが私がしたことですが、それは私が望んでいたアプローチではありません。

フィボナッチ計算は次のようになります (PHP の場合):

$n = 17;
$phi = (1 + sqrt(5)) / 2;
$u = (pow($phi, $n) - pow(1 - $phi, $n)) / sqrt(5);

$uは、この場合は 1597 です。

ただし、このようなフィボナッチ数列の修正版で解決する方法がわかりません。

score 1 · Accepted Answer

私があなたを正しく理解していれば、次のように定義されたシーケンスを効率的に [つまり、O( log(n) )] で計算する必要があります。

a[2n + 5] = a[2n + 4] + a[2n + 3] + a[2n + 2] + a[2n + 1]
a[2n + 2] = a[2n + 1] + a[2n]

2 つの新しいシーケンスを定義しましょう。最初のものは偶数位置の値に対応し、 2 つ目は偶数位置の値に対応します。

b[n] = a[2n]
c[n] = a[2n + 1]

これで、次のようになりました。

c[n] = b[n] + c[n - 1] + b[n - 1] + c[n - 2]
b[n] = c[n - 1] + b[n - 1]

最初の式から 2 番目の式を引くと (何らかの変換後)、次のようになります。

b[n] = ( c[n] - c[n-1] ) /2

次に、この式を最初の式に代入して、 cの式を取得します。

c[n] = 2 c[n-1] + c[n-2]

この式にはcの要素のみが含まれていることに注意してください。したがって、ここで説明する手法を使用して、 cの要素を計算できるようになりました。方程式をもう少し変換することで、bも効率的に計算できるようになります。

score 0 · Accepted Answer

定数係数の線形再帰によって定義されるすべての数列と同様に、フィボナッチ数には閉じた形式の解があります。

ただし、この特定のシーケンスの閉じた形式の式を作成する方法がわかりません。

追加できることは、フィボナッチまたは同様のシーケンスを再帰なしで解決できることです。たとえば、次のようになります。

したがって、スタックではなくループを使用して問題を解決できます。

2 に答える 2