【C++】合計がKとなる最小個数のフィボナッチ数を求める方法

この記事では、数値Kが与えられたときに合計がKに等しくなる最小個数のフィボナッチ数を求める問題について解説します。

フィボナッチ数列とは

フィボナッチ数列とは、直前の2つの数を足し合わせることで次の数を生成していく数列です。数列はF0とF1という2つの初期値から始まり、一般にF0=0、F1=1(またはF0=1、F1=1)が用いられます。

フィボナッチ数列は「0, 1, 1, 2, 3, 5, 8, 13 …」のように続きます。

問題の例

入力:

K = 5

出力:

2

説明:

5は 3 + 2 の合計で表すことができます。

解き方のアプローチ

1自体がフィボナッチ数であるため、フィボナッチ数の組み合わせによって任意の整数を合計として表現できます。たとえば1をn回加算すれば合計はnになります。しかし本問題の目的は、合計Kを作るために必要なフィボナッチ数の個数を最小化することです。

この問題は、硬貨の額面がフィボナッチ数であるとみなした「硬貨両替問題(Coin Change Problem)」と同じ構造を持っています。プログラミングにおいて、この種の問題を解く手法は貪欲法(Greedy法)と呼ばれます。

具体的には、まず合計n以下のフィボナッチ数をすべて列挙します。そのうえで、大きい側の項から順にnから減算し、同時に使用した項数をカウントしていきます。着目中の項がnより大きくなったら、n以下の次のフィボナッチ項へ移動します。最終的にカウントした項数を出力すれば答えとなります。

なお、この貪欲法が常に最小個数を保証できることはツァイケンドルフの定理(Zeckendorf's theorem)によって裏付けられています。任意の正整数は「連続しないフィボナッチ数の和」として一意に表せるため、大きな項から順に選んでいく戦略で必ず最適解が得られます。

アルゴリズム

• フィボナッチ数を生成する関数を作成します。
• n以下のすべてのフィボナッチ数を計算します。
• 次の項がnを超えた場合は、それをベクターに追加せずに処理を終了します。
• 合計がnとなる最小個数のフィボナッチ数を求める関数を作成します。
• フィボナッチ数を格納するベクターを初期化します。
• 合計が0より大きい間、nからフィボナッチ数を減算していきます。
• 合計nをj番目のフィボナッチ数で割ることで、その項が合計に何回分寄与するかを求めます。
• 得られたカウントを出力します。

C++での実装例

以下は、本ソリューションの動作を示すサンプルプログラムです。

#include <bits/stdc++.h>
using namespace std;
void findFiboTerms(vector<int>& fiboVals, int K){
    int i = 3, nextTerm;
    fiboVals.push_back(0);
    fiboVals.push_back(1);
    fiboVals.push_back(1);
    while (1) {
        nextTerm = fiboVals[i - 1] + fiboVals[i - 2];
        if (nextTerm > K)
            return;
        fiboVals.push_back(nextTerm);
        i++;
    }
}
int findTermForSum(int K){
    vector<int> fiboVals;
    findFiboTerms(fiboVals, K);
    int termCount = 0, j = fiboVals.size() - 1;
    while (K > 0) {
        termCount += (K / fiboVals[j]);
        K %= (fiboVals[j]);
        j--;
    }
    return termCount;
}
int main(){
    int K = 11;
    cout<<"Minimum Fibonacci terms with sum equal to K is "<<findTermForSum(K);
    return 0;
}

出力

Minimum Fibonacci terms with sum equal to K is 2

コードのポイント

findFiboTerms関数はK以下のフィボナッチ数をベクターへ格納し、findTermForSum関数では大きい項から順に商と剰余を利用して項数を数えています。フィボナッチ数は指数的に増大するため、必要な項の数は高々数十個程度であり、全体の計算量はO(log K)ときわめて高速に動作します。