C++でn番目のフィボナッチ数の下一桁を求めるプログラム

この記事では、与えられた整数Nに対して、N番目のフィボナッチ数の下一桁（最後の桁）をC++で効率的に求める方法を解説します。

問題の説明

N番目のフィボナッチ数の最後の桁、すなわち最下位桁（LSB）を求めることが課題です。

具体例で問題を確認してみましょう。

入力： N = 120
出力： 1

解決アプローチ

最も単純な解法は、フィボナッチ数の一般項を直接計算する方法ですが、Nが非常に大きな数になった場合には、桁あふれや計算量の観点から現実的ではありません。

そこで活躍するのが、フィボナッチ数列の重要な性質です。それは「下一桁は60項ごとに同じパターンで繰り返す」というものです。例えば、75番目の項の下一桁と135番目の項の下一桁は必ず一致します。この周期性は「ピザーノ周期」と呼ばれています。

つまり、最初の60項までを計算すれば、すべての下一桁のパターンを網羅できます。求めたい項番号Nを60で割った余りを取ることで、どの項と同じ下一桁を持つかを特定できるのです。

アルゴリズムの手順

1. 入力されたNを60で割った余りを求める。
2. その余りの値に対応するフィボナッチ数を反復計算で求める。
3. 結果を10で割った余り（%10）を返すことで下一桁を取得する。

サンプルコード

#include <bits/stdc++.h>
using namespace std;

long int fibo(int N){
    long int a = 0, b = 1, c;
    for(int i = 2; i < N; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

int findLastDigitNterm(int N) {
    N = N % 60;
    return ( fibo(N) % 10);
}

int main() {
    int N = 683;
    cout<<"The last digit of "<<N<<"th Fibonacci term is "<<findLastDigitNterm(N);
    return 0;
}

実行結果

The last digit of 683th Fibonacci term is 1

コードのポイント

• fibo関数： 反復法を用いてn番目のフィボナッチ数を計算します。再帰呼び出しと比べて処理速度が速く、スタックオーバーフローの心配もありません。
• findLastDigitNterm関数： ピザーノ周期を利用してNを60に正規化することで、どんなに大きなNでも最大59項までの計算だけで済みます。
• 演算子 % 10： 計算結果の下一桁だけを抽出します。

この手法により、Nが何桁の数字であっても一定時間内に下一桁を求めることができ、競技プログラミングなどでも頻繁に使われるテクニックです。