ゼッケンドルフの定理をC++で実装：隣り合わないフィボナッチ数の和への分解プログラム

本記事では、与えられた合計値が「互いに隣り合わないフィボナッチ数」の和として表現できるかどうかを判定し、表せる場合には実際にどの数値の組み合わせになるのかを求める方法を解説します。

例えば、合計値が10の場合、これは8と2の和として表せます。8も2もフィボナッチ数であり、しかもフィボナッチ数列の中で隣り合っていません。この性質はゼッケンドルフの定理として知られており、「任意の正の整数は、連続しないフィボナッチ数の和として必ず一意に表せる」ことを示しています。

それでは、考え方をつかむためのアルゴリズムを見ていきましょう。

アルゴリズム

nonNeighbourFibo(sum)

Begin
    while sum > 0, do
        fibo := sum 以下で最大のフィボナッチ数
        print fibo
        sum := sum - fibo
    done
End

処理の流れ

このアルゴリズムは貪欲法に基づいています。合計値が0より大きい間、次の手順を繰り返します。

1. 残りの合計値以下で最大のフィボナッチ数を求める
2. そのフィボナッチ数を出力する
3. 合計値からそのフィボナッチ数を引く

毎回「残りの値を超えない最大のフィボナッチ数」を選ぶため、次に選ばれる数は必ず2つ以上前の項になります。これにより、選ばれたフィボナッチ数同士が数列の中で隣り合わないことが自動的に保証されます。

C++での実装例

#include<iostream>
using namespace std;
int fibonacci(int n) {
    if (n == 0 || n == 1)
        return n;
    // n 以下で最大のフィボナッチ数を取得する
    int prev = 0, curr = 1, next = 1;
    while (next <= n) {
        prev = curr;
        curr = next;
        next = prev + curr;
    }
    return curr;
}
void nonNeighbourFibo(int sum) {
    while (sum > 0) {
        int fibo = fibonacci(sum);
        cout << fibo << " ";
        sum = sum - fibo;
    }
}
int main() {
    int sum = 120;
    cout << "Sum is same as Non-adjacent Fibonacci terms: ";
    nonNeighbourFibo(sum);
}

コードのポイント

• fibonacci(int n): 3つの変数 prev・curr・next を順に更新しながらループを回し、n 以下で最大のフィボナッチ数を返します。
• nonNeighbourFibo(int sum): 合計値が0になるまで、「残りの値以下で最大のフィボナッチ数」を出力しては差し引いていくことで、非隣接フィボナッチ数の組み合わせを求めます。

出力結果

Sum is same as Non-adjacent Fibonacci terms: 89 21 8 2

この出力から、120 = 89 + 21 + 8 + 2 であることが分かります。89・21・8・2はすべてフィボナッチ数であり、数列の中で互いに隣り合っていないことも確認できます。