Q11 フィボナッチ数列

C#のソース

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

class CSBigInteger
{
    const int UB = 50;
    internal int[] mNumArr = new int[UB + 1];

    internal void Add(int pNum)
    {
        int CurrInd = 0;
        while (pNum > 0) {
            mNumArr[CurrInd++] += pNum % 10;
            pNum /= 10;
        }
        KetaAgariSyori();
    }

    internal void Add(CSBigInteger pIns)
    {
        for (int I = 0; I <= UB; I++) {
            mNumArr[I] += pIns.mNumArr[I];
        }
        KetaAgariSyori();
    }

    //桁上がりを処理
    private void KetaAgariSyori()
    {
        for (int I = 0; I <= UB; I++) {
            if (mNumArr[I] >= 10) {
                mNumArr[I + 1] += mNumArr[I] / 10;
                mNumArr[I] %= 10;
            }
        }
    }

    //文字列で表現
    internal string DeriveStr()
    {
        var sb = new System.Text.StringBuilder();
        bool FoundNonZero = false;
        for (int I = UB; 0 <= I; I--) {
            if (mNumArr[I] != 0) FoundNonZero = true;
            if (FoundNonZero) {
                sb.Append(mNumArr[I]);
            }
        }
        if (FoundNonZero == false) return "0";
        return sb.ToString();
    }
}

class Program
{
    const int NeedFoundCnt = 2 + 6 + 5;

    static void Main()
    {
        int FoundCnt = 0;
        var FibList = new List<CSBigInteger>();

        for (int I = 0; true; I++) {
            AddNextKou(FibList);
            int[] NumArr = FibList[I].mNumArr;
            int NumSum = NumArr.Sum();

            int ModVal = 0;
            for (int J = NumArr.GetUpperBound(0); 0 <= J; J--) {
                ModVal *= 10;
                ModVal += NumArr[J];
                ModVal %= NumSum;
            }
            if (ModVal == 0) {
                FoundCnt++;
                Console.WriteLine(FibList[I].DeriveStr());
                if (FoundCnt == NeedFoundCnt) break;
            }
        }
    }

    //フィボナッチ数列の次の項をAddする
    static void AddNextKou(List<CSBigInteger> pFibList)
    {
        if (pFibList.Count == 0 || pFibList.Count == 1) {
            var InsBigInteger = new CSBigInteger();
            InsBigInteger.Add(1);
            pFibList.Add(InsBigInteger);
        }
        else {
            int LastInd = pFibList.Count - 1;
            var InsBigInteger = new CSBigInteger();
            InsBigInteger.Add(pFibList[LastInd - 1]);
            InsBigInteger.Add(pFibList[LastInd]);
            pFibList.Add(InsBigInteger);
        }
    }
}

実行結果

1
1
2
3
5
8
21
144
2584
14930352
86267571272
498454011879264
160500643816367088

解説

C#4.0のBigIntegerクラスもどきを使ってます。