C++で指定された数列のN番目の項を求めるプログラム

この問題では、数値 N が与えられ、指定された数列のN番目の項を求めるプログラムをC++で作成します。

問題の説明

次の数列のN番目の項を求めます。

1, 1, 2, 3, 4, 9, 8, 27, 16, 81, 32, 243, 64, 729, 128, 2187, 256, ... （N項まで）

まずは、この数列の一般項（規則性）を見つけるところから始めます。

具体例で問題を確認してみましょう。

例1

入力： N = 6

出力： 9

例2

入力： N = 13

出力： 64

解法のアプローチ

この問題を解くには、まず数列を注意深く観察する必要があります。この数列は複数の規則が混ざった「混合数列」と呼ばれるタイプで、一見するとパターンが分かりにくいですが、一度規則性に気付いてしまえば簡単に扱えるようになります。

この数列は、次のような構造を持っています。

• 偶数番目の項 … 3の累乗（3⁰, 3¹, 3², 3³, ...）が並んでいます。
• 奇数番目の項 … 2の累乗（2⁰, 2¹, 2², 2³, ...）が並んでいます。

したがって、一般項は次のように表すことができます。

T_N = 2^N/2（Nが奇数の場合）

T_N = 3^(N−1)/2（Nが偶数の場合）

※指数の計算には整数除算を使用します。

C++での実装例

#include <iostream>
#include <cmath>
using namespace std;

// 数列のN番目の項を求める関数
int findNTerm(int N) {
    // Nが偶数の場合：3の累乗
    if (N % 2 == 0) {
        return pow(3, (N - 1) / 2);
    }
    // Nが奇数の場合：2の累乗
    else {
        return pow(2, N / 2);
    }
}

int main() {
    int N = 9;
    cout << N << "番目の項は " << findNTerm(N) << endl;
    N = 14;
    cout << N << "番目の項は " << findNTerm(N);
    return 0;
}

出力結果

9番目の項は 16
14番目の項は 729

コードの解説

findNTerm 関数では、N を2で割った余りを判定し、N の偶奇によって処理を分岐させています。

• N が偶数の場合：3 を (N−1)/2 乗した値を返します。
• N が奇数の場合：2 を N/2 乗した値を返します。

べき乗計算が1回だけで済むため、時間計算量は O(log N)、空間計算量は O(1) と非常に効率的です。なお、N が大きくなると結果が急激に増大するため、実際の利用では整数型のオーバーフローに注意してください。