整数をフィボナッチに効率的にコーディングするには？

Question

フィボナッチシーケンスは、0と1で始まり、最後の2つの数字を加えて次の数字を得ることによって得られます。

すべての正の整数は、繰り返しなしのフィボナッチ数の集合の和として表すことができます。たとえば、13は{13}、{5,8}または{2,3,8}の集合の合計になります。しかし、われわれが見てきたように、いくつかの数値は、合計が数値である複数の集合を持っています。セットに2つの連続するフィボナッチ数を持たせることができないという制約を追加すると、各数値に対してユニークな表現ができます。

バイナリシーケンス（ちょうど0と1）を使用します。たとえば、17 = 1 + 3 + 13です。次に、17 = 100101です。詳細は図2を参照してください。

私はこの表現にいくつかの整数をオンにしたいのですが、整数は非常に大きいかもしれません。どのようにこれを効率的に行うか。

Answer 1

最初に私は本当にこの質問が好きだったと伝えたいと思います。すべての正の整数は繰り返しなしでフィボナッチ数の合計として表現できます。私は誘導によって証明しました。驚くばかり。
あなたの質問に答えるために、プレゼンテーションがどのように作成されるのかを把握しなければならないと思います。私はこれを見つける簡単な方法は、私たちが最も近いマイナーフィボナッチアイテムを見つけた数からであると考えています。
例40を提示したい場合：
Fib（9）= 34とFib（10）= 55なので、プレゼンテーションの最初の要素はFib（9）
です。 6および（Fib（5）= 5およびFib（6）= 8）、次の要素はFib（5）である。
だから我々は、40 =のFib（9）+のFibを持っている（5）+のFib（2）
はC＃

class Program 
    { 
     static void Main(string[] args) 
     { 
      List<int> fibPresentation = new List<int>(); 
      int numberToPresent = Convert.ToInt32(Console.ReadLine()); 
      while (numberToPresent > 0) 
      { 
       int k =1; 
       while (CalculateFib(k) <= numberToPresent) 
       { 
        k++; 
       } 
       numberToPresent = numberToPresent - CalculateFib(k-1); 
       fibPresentation.Add(k-1); 
      } 
     } 
     static int CalculateFib(int n) 
     { 
      if (n == 1) 
       return 1; 

      int a = 0; 
      int b = 1; 
      // In N steps compute Fibonacci sequence iteratively. 
      for (int i = 0; i < n; i++) 
      { 
       int temp = a; 
       a = b; 
       b = temp + b; 
      } 
      return a; 
     } 
    } 

あなたの結果は貪欲なアプローチとしてfibPresentation

Answer 2

これは十分に効率的かどうかはわかりませんが、バックトラッキングを使用して有効な表現を見つけることができます。

私は最大の可能FIB番号を取ることによって、バックトラックのステップを開始し、連続しまたは一度だけ制約違反があった場合にのみ、小さいものに切り替えることをしようとするだろう。

Answer 3

になります私はこれをで書くことができうまくいくようですが、関係を逆転させることができれば十分ですN=Fn。

Binet公式では、Fn=[φ^n/√5]で、角括弧は最も近い整数を表します。次にn=floor(lnφ(√5N))を使用すると、ソリューションに非常に近づきます。

17 => n = floor(7.5599...) => F7 = 13 
4 => n = floor(4.5531) => F4 = 3 
1 => n = floor(1.6722) => F1 = 1 

（私はいくつかのnの値が1でオフにすることができることを排除するものではない。）このエンコーディングは、より正確に「Zeckendorf表現」と呼ばれている

Answer 4

：（貪欲なアプローチが働くhttps://en.wikipedia.org/wiki/Fibonacci_coding

を見ますhttps://en.wikipedia.org/wiki/Zeckendorf%27s_theoremを参照してください）、数字をこの表現に変換するPythonコードがあります。それは最初の100個のフィボナッチ数を使用し、927372692193078999175までのすべての入力に対して正しく動作します（そして、より大きな入力に対しては間違っています）。

fibs = [0, 1] 
for _ in xrange(100): 
    fibs.append(fibs[-2] + fibs[-1]) 

def zeck(n): 
    i = len(fibs) - 1 
    r = 0 
    while n: 
     if fibs[i] <= n: 
      r |= 1 << (i - 2) 
      n -= fibs[i] 
     i -= 1 
    return r 

print bin(zeck(17)) 

出力は次のようになります。

0b100101 

Answer 5

問題自体は簡単です。あなたは常に残りの部分よりも小さい最大のフィボナッチ数を選択します。連続する数値を持つ制約を無視することができます（両方が必要な場合、次のものは両方の合計ですので、最初の2つの代わりに1つを選択する必要があります）。

だから、問題は行列で始まる知らトリックがありますすぐにいくつかの数のX. 未満最大のフィボナッチ数を見つけるために、どのように残っている（Mそれを呼び出す）

1 1 
1 0 

あなたがでfibbonacci数を計算することができます行列乗算（x番目の数はM^xです）。詳細はこちらhttps://www.nayuki.io/page/fast-fibonacci-algorithms。最終的な結果は、あなたが見ている数をO（logN）行列乗算で計算できることです。

既存のタイプに適合しない場合は、多数の計算（乗算と加算）が必要になります。 結果のためにもう一度必要とするので、初めて計算した2の累乗に対応する行列も保存します。

全体的にこれはO（（logN）^ 2 * large_number_multiplications/additions）です。