C#:フィボナッチ数列を列挙する

  • 1
    いいね
  • 0
    コメント
この記事は最終更新日から1年以上が経過しています。

フィボナッチ数の定義

n番目のフィボナッチ数をf(n)とすると、以下のように表せます。


f(0) = 0,
f(1) = 1,
f(n) = f(n-1) + f(n-2)    //  (n ≧ 2)

フィボナッチ数列の詳しい説明については、Wikipediaのこちらのページをみてください。

遅すぎる再帰版のC#のコード

まずは、フォボナッチ数の定義をそのまま、以下のように書いてみました。

FiboRecursive.cs
  public static long Fibo(int n) {
      if (n == 0)
          return 0;
      if (n == 1)
          return 1;
      return Fibo(n - 1) + Fibo(n - 2);
  }

なんてシンプルで美しいんでしょう。

しかし、このメソッド使って、フィボナッチ数列を列挙しようとすると、とんでもなく遅いです。

FiboRecursiveMain.cs
  // f(0)..f(50)までを列挙する
  for (int i = 0; i <= 50; i++) {
      Console.WriteLine(Fibo(i));
  }

上のコードを実行すると、どんどん列挙が遅くなり、50番目のフィボナッチ数の計算の時には、無限ループしちゃったのかな?と思うくらい結果が返ってきません。

高速化したC#のコード

ということで、もっと速く求められるようにしたのが、以下のコードです。
何番目かを表すnを与える方法から、フィボナッチ数をどんどん列挙する方法に変更しました。

C#のコード

Fibonacci.cs
using System;
using System.Collections.Generic;
using System.Linq;

namespace Gushwell.Etude {
    class Program {
        static void Main(string[] args) {
            // f(0)..f(50)までを列挙する
            var fibos = Fibonacci.Enumerate()
                                 .Select((Value, Index) => new { Index, Value })
                                 .TakeWhile(x => x.Index <= 50);
            foreach (var f in fibos) {
                Console.WriteLine($"f({f.Index}) = {f.Value}");
            }
        }
    }

    static class Fibonacci {
        public static IEnumerable<long> Enumerate() {
            yield return 0;
            yield return 1;
            // 無限に求める オーバーフローは無視
            long[] array = new long[] { 0, 1 };
            while (true) {
                var fibo = array[0] + array[1];
                array[0] = array[1];
                array[1] = fibo;
                yield return fibo;
            }
        }
    }
}

フィボナッチ数を求めるには、2つ前までの数字を覚えていればよいので、配列の要素数は2つだけ用意しています。
C#のyield return を使っています。yield return本当に便利です。

ところで、LINQってインデックス扱おうとおもった瞬間、ダメな子になるのが玉に瑕です。まあ、LINQはそれを補ってあまりある魅力があるから良しとしましょう。

実行結果

上のコードの実行結果です。


f(0) = 0
f(1) = 1
f(2) = 1
f(3) = 2
f(4) = 3
f(5) = 5
f(6) = 8
f(7) = 13
f(8) = 21
f(9) = 34
f(10) = 55
f(11) = 89
f(12) = 144
f(13) = 233
f(14) = 377
f(15) = 610
f(16) = 987
f(17) = 1597
f(18) = 2584
f(19) = 4181
f(20) = 6765
f(21) = 10946
f(22) = 17711
f(23) = 28657
f(24) = 46368
f(25) = 75025
f(26) = 121393
f(27) = 196418
f(28) = 317811
f(29) = 514229
f(30) = 832040
f(31) = 1346269
f(32) = 2178309
f(33) = 3524578
f(34) = 5702887
f(35) = 9227465
f(36) = 14930352
f(37) = 24157817
f(38) = 39088169
f(39) = 63245986
f(40) = 102334155
f(41) = 165580141
f(42) = 267914296
f(43) = 433494437
f(44) = 701408733
f(45) = 1134903170
f(46) = 1836311903
f(47) = 2971215073
f(48) = 4807526976
f(49) = 7778742049
f(50) = 12586269025

いやー、あっと言う間に、Int32の上限を超えちゃうんですね。びっくりです。ということは、すぐにlongの最大値も超えちゃいますね。f(200)とか求めたかったら、BigInteger使わないとだめそうですね。


この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。