Problem25 フィボナッチ数列で1000桁になる最初の項番号

問題

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

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桁になる最初の項番号を答えよ

ソース

#include <string>
#include <Windows.h>
#include <stdio.h>

//const int TargetKeta = 3;
const int TargetKeta = 1000;
int intArr[9999][TargetKeta*3];

void main()
{
    intArr[2][0] = intArr[1][0] = 1;

    const int UB0 = sizeof(intArr)/sizeof(intArr[0])-1;
    const int UB1 = sizeof(intArr[0])/sizeof(intArr[0][0])-1;

    for (int N = 3; N <= UB0; N++) {
        for (int Y = 0; Y <= UB1; Y++) {
            intArr[N][Y] = intArr[N-2][Y] + intArr[N-1][Y];
        }
        for (int Y = 0; Y <= UB1; Y++) {
            if (intArr[N][Y] >= 10) {
                intArr[N][Y+1] += intArr[N][Y] / 10;
                intArr[N][Y] %= 10;
            }
        }
        std::string WillOut;
        bool IsHit = false;
        for (int Y = UB1;Y >= 0;Y--){
            if (IsHit==false && intArr[N][Y] > 0) {
                IsHit = true;
            }
            if (IsHit){
                char wk[99]; wsprintf(wk,"%d",intArr[N][Y]);
                WillOut += wk;
            }
        }
        if (WillOut.size() >= TargetKeta) {
            printf("%d番目の値は%d桁(%s)\n",N,WillOut.size(),WillOut.c_str());
            return;
        }
        printf("%d番目の値は%d桁\n",N,WillOut.size());
    }
}

実行結果

省略
4776番目の値は998桁
4777番目の値は998桁
4778番目の値は999桁
4779番目の値は999桁
4780番目の値は999桁
4781番目の値は999桁
4782番目の値は1000桁(10700662663827589367649805844573968850836838966321516650132
35203375314520604694040621889147582489792657804694888177591957484336466672569959
51299603046126274809248218614406943305123477444275027378175308757939166619214925
91867595539664228371489431130746995034395470019854326097230672901928705264472437
26117715821825548491120525013201478612965931381792235559657452039506137551467837
54322911960212993404826070617539770684706820289548690266618543512452190036948064
13574474709117076197669456910700980243934396174741037369125032313655321647736970
23167755051595173518460579954919410967778373229665796581646513903488154256310184
22419025984608800011018625555024549393711365165703944762958471454852342595042858
24253060835444354282126110089928637950480068943303097732178348645431132057656598
68456288616808718693835297350643986297640660000723562917905207051164077614812491
88583094594056668833910935094445657635766615161931775379289166158132715961687748
7983821820492520348473874384736771934512787029218636250627816)

解説

intの配列で大きい桁の変数を代用してます。