数列 7, 15, 32, … のn番目の項を求めるC++プログラム

この問題では、整数 N が与えられ、数列「7, 15, 32, …」のn番目の項を求めることが課題となります。

問題を理解するための例

入力

N = 6

出力

281

説明

n番目の項までの数列は「7, 15, 32, 67, 138, 281」となります。

解法アプローチ

この問題を解く鍵は、数列の規則性を読み解くことにあります。この数列は、複数の規則が組み合わさった複合的な数列であることがわかります。

まず、隣接する項同士の差を調べてみましょう。

T(2) - T(1) = 15 - 7 = 8
T(3) - T(2) = 32 - 15 = 17

ここから、各項の間には次のような漸化式の関係が成り立っていることが導き出せます。

T(2) = 2*T(1) + 1
T(3) = 2*T(2) + 2

T(n) = 2*T(n-1) + (n-1)

つまり、n番目の項の値は、ひとつ前の項を使って求められるということです。この性質を利用し、1からnまでループ処理を行うことで、数列の各項の値を順番に計算していきます。

解法の動作を示すプログラム

例

#include <iostream>
using namespace std;
int findNthTerm(int n) {
    if (n == 1)
        return 7;
    int termN = 7;
    for (int i = 2; i <= n; i++)
        termN = 2*termN + (i - 1);
    return termN;
}
int main(){
    int n = 12;
    cout<<"The series is 7, 15, 32, 67...\n";
    cout<<n<<"th term of the series is "<<findNthTerm(n);
    return 0;
}

出力

The series is 7, 15, 32, 67...
12th term of the series is 18419