C++で数列3、5、33、35、53…のN番目の項を求めるプログラム

はじめに

このチュートリアルでは、数列「3、5、33、35、53…」のN番目の項を求めるC++プログラムについて解説します。

この問題では、ある整数nが与えられます。私たちのタスクは、その数列におけるn番目の項を特定することです。

数列の規則性

まず、この数列がどのように構成されているのかを見てみましょう。

• 1番目の項：3
• 2番目の項：5
• 3番目の項：33（1番目の項に「3」を付加）
• 4番目の項：35（1番目の項に「5」を付加）
• 5番目の項：53（2番目の項に「3」を付加）
• 6番目の項：55（2番目の項に「5」を付加）

つまり、奇数番目の項は「i/2 番目の項の末尾に3を付けた数」、偶数番目の項は「(i/2 − 1) 番目の項の末尾に5を付けた数」という規則で生成されます。この性質を利用すると、動的計画法（DP）によって効率的に任意の項を求めることができます。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
// 数列のn番目の項を求める関数
int printNthElement(int n){
    int arr[n + 1];
    arr[1] = 3;
    arr[2] = 5;
    for (int i = 3; i <= n; i++) {
       if (i % 2 != 0)
          arr[i] = arr[i / 2] * 10 + 3;
       else
          arr[i] = arr[(i / 2) - 1] * 10 + 5;
    }
    return arr[n];
}
int main(){
    int n = 6;
    cout << printNthElement(n);
    return 0;
}

実行結果

55

コードの解説

このプログラムでは、配列arrを使って数列の各項を順番に格納していきます。

1. 初期値として、1番目の項に「3」、2番目の項に「5」を設定します。
2. 3番目以降の項については、インデックスiが奇数の場合は「arr[i / 2] × 10 + 3」、偶数の場合は「arr[(i / 2) − 1] × 10 + 5」という式で計算します。
3. 「×10して3または5を足す」という操作は、既存の数値の末尾に新しい桁を追加することと同じ意味になります。

上記の例ではn = 6としているため、6番目の項である「55」が出力されます。このアルゴリズムの計算量はO(n)であり、非常に効率的にN番目の項を求めることができます。