C++で各桁がすべて奇数となるN番目の数を効率的に求める方法

C++には数学的な問題を解決するための豊富な関数群が用意されています。その中でも、各桁がすべて奇数で構成される数列の中からN番目の数を求めるというのは、興味深い数学的課題の一つです。この記事では、奇数とは何か、そして「各桁がすべて奇数である数」とはどのような数なのかを理解した上で、N番目の数を求めるための完全なアプローチを解説します。

各桁がすべて奇数で構成されるN番目の数を求める

まず基本のおさらいです。奇数とは2で割ると余りが1になる数のことで、小さい順に並べると 1, 3, 5, 7, 9, 11, 13, 15, 17, 19... となります。

ここで求めたいのは「各桁の数字がすべて奇数（1, 3, 5, 7, 9）で構成されている数」です。つまり 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 31, 33... のような数列から、n番目の数を特定します。これを実現するには、大きく分けて2つのアプローチがあります。

アプローチ1：全数チェックによる単純な方法

1つ目の方法は、すべての自然数を順番に調べ、「各桁がすべて奇数であるか」を判定し、条件を満たす数だけをカウントしていくやり方です。カウントがnに達した時点の数が答えとなります。偶数や偶数の桁を含む数はスキップします。

このアプローチは考え方がシンプルで理解しやすい反面、コンピュータプログラミングの観点では、すべての数を一つずつ確認する必要があるため、処理に多くの時間がかかるという欠点があります。

アプローチ2：規則性を利用した効率的な方法

2つ目の方法は、数列のパターンに着目した効率的な手法です。各桁が奇数のみで構成される数は、必ず一の位が 1, 3, 5, 7, 9 のいずれかになります。そこで、まず候補として 1, 3, 5, 7, 9 を確認し、n番目がこの中になければ、次の候補である 11, 13, 15, 17, 19、さらに 21, 23, 25, 27, 29 へと進みます。

これは「既存の数 × 10 + {末尾の候補数字}」というパターンで表現できます。

生成パターンの例

末尾の候補数字：1, 3, 5, 7, 9
次の候補は以下の式で導出できる
1 * 10 + 1 = 11
1 * 10 + 3 = 13
1 * 10 + 5 = 15
1 * 10 + 7 = 17
1 * 10 + 9 = 19
つまり 11, 13, 15, 17, 19

サンプルコード

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

#include<bits/stdc++.h>
using namespace std;
int main(){
    queue<int> q;
    int cnt = 0, ans = 0;
    int n;
    cin >> n;
    int a[5]={1,3,5,7,9};
    for(int i = 0; i < 5;i++){
        cnt++;
        if(cnt == n)
            ans = a[i];
        q.push(a[i]);
    }
    if(ans)
        cout << ans << "\n";
    else{
        while(true){
            int x = q.front();
            q.pop();
            for(int j = 0; j < 5; j++) {
                int temp = x * 10 + a[j];
                q.push(temp);
                cnt++;
                if(cnt == n)
                    ans = temp;
            }
            if(ans)
                break;
        }
        cout << ans << "\n";
    }
    return 0;
}

実行結果

9

入力として5を与えると、出力は9になります。これは、各桁が奇数のみで構成される数列の5番目が9であることを意味します。

上記のコードは、各桁が奇数のみで構成されるN番目の数を求めるC++プログラムです。このコードを理解するために、部分ごとに分解して詳しく見ていきましょう。

コードの解説

ステップ1：入力の受け取りと変数の初期化

int main() {
   queue<int> q;
   int cnt = 0, ans = 0;
   int n;
   cin >> n;
   int a[5]={1,3,5,7,9};

ここでは、キュー（queue）を作成し、カウント用の変数cntと答えを格納するansを初期化しています。また、cinを使ってユーザーからnを入力として受け取り、最初の候補数字（1, 3, 5, 7, 9）で配列を初期化しています。

ステップ2：最初の候補数字の中にN番目があるか判定

for(int i = 0; i < 5;i++){
   cnt++;
   if(cnt == n)
      ans = a[i];
      q.push(a[i]);
   }
   if(ans)
      cout << ans << "\n";

この部分では、配列に格納された最初の候補数字の中にn番目の数が含まれているかを確認しています。同時に、配列内の数字をキューにプッシュしておきます。もしn番目の数がこの中で見つかった場合は、即座に出力します。

ステップ3：キューを活用して次の候補を順次生成

while(true) {
   int x = q.front();
   q.pop();
   for(int j = 0; j < 5; j++) {
      int temp = x * 10 + a[j];
      q.push(temp);
      cnt++;
      if(cnt == n)
         ans = temp;
      }
      if(ans)
         break;
   }
   cout << ans << "\n";
}

最後に、キューから数を一つずつ取り出し（pop）、公式「x * 10 + 末尾の奇数」を使って次の候補となる数を生成してキューに追加していきます。各数を生成するたびにcntをインクリメントし、cntがnと等しくなった時点でその値を答えとしてループを抜けます。

まとめ

この記事では、「各桁がすべて奇数で構成されるN番目の数をどう求めるか」という問題を取り上げ、2つのアプローチを紹介しました。

1つ目のアプローチは、各数を順にチェックして条件に合わない数をスキップするだけなので非常に理解しやすいものの、計算に時間がかかるという課題がありました。

2つ目のアプローチでは、キューを使って奇数のみの数を管理し、「x * 10 + 末尾の候補数字」という公式で次々と新しい候補を生成することで効率的に答えを導き出せます。この手法の計算量はO(n)です。

今回はC++でプログラムを作成しましたが、同じロジックはC、Python、Javaなど他のプログラミング言語でも実装可能です。この記事が、問題解決へのアプローチを完全に理解する助けとなれば幸いです。