C++で配列の偶数・奇数インデックス要素の絶対差を求める方法

この記事では、配列内の偶数インデックスと奇数インデックスにある要素の絶対差を求める方法を解説します。絶対差とは、2つの値の差が負になった場合にも絶対値を取ることを指します。

例として、配列 {1, 2, 3, 4, 5, 6, 7, 8, 9} を考えてみましょう。インデックスは0から始まるため、各要素は次のように分類されます。

• 偶数インデックス（0, 2, 4, 6, 8）の要素：1, 3, 5, 7, 9
• 奇数インデックス（1, 3, 5, 7）の要素：2, 4, 6, 8

計算の手順

まず初期値0から出発し、該当するインデックスの要素を順番に見ながら、直前の累積値との差の絶対値を求めていきます。

偶数インデックス側：

• |0 − 1| = 1
• |1 − 3| = 2
• |2 − 5| = 3
• |3 − 7| = 4
• |4 − 9| = 5

奇数インデックス側：

• |0 − 2| = 2
• |2 − 4| = 2
• |2 − 6| = 4
• |4 − 8| = 4

したがって、偶数インデックスの絶対差は5、奇数インデックスの絶対差は4になります。

アルゴリズム

oddEvenDiff(arr, n)

begin
    even := 0
    odd := 0
    for i := 0 to n-1, do
        if i is even, then
            even := |even – arr[i]|
        else
            odd := |odd – arr[i]|
    done
    return (odd, even)
end

C++での実装例

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

void oddEvenDiff(int arr[], int n, int &o, int &e) {
    int even = 0;
    int odd = 0;
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            even = abs(even - arr[i]); // 偶数インデックスの差を更新
        } else {
            odd = abs(odd - arr[i]);   // 奇数インデックスの差を更新
        }
    }
    e = even;
    o = odd;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int odd, even;
    oddEvenDiff(arr, n, odd, even);
    cout << "The odd and even differences are: " << odd << " and " << even;
}

実行結果

The odd and even differences are: 4 and 5

処理のポイント

このプログラムでは、変数evenとoddをそれぞれ0で初期化し、forループで配列を先頭から走査します。インデックスiが偶数ならevenを、奇数ならoddを、「これまでの累積値と現在の要素の差の絶対値」で更新していきます。

ループが終了した時点で、evenには偶数インデックス全体の絶対差、oddには奇数インデックス全体の絶対差が格納されています。配列を一度だけ走査すれば処理が完了するため、計算量はO(n)と非常に効率的です。