C#でプロジェクトオイラーを解く（問題２５「1000桁のフィボナッチ数」）

Tweet

Pocket

どーも、みつおです。

ついに２５問！レベル１に到達！

問題

フィボナッチ数列は以下の漸化式で定義される:

Fn = Fn-1 + Fn-2, ただし F1 = 1, F2 = 1.

最初の12項は以下である.

• F1 = 1
• F2 = 1
• F3 = 2
• F4 = 3
• F5 = 5
• F6 = 8
• F7 = 13
• F8 = 21
• F9 = 34
• F10 = 55
• F11 = 89
• F12 = 144

12番目の項, F12が3桁になる最初の項である.

1000桁になる最初の項の番号を答えよ.

出典：Problem25

解答

using System;
using System.Numerics;

namespace Problem25
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Solve());
            Console.ReadLine();
        }

        private static long Solve()
        {
            long ret = 2;          
            int len = 0;

            BigInteger f0 = 0;
            BigInteger f1 = 1;
            BigInteger f2 = f1 + f0;

            //1000桁になるまでループ
            while (len < 1000)
            {
                //フィボナッチ数を計算
                f0 = f1;
                f1 = f2;
                f2 = f1 + f0;

                //桁数を取得
                len = f2.ToString().Length;

                ret++;
            }

            return ret;
        }
    }
}

出力

4782