【C++】数列 14, 28, 20, 40, … のN番目の項を求める方法を解説

問題概要

この記事では、整数値 N が与えられたとき、以下の数列の N番目の項 を求める方法を解説します。

14, 28, 20, 40, 32, 64, 56, 112, …

具体例

入力:

N = 6

出力:

64

このように、N = 6 の場合は数列の6番目の項である「64」が出力されます。

解法アプローチ

数列のN番目の項を求めるには、まず数列の一般項(規則性)を見つける必要があります。数列を注意深く観察すると、大きく分けて2つのアプローチがあることがわかります。

方法1: 奇数位置と偶数位置の2つの数列に分解する

この数列は、奇数番目の項からなる数列と、偶数番目の項からなる数列が交互に並んだ構造になっています。

奇数番目の項の規則性： 14, 20, 32, 56, …

T1 = 14
T3 = 20 = T1 + 6
T5 = 32 = T3 + 12
T7 = 56 = T5 + 24 = T1 + 6 + 12 + 24 = T1 + 6 × (1 + 2 + 4)
TN = T1 + 6 × (20 + 21 + 22 + … + 2((N/2)-1))

偶数番目の項の規則性： 28, 40, 64, 112, …

T2 = 28
T4 = 40 = T2 + 12
T6 = 64 = T4 + 24
T8 = 112 = T6 + 48 = T2 + 12 + 24 + 48 = T2 + 6 × (2 + 4 + 8)
TN = T2 + 6 × (21 + 22 + … + 2((N/2)-1))

以上のことから、数列のN番目の項は次の一般式で表せます。

T_N = T_s + 6 × Σ 2^((N/2)-1)(添字は s から N まで2ずつ増加)

• N が偶数の場合： s = 2
• N が奇数の場合： s = 1

C++での実装例

#include <iostream>
#include <math.h>
using namespace std;

long findNthAdd(int s, int i, int n){
    int sum = 0;
    for(; i <= n; i += 2){
        sum += pow(2, (int)((i/2) - 1));
    }
    return 6*sum;
}

long findNthTermSeries(int n){
    int s, i;
    if(n % 2 == 0){
        s = 28;
        i = 4;
    }
    else{
        s = 14;
        i = 3;
    }
    return ( s + findNthAdd(s, i, n));
}

int main(){
    int n = 15;
    cout<<n<<"th term of the series is "<<findNthTermSeries(n);
    return 0;
}

出力:

15th term of the series is 776

方法2: 前の項との関係に着目する

もう一つのシンプルな解法は、「現在の項は、前の項の2倍、もしくは前の項より8小さい値になる」という規則性を利用する方法です。どちらになるかは、その項の位置が偶数か奇数かによって決まります。

N が偶数の場合： TN = 2 × T(N-1)
N が奇数の場合： TN = T(N-1) - 8

したがって、2からNまでループ処理を行い、各位置が偶数か奇数かを判定しながら項の値を順番に計算していきます。

C++での実装例

#include <iostream>
using namespace std;

bool isEven(int N){
    if(N % 2 == 0)
        return true;
    return false;
}

int findNthTermSeries(int n){
    int TermN = 14;
    for (int i = 2; i <= n; i++) {
        if (isEven(i))
            TermN *= 2;
        else
            TermN -= 8;
    }
    return TermN;
}

int main(){
    int n = 15;
    cout<<n<<"th term of the series is "<<findNthTermSeries(n);
    return 0;
}

出力:

15th term of the series is 776

まとめ

数列 14, 28, 20, 40, … のN番目の項を求めるには、①奇数位置と偶数位置それぞれの一般式を導出する方法と、②「偶数位置なら前の項の2倍、奇数位置なら前の項から8を引く」という漸化式的な規則を利用する方法の2つがあります。特に方法2はロジックが直感的で実装も簡単なため、可読性の高いコードを書きたい場合に適しています。