22

フィボナッチ再帰のアルゴリズムを思い出そうとしています。以下：

public int fibonacci(int n)  {
  if(n == 0)
    return 0;
  else if(n == 1)
    return 1;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

それは貪欲なので、私が探しているものではありません。これは指数関数的に増加します ( Java の再帰的なフィボナッチ数列を見てください。最初の引数が大きいほど、無駄な呼び出しが行われます)。

おそらく、以前のフィボナッチ値を呼び出すと、値を再計算する代わりに値を取得する「巡回引数シフト」のようなものがあります。

4

9 に答える 9

43

多分このように：

int fib(int term, int val = 1, int prev = 0)
{
 if(term == 0) return prev;
 return fib(term - 1, val+prev, val);
}

この関数は末尾再帰です。これは、非常に効率的に最適化および実行できることを意味します。実際、単純なループに最適化されます..

于 2012-12-11T19:11:36.370 に答える
10

この種の問題は線形再帰型であり、高速な行列累乗によって最も速く解決されます。この種のアプローチを簡潔に説明するブログ投稿は次のとおりです。

于 2012-12-11T19:24:22.617 に答える
8

メモ化(つまり、以前の結果を保存して再計算を避ける) を使用すると、再帰的なフィボナッチのかなり高速なバージョンを実行できます。たとえば、Python での概念実証は次のとおりです。ここでは、以前の結果を保存するために辞書が使用されます。

results = { 0:0, 1:1 }

def memofib(n):
    if n not in results:
        results[n] = memofib(n-1) + memofib(n-2)
    return results[n]

通常は「通常の」再帰バージョンをブロックする入力値に対して、すばやく戻ります。intデータ型は大きな結果を保持するには不十分であり、任意精度の整数を使用することをお勧めします。

完全に別のオプション - この反復バージョンを書き直す ...

def iterfib(n):
    a, b = 0, 1
    for i in xrange(n):
        a, b = b, a + b
    return a

loop...私のコードで呼び出される末尾再帰関数として：

def tailfib(n):
    return loop(n, 0, 1)

def loop(i, a, b):
    if i == 0:
        return a
    return loop(i-1, b, a+b)
于 2012-12-11T19:12:40.507 に答える
3

n 番目の fib 番号を取得したい場合は、前の番号を含む配列を作成します。

int a[n];
a[0] = 0;
a[1] =1;
a[i] = n[i-1]+n[n-2];
于 2012-12-11T19:11:20.753 に答える
3

フィボナッチ問題に関する興味深い記事を見つけました

ここにコードスニペット

# Returns F(n)
def fibonacci(n):
    if n < 0:
        raise ValueError("Negative arguments not implemented")
    return _fib(n)[0]


# Returns a tuple (F(n), F(n+1))
def _fib(n):
    if n == 0:
        return (0, 1)
    else:
        a, b = _fib(n // 2)
        c = a * (2 * b - a)
        d = b * b + a * a
        if n % 2 == 0:
            return (c, d)
        else:
            return (d, c + d)

# added iterative version base on C# example
def iterFib(n):
    a = 0
    b = 1
    i=31
    while i>=0:
        d = a * (b * 2 - a)
        e = a * a + b * b
        a = d
        b = e
        if ((n >> i) & 1) != 0:
            c = a + b;
            a = b
            b = c
        i=i-1
    return a
于 2014-01-03T05:28:55.823 に答える
1

効率を高めるために再帰と遅延初期化キャッシュを使用する JavaScript の例:

var cache = {};

function fibonacciOf (n) {
  if(n === 0) return 0;
  if(n === 1) return 1;
  var previous = cache[n-1] || fibonacciOf(n-1);
  cache[n-1] = previous;
  return previous + fibonacciOf(n-2);
};
于 2015-06-06T17:06:35.230 に答える
0

高速なフィボナッチ計算に適したアルゴリズムは (Python で):

def fib2(n):
    # return (fib(n), fib(n-1))
    if n ==  0: return (0,  1)
    if n == -1: return (1, -1)
    k, r = divmod(n, 2) # n=2k+r
    u_k, u_km1 = fib2(k)
    u_k_s, u_km1_s = u_k**2, u_km1**2  # Can be improved by parallel calls
    u_2kp1 = 4 * u_k_s - u_km1_s + (-2 if k%2 else 2)
    u_2km1 = u_k_s + u_km1_s
    u_2k   = u_2kp1 - u_2km1
    return (u_2kp1, u_2k) if r else (u_2k, u_2km1)

def fib(n):
    k, r = divmod(n, 2) # n=2k+r
    u_k, u_km1 = fib2(k)
    return (2*u_k+u_km1)*(2*u_k-u_km1)+(-2 if k%2 else 2) if r else u_k*(u_k+2*u_km1)

非常に高速な計算が必要な場合は、libgmp にリンクし、mpz_fib_ui() または mpz_fib2_ui() 関数を使用します。

于 2016-12-15T23:02:50.963 に答える
0

Swift に翻訳された duedl0r のアルゴリズム:

func fib(n: Int, previous: (Int, Int) = (0,1)) -> Int {
    guard n > 0 else { return 0 }
    if n == 1 { return previous.1 }
    return fib(n - 1, previous: (previous.1, previous.0 + previous.1))
}

作業例:

fib(4)
= fib(4, (0,1) )
= fib(3, (1,1) )
= fib(2, (1,2) )
= fib(1, (2,3) )
= 3
于 2016-01-02T13:55:57.160 に答える