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

プロジェクトオイラー
Pocket

どーも、みつおです。

ついに25問!レベル1に到達!

問題

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

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

コメント

タイトルとURLをコピーしました