« [Windows7] 一般向けのβ版ダウンロード開始、 日本語版も。 | トップページ | [TDD の練習(4)] フィボナッチ数列の問題 ~ その2 : 偶数だけを集計する »

2009年1月12日 (月)

[TDD の練習(4)] フィボナッチ数列の問題 ~ その1 : 数列を生成する

ぴえろっちが教えてくれた Project Euler の問題 ( かってに改題 f(^^; ) より。
…いや、 オリジナルを示しておきましょか。

Project Euler .net ~ Problem 2 ( 19 October 2001 )
日本語訳: Project Euler ~ Problem 2
フィボナッチ数列の項は前の2つの項の和である。最初の2項を 1, 2 とすれば、最初の10項は以下の通りである。

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

数列の項が400万を超えない範囲で、偶数の項の総和を求めよ。

この問題を解くプログラムには、 2つのモノが必要でしょう。
ひとつは、 フィボナッチ数列を生成するモノ。 ちゃんとフィボナッチ数列を作り出すことができなければ、 総和を求めるもへったくれもありません。
そしてもうひとつは、 生成されてくるフィボナッチ数列から偶数を選び出して集計してくれるモノ。 こいつに、 「数列の項が400万を超えない範囲での合計はどんだけ?」 って聞いてやれば、 答えが返ってくるわけです。

ということで、 まずは、 「フィボナッチ数列発生機」 を作ります。
例によって、 どんなテストコードを書いていけばいいのかを、 文章で書いてみますので、 ユニットテストに書き下してみてください。
※ サンプルは C# 2008 EE で作りました。 ので、 カッコつけて yield retun を使ってます。 f(^^;

  1. n=1 のとき、 1が返る。
    → 実装は yield return 1; だけでいい。 シグネチャ等を確定させる。
     
  2. n=2 のときは、 2。
    → テストの方法を考える。 実装は、 最初は 1、 次は 2 を yield return してやる。

  3. n=3 以降のとき ( 適当な個数の期待値を用意してやる以外は、 2. と同じテスト )
    → 実装のコア部分は、これで完成する。
     
  4. [確認テスト] n が大きくなると例外が出るはず。  無限ループを回してみて、 例外が出ることを確認し、 その後、 try ~ catch のカタチのテストに直しておく。
    ※ n が幾つまでいけるのか? 使う人に情報を提供するためのテストです。 もちろん、 もし要件に満たなければ、 int を long に変えるなどの修正が必要になりますね。

回答例 ( C# + NUnit 用のソースコード ) はこちら → FibonacciSequenceGeneratorTest.cs [3KB]

ちゃんと自分で書いてみてから、 見てくださいね f(^^;

そして、 このテストコードをパスするように実装とリファクタリングしたコードは、 こうなりました。

using System.Collections.Generic;

namespace フィボナッチ数列 {
  public static class フィボナッチ数列発生機 {
    public static IEnumerable<int> Getフィボナッチ数列() {
      int f1 = 0;
      int f2 = 0;
      int f3 = 1;

      while (true) {
        f1 = f2;
        f2 = f3;
        f3 = checked(f1 + f2);
        yield return f3;
      }
    }
  }
}

※ 途中経過をコメントに残したコードは、 こちら → FibonacciSequenceGenerator.cs [2KB]

|

« [Windows7] 一般向けのβ版ダウンロード開始、 日本語版も。 | トップページ | [TDD の練習(4)] フィボナッチ数列の問題 ~ その2 : 偶数だけを集計する »

プログラミング」カテゴリの記事

-プログラミング ( わんくま )」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/209349/43721317

この記事へのトラックバック一覧です: [TDD の練習(4)] フィボナッチ数列の問題 ~ その1 : 数列を生成する:

» [TDD の練習(4)] フィボナッチ数列の問題 ~ その2 : 偶数だけを集計する [biac の それさえもおそらくは幸せな日々@nifty]
前回で 「フィボナッチ数列発生機」 が出来上がりました。こんどは、 生成されてくるフィボナッチ数列から偶数を選び出して集計してくれるモノ 「フィボナッチ数列偶数集計機」 を作ります。 フィボナッチ数列発生機の使い方は、 そのテストコードを見れば分かりますね。 また、 テストコードには、 n=45, F(n)=18363... [続きを読む]

受信: 2009年1月12日 (月) 22時45分

» [コミック] 数学ガール [biac の それさえもおそらくは幸せな日々@nifty]
・ 「数学ガール 上」 原作/結城浩・作画/日坂水柯 978-4840122924・ 「数学ガール 下」 原作/結城浩・作画/日坂水柯 978-4840125864 なんで #アニメ・コミック の方じゃなくてこっちかというと、 プログラマー向きのコミックだから f(^^;「僕」 が惚れているミルカさんと、 「僕」 に惚... [続きを読む]

受信: 2009年9月15日 (火) 13時22分

« [Windows7] 一般向けのβ版ダウンロード開始、 日本語版も。 | トップページ | [TDD の練習(4)] フィボナッチ数列の問題 ~ その2 : 偶数だけを集計する »