フィボナッチ数列の位置に「O」を含む名前を生成するC++コードの解説

数値 n が与えられたとします。Amal はペットに名前を付けようとしており、あるアルゴリズムに従って名前を決定します。名前の長さは n 文字で、大文字の「O」と小文字の「o」のみで構成されます。アルゴリズムのルールは次のとおりです。名前の i 番目の文字は、i がフィボナッチ数列に含まれる場合は大文字の「O」、それ以外の場合は小文字の「o」となります。名前の文字は 1 から n までの番号が付けられています。

例えば、入力が n = 10 の場合、出力は「OOOoOooOoo」になります。これは、フィボナッチ数列の最初の数値が 1、2、3、5、… であるためです。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• まず、サイズ n の文字列 s を用意し、すべての文字を「o」で初期化します。
• 次に、i と j を 1 で初期化し、i が n 以下である限りループを回します。各反復処理の後で i を j ずつ増加させ、j を i - j に更新します。このテクニックにより、フィボナッチ数列を追加の配列や再帰なしで効率的に生成できます。
• ループ内では、s[i-1] を「O」に置き換えます。
• 最終的に文字列 s を返します。

このアルゴリズムの擬似コードは以下のようになります。

s := a string of size n and filled with 'o's
for initializing i and j from 1, when i <= n, increase i by j and set
j := i-j after each iteration, do
    s[i-1] := 'O'
return s.

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
string solve(int n){
    string s(n, 'o');
    for (int i = 1, j = 1; i <= n; i += j, j = i - j)
        s[i - 1] = 'O';
    return s;
}
int main(){
    int n = 10;
    cout << solve(n) << endl;
}

入力

10

出力

OOOoOooOoo

コードのポイント

この実装の魅力は、そのシンプルさにあります。フィボナッチ数列を事前に計算して配列に保存する代わりに、2つの変数 i と j を使った巧みな更新処理（i += j と j = i - j）によって、数列を順次生成しながら文字列を直接構築しています。これにより、時間計算量はフィボナッチ数の個数に比例し、O(log n) 程度で処理が完了するため、非常に効率的です。