Problem104 両端がパンデジタルなフィボナッチ数

問題

フィボナッチ数列は再帰的な関係によって定義される:
F[n] = F[n-1] + F[n-2]

F[541] (113桁)は,
下9桁に1から9までの数字をすべて含む初めてのフィボナッチ数である

そして,
F[2749] (575桁)は, 頭から9桁に1から9までの数字をすべて含む初めてのフィボナッチ数である.

F[k]が, 頭から9桁と下9桁の
どちらも1から9までの数字をすべて含む初めてのフィボナッチ数とするとき,
kを求めよ.

ソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static int mCurrKeta;

    const int JyougenKousuu = 330000;

    //桁上がりには 最低4回は演算が必要 9*2=18 18*2=36 36*2=72 72*2=144
    const int JyougenKetasuu = JyougenKousuu / 4;

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();
        int[] PrevArr = new int[JyougenKetasuu + 1];
        int[] CurrArr = new int[JyougenKetasuu + 1];
        int[] wkArr = new int[JyougenKetasuu + 1];

        PrevArr[1] = 0; CurrArr[1] = 1;
        mCurrKeta = 1;

        for (int I = 2; I <= JyougenKousuu; I++) {
            if (I % 1000 == 2) Console.WriteLine("{0}。{1}項目の検証中。現在の桁数={2}",
                sw.Elapsed, I, mCurrKeta);
            Array.Copy(CurrArr, 1, wkArr, 1, mCurrKeta);
            Kasan(CurrArr, PrevArr);
            Array.Copy(wkArr, 1, PrevArr, 1, mCurrKeta);

            if (IsOK(I, CurrArr)) return;
        }
    }

    static bool IsOK(int pI, int[] pCurrArr)
    {
        for (int I = mCurrKeta + 1; I >= 1; I--) {
            if (pCurrArr[I] != 0) {
                mCurrKeta = I;
                break;
            }
        }

        if (mCurrKeta < 9) return false;

        if (IsPandigital(1, 9, pCurrArr) == false) return false;
        if (IsPandigital(mCurrKeta - 8, mCurrKeta, pCurrArr) == false) return false;

        Func<string> DeriveStr = () =>
        {
            var sb = new System.Text.StringBuilder();
            for (int I = mCurrKeta; I >= 1; I--)
                sb.Append(pCurrArr[I]);
            return sb.ToString(); ;
        };

        Console.WriteLine("{0}項目の{1}は先頭も末尾もパンデジタルです", pI, DeriveStr());
        return true;
    }

    static bool IsPandigital(int pSta, int pEnd, int[] pCurrArr)
    {
        bool[] CheckedArr = new bool[9 + 1];
        for (int I = pSta; I <= pEnd; I++) {
            if (pCurrArr[I] == 0) return false;
            int Num = pCurrArr[I];
            if (CheckedArr[Num]) return false;
            CheckedArr[Num] = true;
        }
        return true;
    }

    static void Kasan(int[] pArrDest, int[] pArrSource)
    {
        for (int I = 1; I <= mCurrKeta; I++) {
            pArrDest[I] += pArrSource[I];
        }
        Ketaagari(pArrDest);
    }

    static void Ketaagari(int[] pArr)
    {
        for (int I = 1; I <= mCurrKeta + 1; I++) {
            if (pArr[I] >= 10) {
                pArr[I + 1] += pArr[I] / 10;
                pArr[I] %= 10;
            }
        }
    }
}

実行結果

省略
00:16:39.1824002。321002項目の検証中。現在の桁数=67085
00:16:44.3339287。322002項目の検証中。現在の桁数=67294
00:16:49.4948237。323002項目の検証中。現在の桁数=67503
00:16:54.6864285。324002項目の検証中。現在の桁数=67712
00:16:59.9606567。325002項目の検証中。現在の桁数=67921
00:17:05.1806830。326002項目の検証中。現在の桁数=68130
00:17:10.4830870。327002項目の検証中。現在の桁数=68339
00:17:15.7433752。328002項目の検証中。現在の桁数=68548
00:17:21.0125437。329002項目の検証中。現在の桁数=68757
329468項目の2456817391860・・・省略・・・30505511790352786941は先頭も末尾もパンデジタルです

解説

Int型の配列で大きな桁を代用してます。

ArrayクラスのCloneメソッドよりも
ArrayクラスのCopyメソッドで最小限のデータコピーにしたほうが
処理が速いようですね。