C++でK番目のブーム数を求めるアルゴリズムと実装方法

はじめに

このチュートリアルでは、C++を使って「k番目のブーム数」を見つけるプログラムを作成します。

ブーム数とは、数字の2と3のみで構成される数のことです。たとえば、2、3、22、23、32、33、222などが該当します。

アルゴリズムの手順

この問題は、キュー（queue）を活用した幅優先探索（BFS）の考え方で効率よく解くことができます。具体的な手順は以下の通りです。

• 変数kの値を初期化します。
• 文字列型のキューを用意します。
• 空文字列をキューに追加します。
• カウンター変数を0で初期化します。
• カウンターがkに達するまで、以下の処理を繰り返すループを作成します。
  • キューの先頭要素を取得し、キューから取り出します。
  • 先頭要素を別の変数に保存しておきます。
  • 保存した文字列の末尾に「2」を付けた数をキューに追加します。
  • カウンターを1増やし、kと一致した場合はその値を出力して処理を終了します。
  • 同様に、末尾に「3」を付けた数をキューに追加します。
  • カウンターを増やし、kと一致した場合は値を出力して終了します。

この手法により、桁数が小さいものから順に、また同じ桁数内では昇順にブーム数を生成できるため、k番目の数を確実に求められます。

実装例

それでは、実際のコードを見てみましょう。

#include<bits/stdc++.h>
using namespace std;
void findKthBoomNumber(long long k) {
   queue<string> queue;
   queue.push("");
   long long count = 0;
   while (count <= k) {
      string numberOne = queue.front();
      queue.pop();
      string numberTwo = numberOne;
      queue.push(numberOne.append("2"));
      count++;
      if (count == k) {
         cout << numberOne << endl;
         break;
      }
      queue.push(numberTwo.append("3"));
      count++;
      if (count == k) {
         cout << numberTwo << endl;
         break;
      }
   }
}
int main() {
   long long k = 45;
   findKthBoomNumber(k);
   return 0;
}

出力結果

上記のコードを実行すると、次のような結果が得られます。

23332

コードのポイント

このコードでは、キューから取り出した文字列をもとに、「2」を付けた数と「3」を付けた数の2つを順番に生成しています。文字列として扱うことで、非常に大きな桁数のブーム数にも対応できる点が特徴です。なお、出力時にはlong long型の範囲を超える可能性があるため、string型のまま扱うのが安全です。

まとめ

本記事では、キューを用いた幅優先探索の考え方により、k番目のブーム数を求める方法を解説しました。本チュートリアルについてご質問がある場合は、コメント欄でお気軽にお知らせください。