Problem2『Even Fibonacci numbers』


FibonacciFibonacci / OndasDeRuido
projecteuler.net


問題

 フィボナッチ数列において、400万以下の偶数項の総和を求めよ。

とりあえずフィボナッチ数列ぶん回すか!
using System;
using System.Diagnostics;

namespace Problem2
{
    class Program
    {
        static void Main(string[] args)
        {
            Debug.WriteLine(EF1(4000000));
        }

        static int EF1(int max)
        {
            int f1, f2;
            int sum = 0;

            f1 = 1;
            f2 = 1;
            while(true)
            {
                int f3 = f1 + f2;

                if (f3 > max) break;

                if (f3 % 2 == 0) sum += f3;

                f1 = f2;
                f2 = f3;
            }

            return sum;
        }
    }
}

 いつも通りフィボナッチ数列の項を1つ1つ判定して足していくプログラムです。


偶数の出かたとか

 フィボナッチ数列
\( 0,1,1,2,3,5,8,13,21,34,\cdots \)
と続きます。
前の2項を足したものが次の項、という形ですね。
漸化式としてはこんなの。
\(a_{n+2} = a_{n+1} + a_{n} \)


 数列をよく見ればわかりますが、規則正しい間隔で偶数が出現してます。
最初の0を抜かせば、
\(奇数、奇数、偶数、奇数、奇数、偶数、\cdots \)
という形になっています。
つまり、約2/3が奇数なので全部奇数偶数チェックする必要はないってこと。


 じゃぁ偶数項だけ算出できないかなと考えて、偶数項だけ抜き出してみました。
\( 2, 8, 34, 144, 610, 2584, \cdots \)
じっと見てると「なんとなく4倍くらい…?」と感じたので(直感派)いじくると、こんな式になりました。
\( a_{n+2} = 4 \cdot a_{n+1} + a_{n} \)
例えば、偶数第4項の値を求めるには、
\( a_{4} = 4 \cdot a_{3} + a_{2} \)
\( a_{4} = 4 \cdot 34 + 8 \)
\( a_{4} = 136 + 8 = 144 \)
と、こんな感じ。
これを使えばフィボナッチ数列から偶数項だけを取り出せる。


 …まぁ、フィボナッチ数列の一般項使えばいいんですけどね。

偶数列でやってみる
using System;
using System.Diagnostics;

namespace Problem2
{
    class Program
    {
        static void Main(string[] args)
        {
            Debug.WriteLine(EF2(4000000));
        }

        static int EF2(int max)
        {
            int sum = 0;

            int f2 = 2;
            int f1 = 0;

            sum += f2;

            while (true)
            {
                int fnext = f2 * 4 + f1;

                if (fnext > max) break;

                sum += fnext;

                f1 = f2;
                f2 = fnext;
            }

            return sum;
        }
    }
}

フィボナッチ―自然の中にかくれた数を見つけた人

フィボナッチ―自然の中にかくれた数を見つけた人

  • 作者: ジョセフダグニーズ,ジョンオブライエン,Joseph D’Agnese,John O’Brien,渋谷弘子
  • 出版社/メーカー: さえら書房
  • 発売日: 2010/09
  • メディア: ハードカバー
  • クリック: 37回
  • この商品を含むブログ (3件) を見る
波紋と螺旋とフィボナッチ

波紋と螺旋とフィボナッチ

不思議な数列フィボナッチの秘密

不思議な数列フィボナッチの秘密