フィボナッチ数の定義
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つ前までの数字を覚えていればよいので、配列の要素数は２つだけ用意しています。
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で公開したものを加筆・修正したものです。