Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

フィボナッチ数の定義

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はそれを補ってあまりある魅力があるから良しとしましょう。

GitHubでコードを公開しています。

実行結果

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

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で公開したものを加筆・修正したものです。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした